Prove the condition of the score sequence make the tournament strong Prove the theorem 4.19: A non-decreasing sequence $\pi:s_1,s_2,\ldots,s_n$ of nonnegative integers is a score sequence of a strong tournament if and only if 
$$\sum_{i=1}^ks_i > \binom k 2 $$
for $1≤k≤n-1$ 
and 
$$\sum_{i=1}^ns_i = \binom n 2 $$
Furthermore, every tournament whose score sequence satisfies these conditions is strong.
I know how to show that $\pi$ is the score sequence of $T$ if and only if it satisfy these 2 conditions, but I can't see how these 2 conditions make the tournament strong
 A: I think that this argument is along the lines of the material that you’ve been studying.
Let’s say that a score sequence $\langle s_1,\ldots,s_n\rangle$ is a strong score sequence if $\sum_{i=1}^ks_i>\binom{k}2$ for $k=1,\ldots,n-1$. We want to show that a tournament is strong iff its score sequence is strong. The easier direction is to show that if a tournament is strong, so is its score sequence.
Suppose that $T$ is a tournament with score sequence $\langle s_1,\ldots,s_n\rangle$ that is not strong; then there is a $k<n$ such that $\sum_{i=1}^ks_i=\binom{k}2$. 


*

*Show that $T$ has no edge from $\{v_1,\ldots,v_k\}$ to $\{v_{k+1},\ldots,v_n\}$, and conclude that $T$ cannot be strong.


The other direction is harder. Suppose that $T$ has the strong score sequence $\langle s_1,\ldots,s_n\rangle$, corresponding to vertices $v_1,\ldots,v_n$; we want to show that $T$ is strong. Note that since the score sequence is strong, $s_1\ge 1$.
Let $C$ be a maximal cycle in $T$. (There must be one; why?) If $C$ is Hamiltonian, we’re done: $T$ is strong. Suppose, then, that $C$ is not Hamiltonian, and let $v$ be vertex not in $C$. 


*

*Suppose that there are vertices $x$ and $y$ in $C$ such that $xv$ and $vy$ are edges of $T$; show that in that case there are consecutive vertices $u$ and $w$ of $C$ (i.e., $uw$ is an edge of $C$) such that $uv$ and $vw$ are edges of $T$.  

*Conclude that $C$ is not maximal and hence that either every edge between $v$ and $C$ is from $v$ to $C$, or every edge between $v$ and $C$ is from $C$ to $v$.
Let $A$ be the set of vertices $v\notin C$ such that $vx$ is an edge of $T$ for each $x\in C$, and let $B$ be the set of vertices $v\notin C$ such that $xv$ is an edge of $T$ for each $x\in C$.


*

*Show that if $x\in A$ and $y\in B$, then $xy$ is an edge of $T$. (HINT: If not, $C$ isn’t maximal.)


Now we have the following schematic:
$$\begin{array}{ccc}
A&&\longrightarrow&&B\\
&\searrow&&\nearrow\\
&&C
\end{array}$$
Note that $A$ or $B$ may be empty. Suppose that $B\ne\varnothing$.


*

*Show that if $|B|=k$, then $B=\{v_1,\ldots,v_k\}$, the $k$ vertices at the beginning of $T$’s score sequence. (HINT: Compare the out-degree of each vertex of $T$ with $k$.)  

*Conclude further that $\sum_{i=1}^ks_i=\binom{k}2$, contradicting the assumption that $T$ has a strong score sequence.


This shows that $B=\varnothing$. 


*

*Now suppose that $A\ne\varnothing$, and use essentially the same argument to get a contradiction.


We’ve now shown that $C$ is Hamiltonian and hence that $T$ is strong.
A: HINTS (I will add details if desired, but you will learn more if you try to find them
by yourself).
Step 1: make a bipartite graph $G$ with bipartition $X,Y$.
The vertices of $X$ are the edges of $K_n$, the vertices of $Y$ are the vertices $v_1,\ldots,v_n$,
each with the desired multiplicity, i.e. there are $s_1$ copies of $v_1$, $s_2$ copies of $v_2$ etc.
An vertex $e$ of $X$ is made adjacent to all copies of both its endpoints.
Step 1a: show that $|X|=|Y|$.
Step 2: show that Hall's condition holds in $G$ (for $X$).
Step 3: use the perfect matching you find as a consequence of the previous steps to obtain
an orientation of $K_n$ with the desired score sequence.
Step 4: assume that the found orientation is not a strong orientation
and obtain a contradiction with the result that every graph has a strong component
without outarrows.
A: There's a much simpler answer:
Suppose we have $\sum_{i=1}^{k}s_i>\binom k 2$, for $1\leq k \leq n-1$. If the graph is not strongly connected, then its vertices can be decomposed into strong components, and one of these components has no outgoing edges. Name this component $S$ with size $t<n$. For any $v\in S$, we have $deg^+(v)<t$, and for any $v \notin S$ we have $deg^+(v)\geq t$. So the first $t$ vertices in score sequence are exactly the elements of $S$. Therefore we have $\sum_{i=1}^{t}s_i=\binom t 2$. This is a contradiction, and we can conclude that the tournament is strong.
Conversely, if the tournament is strong, but there exist a $k$ such that $k<n$ and $\sum_{i=1}^{k}s_i=\binom k 2$, then we name $S = \{v_1, . . ., v_k\}$, then no edge can go from $S$ to outside of $S$ (we have already $\binom n 2$ edges inside $S$). This also is a contradiction, so no such k exist, therefore we have $\sum_{i=1}^{k}s_i>\binom k 2$ for $1\leq k<n$. $\blacksquare$
