Problem 8 Lemma (Existence of a Complete Sequence)

Lemma: Let $W$ be a tournament directed graph on $2n+1$ nodes where every node projects an arrow to exactly $n$ other nodes. Then there exists on $W$ a sequence $p_1→p_2→...→p_{2n+1}→p_{2n+2}=p_1$ such that $p_i \neq p_j$ for all $i \neq j$ for $1 \leq i,j \leq 2n+1$.

Proof: The results in my attached exercise on Vandermonde determinants imply that there must exist some sequence $p_1→...→p_m→p_{m+1}=p_1$ involving distinct nodes, so let us observe such a sequence where $m$ is assumed to be maximal of all possible sequences of that form. Assume $m \neq 2n+1$. Denote by $P$ the set of nodes in the sequence and set $Q=W \setminus P$. For all $w \in W$ denote by $\text{img }w$ the set of nodes toward which $w$ projects an arrow.

First, a sublemma: Let $q \in Q$ such that $p_i→q→p_j$ for some $i,j$. Then it follows that we must have some $k$ for $p_k→q→p_{k+1}$ (else all the nodes could be shown to point toward $q$ iff $p_i$ does, a contradiction for $p_j$). Then $p_1→...→p_k→q→p_{k+1}→...→p_m→p_{m+1}=p_1$ is a strictly larger sequence, a contradiction by the maximality of $m$. Therefore for all $q \in Q$ we have $P \subseteq \text{img }q$ or $P \cap \text{img }q = \emptyset$.

Assume $m > n$. Then since $1 \leq |Q| \leq n$ we may choose some $q \in Q$, where necessarily $)\text{img }q) \cap P \neq \emptyset$, therefore $P \subseteq \text{img }q$, but now $n < |P| \leq |\text{img }q| = n$, a contradiction.

Therefore $m \leq n$. Then by the sublemma $p_i→q \iff p_1→q$ for $q \in Q$. Since $|P \setminus \{p_1\}| < n$ we must have $p_1 → q$ for some $q \in Q$. Now $(\text{img }p_1) \setminus P = (\text{img }P) \setminus P$ and since $|Q| \geq n+1$ we observe the nonempty $S = (\text{img }P) \setminus P$ and $T = W \setminus (S \cup P)$. Note $P$, $S$, and $T$ partition $W$. Now, $|S| \leq n$ and $(\text{img }S) \cap P = \emptyset$, hence for all $s \in S$ there exists $t \in T$ such that $s→t$. Choose such $s$ and $t$ and observe that $p_1→s→t→p_2→...→p_m→p_{m+1}=p_1$ is a strictly larger sequence once more.$\square$

The motivation behind this lemma was to justify the privilege of imagining every such tournament directed graph as a polygon of nodes, with each successive vertex pointing toward the next. However, the utility of this was never realized.