# Thread: Prove of path which is n-1 edge long

1. ## Prove of path which is n-1 edge long

Hi guys so I have this problem and need to find a proof. There is tennis tournament where we have n players. Every player plays match with every other player. We create graph where nodes are players and edges are made from player who won to player who lost. I need to prove that there is path in this graph that is n-1 edges long. But how?

2. ## Re: Prove of path which is n-1 edge long

Is this a directed graph? Because if not the graph you describe is the complete graph on n vertices.

If it is not directed, the proof is trivial. If it is directed, use Induction. Base of induction is a tournament with two players. No matter who wins, you have a path of length 1. Suppose it is true up to n players. We want to see if it is true for n+1 players. Remove any player. The remaining n players satisfy induction hypothesis, so there is a path of length n. Line them up in order of their wins:
1->2->...->n
If the removed player beat #1, there is a path from him to 1 to ... to n
If he lost to 1, but beat 2, there is a path from 1 to him to 2 to ... to n
.
.
.
If he lost to every player, the path goes from1 to ... to n to him.

3. ## Re: Prove of path which is n-1 edge long

Originally Posted by SlipEternal
The remaining n players satisfy induction hypothesis, so there is a path of length n.
That was supposed to read a path of length n-1.