3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ @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). $\endgroup$ – Tyler Seacrest Feb 18 '15 at 8:01
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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$? $\endgroup$ – budwarrior Dec 29 '17 at 10:59
  • $\begingroup$ 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. $\endgroup$ – Adam Lowrance Jan 5 '18 at 15:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.