Spanning trees for complete graph

Question

Let $K_n = (V, E)$ be a complete undirected graph with $n$ vertices (namely, every two vertices are connected), and let $n$ be an even number. A spanning tree of $G$ is a connected subgraph of $G$ that contains all vertices in $G$ and no cycles. Design a recursive algorithm that given the graph $K_n$, partitions the set of edges $E$ into $n/2$ distinct subsets $E_1,E_2,\dots,E_{n/2}$, such that for every subset $E_i$, the subgraph $G_i = (V, E_i$) is a spanning tree of $K_n$.

(Hint: Solve the problem recursively by removing two nodes and their edges in $K_n$. From the output of recursive call, you get $(n − 2)/2$ spanning trees for $K_{n−2}$. Extend those trees to be spanning trees for $K_n$ and then construct a new spanning tree to complete the job. PS: A collection of sets $S_1,\dots,S_k$ is a partition of $S$, if each $S_i$ is a subset of $S$, no two subsets have a non-empty intersection, and the union of all the subsets is $S$.)

Even with the hint, I'm struggling to understand how to solve this question. So when you remove two vertices, you get $n/2 - 1$ spanning trees for $K_{n-2}$, and somehow expand this to $n/2$ spanning trees for $K_n$? Any help would be appreciated.

Answer 1

Here is how one step of the construction might look like - going from a tree decomposition of $K_4$ to a tree decomposition of $K_6$.

On the left, we have (in orange and teal) a partition of the edges of a $K_4$ into two spanning trees. The $K_4$ is sitting inside a $K_6$ that we want to decompose. So on the right, we extend the orange and teal trees by two edges each to make them spanning trees of $K_6$, and add a purple tree consisting of the remaining edges.

To go from $K_6$ to $K_8$, you'll extend each of these three trees by two edges each, then add a fourth tree.

For any particular step, it is not too hard to make this work. The important thing is to figure out a pattern to tell you how to go from $n-2$ to $n$ for any even $n$. For this, you should try to do something as symmetric as possible, because symmetric things are easiest to describe.

For example, if we're adding two vertices $x$ and $y$, then there's one "unusual" edge: the edge $xy$. I made this edge part of the new, purple tree in the diagram above, because adding it to just one of the existing trees would break symmetry. You could still do it - it would just be harder to describe what you're doing generally.

From there, think about what we're doing to go from $K_4$ to $K_6$ - or try going from $K_6$ to $K_8$ yourself, if you think you need more to go on - and then generalize.