# 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

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

## Related Questions

### Derivative of vectorized function wrt to a Cholesky decompositiion

1  Asked on November 29, 2021 by user802652

### Simplification of division of integral of standard normal distribution

0  Asked on November 29, 2021 by ga13

### How does integration affect the spectrum of a vector outer product?

1  Asked on November 29, 2021

### Condition number – eigenvalues

0  Asked on November 29, 2021 by felipe-ca

### Is there a general form for the relation between $df(x)$ and $dx$?

3  Asked on November 26, 2021

### Solve second order DE: $sin^2 xfrac{d^2y}{dx^2} = 2y$

1  Asked on November 26, 2021

### Spiral equation

1  Asked on November 26, 2021

### If $exists$ a surjection from nonempty set $A$ onto $mathcal{P}(mathbb{Z_+})$, then $A$ is uncountable

0  Asked on November 26, 2021

### How to show that $int_0^1frac{sin(frac{1}{x})}{x^2}dx$ diverges?

1  Asked on November 26, 2021 by abuka123

### Question regarding measure theory and Lebesgue integral

0  Asked on November 26, 2021

### Scaling of a matrix and its impact on eigen values

0  Asked on November 26, 2021

### Is there any infinitesimal number both definable and computable?

1  Asked on November 26, 2021 by user403504

### Prove that if $p$ and $q$ are rational number with $p < q$ then there exist $r in A$ such that $p le r le q$

1  Asked on November 26, 2021 by npdfe

### Prove that $|a + b| = |a| + |b| iff aoverline{b} ge 0$

4  Asked on November 26, 2021

### Let $G$ be a finite nilpotent group and $G’$ its commutator subgroup. Show that if $G/G’$ is cyclic then $G$ is cyclic.

3  Asked on November 26, 2021

### Proof of fourier transform expression

0  Asked on November 26, 2021

### Why power set of $Omega$ (set of all outcomes) can’t always be used as field in probability space ($Omega,mathcal{F}, P$)?

0  Asked on November 26, 2021

### Topological proof for the unsolvability of the quintic

1  Asked on November 26, 2021

### Question about convergence of a sum of integrals as mesh tends to $0$ using continuity

1  Asked on November 26, 2021

### Prove that if $a, b, c$ are positive odd integers, then $b^2 – 4ac$ cannot be a perfect square.

6  Asked on November 26, 2021 by topher