Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof in graph theory

  1. Oct 1, 2010 #1
    1. The problem statement, all variables and given/known data

    Prove the following:

    If the tournament graph is acyclic, there is exactly one vertex which got edges more than any vertex in the graph.

    2. Relevant equations

    A tournament is a directed graph (digraph) obtained by assigning a direction for each edge in an undirected complete graph


    3. The attempt at a solution

    I am not sure how to start. Is it easier to go with the indirect proof (i.e proof by contradiction) ?

    Lets say that that kind of vertex does not exist. Than either all vertices have equal number of edges or there are two edges or more with same number of edges which got more edges than any other pair of vertices.

    Because the graph is acyclic we could easily see that the relation under the graph is not transitive, not symmetric, not reflexive, is asymmetric.

    Could somebody help me please and tell me if I should prove like the way I did?

    Thank you.
     
  2. jcsd
  3. Oct 3, 2010 #2
    any ideas please?
     
  4. Oct 3, 2010 #3
    Question: If a tournament graph is simply a complete graph with directions assigned to each edge, how can any vertex in a tournament graph have more edges than the others? In a complete graph every vertex "has" the same number of edges.
     
  5. Oct 3, 2010 #4
    Sorry for misunderstanding but I meant starting edges (directed graph) or vertex with max indegree.

    Thank you.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook