snorkel's blog

Proof about Complete Graph
By snorkel, history, 4 years ago, In English

How do I prove that the Complete Graph with $$$n$$$ ($$$n$$$ is even) vertices can have as much as $$$n / 2$$$ disjoint spanning trees (spanning trees that does not share an edge between them)?

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Here's a construction I found by trying to add two vertices and one spanning tree inductively to a smaller solution and then simplifying the result: Pair up the vertices arbitrarily. Each spanning tree will correspond to one of the $$$n/2$$$ pairs and will contain the edge between the two vertices in its pair. The other $$$n-2$$$ vertices will be leaf nodes. This means that for two pairs $$$(x, y)$$$ and $$$(u, v)$$$, two of the edges between them will be used to connect $$$x$$$ and $$$y$$$ to the $$$(u, v)$$$ spanning tree and the other two edges between them will be used to connect $$$u$$$ and $$$v$$$ to the $$$(x, y)$$$ spanning tree in a pattern like this one:

Since every edge is either within one pair or connects two different pairs, this accounts for every edge.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I can't get your solution. So you have a solution for $$$n-2$$$ and add $$$2$$$ vertices to it, but you say `"arbitrarily" which is confusing for me. Overall I can't understand anything.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Adding two vertices at a time was how I originally found this solution, but isn't how I chose to describe it, since it turned out that the order in which the vertex pairs were added doesn't make a difference. Maybe a picture demonstrating the construction on a slightly larger case will make it clear? Here's one with $$$n=8$$$.

      Spoiler
      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        So in "arbitrarily" you mean if you randomly add edges to those two new vertices, it will be still a valid partition?

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          The only thing I mention as done "arbitrarily" is the pairing of vertices. Please don't let this one word confuse you: It's obvious that the vertices can be relabeled after-the-fact in any strategy. I included this word only to emphasize that, despite the inductive origins of my strategy, all of the spanning trees it creates are basically the same. (This is in contrast to the possibility of one most-recently-added spanning tree being possible to single out, or something like that.)

          Each of the four quadrants in the spoilered image illustrates only one spanning tree completely (because I thought all four on top of one another were quite visually cluttered), and uses the bold edges to indicate the pairing, which is the red spanning tree to the top two vertices, the green spanning tree to the bottom two vertices, and so on.

          If you look at only the six edges between the top two nodes (the pair corresponding with the red spanning tree) and the bottom two nodes (the pair corresponding with the green spanning tree), you can see that they form the same pattern as in the diagram in my first comment. The same goes for the six edges between the two non-leaves of any two spanning trees.

          Technically for each of the $$$\binom {n/2}{2}$$$ sets of two spanning trees, there are two ways to create this pattern, but here I intentionally did not use the word "arbitrarily" despite the existence of some choice because there are obviously a few colorings that don't make this pattern and thus don't work!

          → Reply
»
4 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Hello;

I think by proving that every complete graph with n (n is even) vertices can be decomposed into n/2 Hamiltonian simple paths, your question would be answered, because that seems like kind of a spanning tree too.

I'll give you an idea of what you can do, place the vertices of the complete graph on a regular polygon, try to zigzag through the vertices, starting from each vertex once, and the complete graph will be decomposed into n/2 Hamiltonian paths.

Here is how it happens for a complete graph with six vertices, I think this shall clarify the explanations

first
second
third

Now you just need to say somehow that this always works, not that hard I guess

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How is this the Hamiltonian path? I was not able to form the Hamiltonian path by first traversing the tree with the first photo and then second for example.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      sorry for the late reply;

      Well the paths are not continuous, that is when you finish the first photo, you should take the pen off the paper, and start drawing the second zigzag, which is the yellow one, and then do the same procedure for the third one.

      and at the end, each of these would be a Hamiltonian path

      → Reply