Consider an undirected connected bipartite graph (with cycles) $G = (V_1,V_2,E)$, where $V_1,V_2$ are the two node sets and $E$ is the set of edges connecting nodes in $V_1$ to those in $V_2$. We assume that $|V_1|=v_1$, $|V_2|=v_2$ and $|E|=e$.

Then $(e-v_1-v_2+1)$ edges need to be removed to make $G$ a spanning tree, we refer to this set of removed edges as $C$. We define $x_i$ as the decrease in the degree of $i$th node in $V_1$ due to choice of $C$ and subsequent removal of edges (i.e., $x_1+x_2+\cdots+x_{v_1}=e-v_1-v_2+1$).

We may have multiple choices for $C$ (the number of choices equals the number of spanning trees). I am interested in finding a choice of $C$ that minimizes $\max x_i$. In particular, I want to know if the problem is NP-hard or if there is a polynomial-time (in $v_1,v_2,e$) algorithm that can generate the desired choice of $C$.