Prove that T is transitive if and only if the score of the $k^{th}$ vertex ($s_k$) = '$k-1$' for $k =1,2,ldots. n $

Mathematics Asked by user146215 on December 14, 2020

There is a transitive tournament (T) with $n > 1$ vertices and the score sequence is defined as $s_1, s_2, ldots,s_n$

Prove that T is transitive if and only if the score of the $k^{th}$ vertex ($s_k$) = ‘$k-1$’ for $k =1,2,ldots. n $

i.e $s_k = k-1$ for all $k= 1,2,3,ldots, n$

I have been researching and noticed that this is similar to the Landau’s Theorem (1953), however i am completely lost with the proof. I know that the score is the out degree, and i know that the out degree is the total number of edges going out of the vertex which is of course also (0,1,2,3…n-1).

I know that a tournament must have a unique ranking, and i also know that at transitive tournament must have at least one in degree on 0 .

I also know that a transitive tournament must have a score sequence of $(0,1,2,3,…n-1)$, and obviously the in degree is the number of edges minus that.

I have tried going along the lines of proof by contradiction, but i am completely stuck

I would really like to find a proof for this, please help!

One Answer

We want to show that a transitive tournament with $n$ vertices has the score sequence of $(0,1,2,…,n−1)$. Now suppose that it holds for all the transitive tournaments.

The proof is by induction on the number of vertices of $T$, the result being trivial for transitive tournaments with at most two vertices.

Let T be a transitive tournament with $n+1$ vertices. We know that a tournament is an orientation of a complete graph. In addition, transitivity implies that $T$ is acyclic. So $T$ has a vertex $V$ with out-degree of $n$. If we delete $V$ and it's incident edges, then the graph that remains is a transitive tournament with $n$ vertices and it has a vertex with out-degree of $n-1$. By our induction hypothesis, this graph has the score sequence of $(0,1,2,…,n−1)$. Appending the score of V to it gives the score sequence of $T$ which is $(0,1,2,...,n)$.

Now we want to show that if score sequence $(S_1,S_2,S_3,...,S_n)$ where $S_k=k-1$ for all $k=1,2,3,…,n$ then $T$ is transitive.

Remove leaf vertex $V$ and it's incident edges. Removing $V$ will decrease all of the remaining vertices in-degrees by one so there will be another leaf vertex. Keep removing leaf vertices, we will eventually remove all vertices: The tournament is acyclic therefore transitive.

Answered by Root G on December 14, 2020

Add your own answers!

Related Questions

Condition number – eigenvalues

0  Asked on November 29, 2021 by felipe-ca


Spiral equation

1  Asked on November 26, 2021


Ask a Question

Get help from others!

© 2022 All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP