Let $D$ be a transitive tournament. Show that there is an order $v_1, v_2, ..., v_n$ of the vertices of $D$

178 Views Asked by At

Let $D$ be a transitive tournament. Show that there is an order $v_1, v_2, ..., v_n$ of the vertices of $D$, such that $d^+(v_i) = n-i$ for all $i = 1,..., n$.

My try:

Let $v_1 \in V$ such that $d^+(v_1) = n - 1$, which means that it has edges to the rest of the vertices of $D$, particualarly $v_2 \in V$, such that $d^+(v_2) = n-2$, which has edges to all $v_i\in V/(v_1,v_2)$. If we keep doing this process we end up with $v_n\in V$, such that $d^+(v_i) = 0$.

I don't know if this process is correct. Any suggestions would be great!

1

There are 1 best solutions below

2
On BEST ANSWER

The idea of your proof is correct, but you haven't shown that $d^+(v_i)=n-i$ for each $i$. These follow from the tournament's transitivity.

A simpler writeup would be as follows: $D$ is transitive, so it has a topological ordering; $D$ is a tournament, so in this topological ordering there is an edge from every node to every later node. Then the outdegrees of the vertices can be read off from the ordering: the first node has outdegree $n-1$, the second $n-2$ and so on up to the last vertex having outdegree $0$.