Results 1 to 3 of 3

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

  1. #1
    Newbie
    Joined
    Nov 2017
    From
    Slovakia
    Posts
    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,967
    Thanks
    1140

    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.
    Last edited by SlipEternal; Nov 2nd 2017 at 04:15 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,967
    Thanks
    1140

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

    Quote Originally Posted by SlipEternal View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 14
    Last Post: Oct 30th 2012, 07:40 AM
  2. Replies: 2
    Last Post: Jul 23rd 2010, 04:42 AM
  3. The long path
    Posted in the Math Puzzles Forum
    Replies: 5
    Last Post: Apr 8th 2010, 02:42 PM
  4. Replies: 11
    Last Post: Jan 14th 2010, 07:24 PM
  5. Prove that C(X) is path-connected
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: May 20th 2009, 09:34 PM

/mathhelpforum @mathhelpforum