Two disjoint spanning trees, spanning subgraph with all even degrees Show that if a graph has two edge-disjoint spanning trees then it has a connected, spanning subgraph with all degrees even. 
I start by looking at the union of the two spanning trees. I know it has $2n-2$ edges and is connected. But I don't know where to go from there. Perhaps it has to do with Euler circuits? If I prove the union has a Euler circuit I can just take the circuit and then the degrees are all $2$.
 A: I like the Eulerian circuit idea but I find it's almost always easier to use induction when working with trees -- in particular, induction involving removing a leaf and continuing down the tree in that manner.  To get that to work in this case requires a bit of modification, but it works.  For example, here is a slightly stronger statement:
``A graph $G$ contains a connected spanning subgraph $A$ and a (potentially non-spanning) tree $B$, edge-disjoint from $A$, that contains all of $A$'s odd vertices.  Then $G$ contains a spanning connected subgraph of all even degrees."
Proof sketch:  Induct on the number of edges in $B$.  Choose edge $uv$ where $v$ is a leaf of $B$.  If $v$ is odd for $A$, then add the edge $uv$ to $A$ and remove it from $B$.  If $v$ is even for $A$, then just remove $uv$ from $B$ without adding it to $A$.  Either way, the number of edges in $B$ is smaller, so induction carries you the rest of the way.
A: Without using induction you need to look at one spanning tree say $T_1$, Now let's look at the number of odd degrees in it:
$V_{odd}(T_1)={v_1,v_2,...,v_{2k-1},v_{2k}}$ We have an even number of odd degrees.


*

*let's pair $V_{odd}(T_1)$ look at those pairs:$(v_1,v_2) ,...,(v_{2k-1},v_{2k})$
Look at $T_2$ we have between each such pair $(v_i,v_{i+1})$ a unique path between those two vertices $P_i$ in $T_2$ and $P_i$ is edge disjoint from all paths in $T_1$.

*Look at pair $(v_i,v_{i+1})$ and add $P_i$, and do so for every i. Look what happens to the degrees start with i=1 and continue, you will build a spannig graph of G with all degrees even. See that you understand how.
