CopeCope's blog

Prove or disprove
By CopeCope, history, 8 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 \lt =i,j \lt =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

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

Is graph directed?

→ Reply
»
8 years ago, hide # |
← 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 \lt 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
  • »
    »
    8 years ago, hide # ^ |
     
    Vote: I like it +3 Vote: I do not like it

    Thank you :)

    → Reply
    • »
      »
      »
      8 years ago, hide # ^ |
       
      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 \gt 1$$$

      → Reply