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

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.

• @UserB95: what about the condition that B contains all of As odd vertices? If B is a single edge, this is unlikely to be fulfilled (and if it is fulfilled by this single edge, then A + B works as having all even degrees). – Tyler Seacrest Feb 18 '15 at 8:01

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.

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

2. 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 don't understand why all the vertices at the end must have even degree. Won't it cause a problem if we have $P_i\subset P_j$ for some $i>j$? – budwarrior Dec 29 '17 at 10:59
• This approach can be modified to work. Start with $H_1:= T_1$ and build a sequence $T_1=H_1,H_2,\dots,H_k$ where $H_k$ is the desired connected spanning subgraph with even degree. Define $H_{i+1} = H_i \vartriangle P_i$ where $\vartriangle$ denotes the symmetric difference. The number of odd vertices decreases by two at each step. Also, $T_1$ is a subgraph of each $H_i$, so $H_k$ is connected and spanning. – Adam Lowrance Jan 5 '18 at 15:53