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$. 



Removing cycles from an undirected connected bipartite graph in a special manner
[edited]


It seems this question is NP-Complete. 


The general idea:
In a graph which is a 3-regular graph minus an edge, 
a spanning tree that minimizes $\max x\_i$ is (more or less) an Hamiltonian Path.
Some more work is needed in order to make it an Hamiltonian Cycle;
finding an Hamiltonian Cycle in a 3-regular bipartite graph is NP-complete.


Assume there is an algorithm for finding such a set $C$ for any bipartite graph.
Consider only the subclass of graphs with $v\_1 = v\_2$, that are also 3-regular. 


* The reduction:


Consider a 3-regular bipartite graph $G$. 
Add two vertices to the graph, $a\_1\in V\_1$, $a\_2 \in V\_2$.
We repeat the rest for every choice of an edge $(b\_1,b\_2) \in E$:
Split $(b\_1,b\_2)$ into the two edges $(a\_1, b\_2)$ and $(b\_1, a\_2)$;
mark the new graph as $G'=(V,E')$.
Run the algorithm on $G'$ to find a set $C$ of edges that minimizes $\max x\_i$.
If the value returned is $1$, then $E' \setminus C$ induces an 
Hamiltonian Cycle in $G$; 
if a value greater than $1$ is always returned, no such cycle exists in $G$.


* Correctness:


From the new vertices, $a\_1$ and $a\_2$, 
the algorithm cannot remove an edge, as it will leave them disconnected.
From any other vertex, it must remove at one edge in average, 
as every other vertex has degree 3.


The algorithm can find a set $C$ with $\min \max x\_i = 1$
iff its complement $E' \setminus C$ is an Hamiltonian Path connecting $b\_1$ and $b\_2$;
this path induces an Hamiltonian Cycle in $G$.


Finding an Hamiltonian Cycle in a 3-regular bipartite graphs is NP-Complete (see this [article](http://www.nishizeki.ecei.tohoku.ac.jp/nszk/nishi/sub/j/DVD/PDF_J/J029.pdf)), which completes the proof.


