graph theorytrees
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$.
Conceptual note
First, note that each spanning tree will have $|G|-1$ edges... since $G$ is partitioned into $n$ vertex classes, it is likely that each tree has more than $n-1$ vertices total, i.e. $|G|\geq n$ but could be much much larger than $n$.
Rough idea of solution
Consider any partition of the vertex set $V_1,...,V_{n}$ and let $T_{i}$ be a spanning tree--one of the $k$ edge disjoint spanning trees you are guaranteed to have. Consider only the edges in $T_{i}$ and view the sets $V_{i}$ as a single vertex; say that $V_{i}\sim V_{j}$ if any vertex in $V_{i}$ is adjacent to any vertex in $V_{j}$. Note that since $T_{i}$ is a spanning tree the glob graph you just created is connected. Since the glob graph is on $n$ vertices and is connected it contains at least $n-1$ edges. These edges are precisely those in $T_{i}$ that have endpoints in two different partitions of the vertices. You could have constructed the edge set of your glob graph with any of the $k$ edge-disjoint spanning trees. Thus, you have at least $k(n-1)$ edges with endpoints in two different sets of vertices.
The answers to the question you linked are not all correct. In particular, the answer relating to maximum flow computation is wrong. Let me first give you an example showing that this answer is wrong and then further readings stating correct algorithms for finding edge-disjoint trees in a graph.
Consider the following graph:
This graph obviously admits a flow of value 2 between any two vertices. However, it does not admit 2 edge-disjoint spanning trees. Assume such two trees $T_1$ and $T_2$ would exist.
Thus, the given graph fulfills the requirement that between every two vertices there exists a flow of value at least two, but the graph does not admit two edge-disjoint trees.
Luckily, another answer to the question you linked is correct: The works of Tutte [1] and Nash-Williams [2] give characterizations of the graphs that admit $k$ edge-disjoint trees as well as algorithms computing these trees.
In the above example, consider the partition $P = \{\{1\}, \{2,6\}, \{3,7\}, \{4\}, \{5\}, \{8\}\}$ for $r = 6$. There are 8 edges with endpoints in different sets of the partition. However, the characterization of Tutte and Nash-Williams requires there to be $k (r - 1) = 2 \cdot 5 = 10$ such edges. Therefore, the above example does not fulfill the conditions.
Since the author of the original answer only gave the authors of the papers, here are the full references to the two papers.
[1] On the Problem of Decomposing a Graph into n Connected Factors, Tutte, 1961, Journal of the London Mathematical Society s1-36(1), pages 221-230
[2] Edge-Disjoint Spanning Trees of Finite Graphs, Nash-Williams, 1961, Journal of the London Mathematical Society s1-36(1), pages 445-450
Best Answer
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.