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