CopeCope's blog

Prove or disprove
By CopeCope, history, 6 years ago, In English

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

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is graph directed?

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +48 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Thank you :)

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +42 Vote: I do not like it

      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$$$

      → Reply