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

Prove or disprove
Автор CopeCope, история, 6 лет назад, По-английски

Given graph with $$$N$$$ vertices and there are $$$N*(N-1)/2$$$ edges, each one is either $$$(i,j)$$$ or $$$(j,i)$$$ for every $$$1<=i,j<=N$$$. How to prove or disprove that there is always a path of length $$$N-1$$$(edges) that visits every vertex once

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is graph directed?

→ Ответить
»
6 лет назад, # |
← Rev. 3   Проголосовать: нравится +48 Проголосовать: не нравится

there is always such a path.

Proof by induction: suppose for every graph of size $$$n$$$ there is such a path $$$(p_0, p_1, \dots, p_n)$$$ (obviously its true for $$$n < 3$$$) we now add a new vertex $$$x$$$. The edge between $$$x$$$ and $$$p_n$$$ has to go from $$$x$$$ to $$$p_n$$$ as else we would already have our path. Now the edge from $$$p_{n-1}$$$ has also go from x to $$$p_{n-1}$$$ or we could just add $$$x$$$ between $$$p_{n-1}$$$ and $$$p_n$$$. This goes on until we reach the vertex $$$p_0$$$. We still have to add the edge from $$$x$$$ to $$$p_0$$$ for the same reason (our path would be $$$p_0, x, p_1, \dots$$$). But adding the edge like this also leads to a path $$$(x, p_0, p_1, \dots)$$$. Therefore the statement holds for all graphs on $$$n + 1$$$ vertices. By induction there is always such a path.

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

    Thank you :)

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

      even more interesting: you need all $$$\frac{N \cdot (N-1)}{2}$$$ edges for the statement to be true, with a single edge less there are counterexamples for every $$$n > 1$$$

      → Ответить