### CopeCope's blog

By CopeCope, history, 7 months ago, ,

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

 » 7 months ago, # |   0 Is graph directed?
•  » » 7 months ago, # ^ | ← Rev. 2 →   0 Yes,edge is either from i to j or j to i
 » 7 months ago, # | ← 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.
•  » » 7 months ago, # ^ |   +3 Thank you :)
•  » » » 7 months ago, # ^ |   +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$