Results 1 to 4 of 4

Math Help - Graph Theory

  1. #1
    Len
    Len is offline
    Member
    Joined
    Mar 2008
    Posts
    93
    Thanks
    1

    Graph Theory

    Let T be a tournament on n vertices. Prove that:



    A question from my book I am not sure how to do, anyone can show me how to solve or any tips on tackling this problem?

    Thanks =)

    Edit: all my stats were deleted :P
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Dec 2010
    Posts
    470
    With a tournament of n vertices each vertex v has:
    indeg(v) + outdeg(v) = n - 1

    Think about this.
    \sum (outdeg(v)^2 - indeg(v)^2)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Len
    Len is offline
    Member
    Joined
    Mar 2008
    Posts
    93
    Thanks
    1
    Quote Originally Posted by snowtea View Post
    With a tournament of n vertices each vertex v has:
    indeg(v) + outdeg(v) = n - 1

    Think about this.
    \sum (outdeg(v)^2 - indeg(v)^2)
    Thanks for the reply.

    So the degree has to be n-1 because in a tournament every vertex is connected to every other vertex.

    I'm having trouble wraping my head around the concept here... This is what I am understanding, in the tournament, the sum of all out degree must equal the sum of all in degree(intuitively for every out, there must be an in)

    Maybe I am misunderstanding the question but what is the signifigance of squaring it? If x=y then of course x^2=y^2

    \sum (outdeg(v)^2 - indeg(v)^2) Would this not equal zero?

    I'm sorry but I really do appreciate the help.

    Thanks
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Dec 2010
    Posts
    470
    Quote Originally Posted by Len View Post
    Thanks for the reply.
    So the degree has to be n-1 because in a tournament every vertex is connected to every other vertex.
    Yes.

    I'm having trouble wraping my head around the concept here... This is what I am understanding, in the tournament, the sum of all out degree must equal the sum of all in degree(intuitively for every out, there must be an in)
    You are correct, but you will not use this until later.

    \sum (outdeg(v)^2 - indeg(v)^2) Would this not equal zero?
    This is what you are trying to show
    Hint factor.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph theory, bipartite Graph
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: March 10th 2012, 06:47 AM
  2. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2011, 10:59 AM
  3. (Graph Theory)Prove that graph X is a tree.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 1st 2011, 04:30 AM
  4. Replies: 0
    Last Post: September 25th 2010, 06:59 AM
  5. Graph Theory - Size of a Line Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 26th 2010, 12:15 AM

Search Tags


/mathhelpforum @mathhelpforum