# Proof in graph theory

1. Oct 1, 2010

### njama

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. Oct 3, 2010

### njama

any ideas please?

3. Oct 3, 2010

### JThompson

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.

4. Oct 3, 2010

### njama

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