Блог пользователя snorkel

Proof about Complete Graph
Автор snorkel, история, 4 года назад, По-английски

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)?

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
4 года назад, # |
← Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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
      → Ответить
      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        → Ответить
        • »
          »
          »
          »
          »
          4 года назад, # ^ |
          ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          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!

          → Ответить
»
4 года назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

      → Ответить