トーナメント

各辺 $u\to v$ は $u$ の得点にだけ 1 を加えるので、得点の和は辺の本数 $\binom n2$ に等しい。$S$ の 2 頂点を結ぶ $\binom{|S|}2$ 本の辺は、それぞれ $S$ のどちらかの頂点の得点に 1 を加えるので、$S$ の頂点の得点の和はそれ以上である。$\square$

頂点の個数 $n$ についての帰納法で示す。$n\le1$ なら明らかである。$n\ge2$ とし、頂点 $x$ を 1 つ選ぶ。$x$ を除いたトーナメントは、帰納法の仮定により有向 Hamilton 道 $v_1\to v_2\to\dots\to v_{n-1}$ をもつ。$x$ をこの道に差し込む。

• $x\to v_1$ なら、$x\to v_1\to\dots\to v_{n-1}$ が求める道である。
• $v_{n-1}\to x$ なら、$v_1\to\dots\to v_{n-1}\to x$ が求める道である。
• どちらでもなければ $v_1\to x$ かつ $x\to v_{n-1}$ である。$v_i\to x$ となる $i$ のうち最大のものを $i$ とすると $i\le n-2$ で、$i$ の最大性から $x\to v_{i+1}$ である。よって $v_1\to\dots\to v_i\to x\to v_{i+1}\to\dots\to v_{n-1}$ が求める道である。$\square$

1 ⇒ 2：3-閉路 $u\to v\to w\to u$ があれば、推移性から $u\to w$ となり、$w\to u$ と両立しない。
2 ⇒ 3：トーナメントにはループも長さ $2$ の有向閉路（$u\to v$ と $v\to u$）もないので、有向閉路の長さは $3$ 以上である。有向閉路があるとして、最も短いもの $v_0\to v_1\to\dots\to v_{\ell-1}\to v_0$ をとる。2 により $\ell\ge4$ である。$v_2\to v_0$ なら $v_0\to v_1\to v_2\to v_0$ が 3-閉路になる。$v_0\to v_2$ なら $v_0\to v_2\to\dots\to v_{\ell-1}\to v_0$ が長さ $\ell-1$ の有向閉路になり、最短性に反する。
3 ⇒ 4：有向グラフ の記事の定理「非巡回性と位相的順序」により、どの辺 $v_i\to v_j$ でも $i< j$ となる並べ方 $v_1,\dots,v_n$ がある。$i< j$ のとき $v_i$ と $v_j$ を結ぶ辺の向きは $v_i\to v_j$ か $v_j\to v_i$ だが、後者なら $j< i$ となるので、$v_i\to v_j$ である。
4 ⇒ 5：$v_i$ は $v_{i+1},\dots,v_n$ のちょうど $n-i$ 頂点に勝つので $s(v_i)=n-i$ であり、得点は相異なる。
5 ⇒ 1：$n$ についての帰納法で示す。$n\le2$ なら推移性の仮定に当てはまる 3 頂点がないので成り立つ。$0\le s(v)\le n-1$ の $n$ 個の相異なる整数なので、得点は $0,1,\dots,n-1$ をちょうど 1 回ずつとる。得点 $n-1$ の頂点 $t$ はほかの全員に勝つ。$t$ を除いたトーナメント $T'$ では、どの頂点も $t$ に負けていたので得点は変わらず、相異なる。帰納法の仮定により $T'$ は推移的である。$u\to v$、$v\to w$ とする。$t$ に勝つ頂点はないので $v,w\ne t$ である。$u=t$ なら $t\to w$。$u\ne t$ なら $u,v,w$ は $T'$ の頂点で、$u\to w$ である。これは 5 の後半も含む。
最後の主張：4 の並べ方で、$v_i\to v_j$ は $i< j$ のときに限るので、有向道に沿って添字は増える。すべての頂点を通る有向道は、添字が $1$ ずつ増えるもの $v_1\to\dots\to v_n$ しかない。$\square$

頂点の 3 点集合 $\{a,b,c\}$ の間の 3 本の辺は、ex-tn-small の 1 により、3-閉路をなすか、ある 1 頂点が他の 2 頂点に勝つかのちょうど一方である。後者の 3 点集合を、他の 2 頂点に勝つ頂点 $v$ ごとに数えると、$v$ が勝つ $s(v)$ 頂点から 2 つ選ぶ選び方の数 $\binom{s(v)}2$ だけある。よって 3-閉路をなさない 3 点集合は $\sum_v\binom{s(v)}2$ 個で、等式を得る。
不等式：$\sum_v\binom{s(v)}2=\frac12\sum_vs(v)^2-\frac12\binom n2$（prop-tn-score-sum）なので、$\sum_vs(v)^2$ の最小値を求めればよい。和が $\binom n2$ の非負整数 $s_1,\dots,s_n$ で、$s_a\ge s_b+2$ となる組があれば、$s_a,s_b$ を $s_a-1,s_b+1$ に替えると平方和は $2(s_a-s_b)-2>0$ だけ減る。よって平方和が最小になるのは、どの 2 つの差も $1$ 以下のときであり、これは $n$ が奇数なら全員が $\frac{n-1}2$、$n$ が偶数なら半数が $\frac n2$、残りの半数が $\frac n2-1$ のときである。このとき
$$ \binom n3-n\binom{(n-1)/2}{2}=\frac{n(n-1)(n+1)}{24},\qquad \binom n3-\frac n2\Bigl(\binom{n/2}2+\binom{n/2-1}2\Bigr)=\frac{n(n-2)(n+2)}{24} $$
となり、上の上界を得る。$n$ が奇数なら等号は全員の得点が等しいとき、すなわち正則トーナメントのときに限り、ex-tn-regular がその例である。$n$ が偶数なら、$n+1$ 頂点の正則トーナメントから 1 頂点 $x$ を除くと、$x$ に負けていた $\frac n2$ 頂点の得点は $\frac n2$ のまま、$x$ に勝っていた $\frac n2$ 頂点の得点は $\frac n2-1$ になり、等号が成り立つ。$\square$

ある頂点 $w\ne v$ についてどちらも成り立たないとする。$v\to w$ でないので $w\to v$ である。$v$ が勝つ頂点 $u$ について $u\to w$ でないので $w\to u$ である。よって $w$ は $v$ と、$v$ が勝つ $s(v)$ 頂点のすべてに勝ち、$s(w)\ge s(v)+1$ となる。これは $s(v)$ の最大性に反する。$\square$

3-閉路． $u$ が勝つ頂点の集合を $S$、$u$ に勝つ頂点の集合を $R$ とすると、$V=\{u\}\cup S\cup R$ で、上の段落により $S,R$ はどちらも空でない。$S$ のある頂点から $R$ のある頂点への辺がなければ、$u$ から出る辺の行き先は $S$、$S$ から出る辺の行き先は $S$ の中だけになる（$S$ の頂点は $u$ に負けている）。すると $u$ から $R$ へ行けず、強連結性に反する。よって $s\to r$（$s\in S$、$r\in R$）となる辺があり、$u\to s\to r\to u$ が 3-閉路である。
$k$ から $k+1$ へ． $3\le k< n$ とし、$u$ を通る $k$-閉路 $C:v_0\to v_1\to\dots\to v_{k-1}\to v_0$（$v_0=u$）があるとする。$C$ の外の頂点の集合を $W$ とすると $W\ne\emptyset$ である。
$C$ の頂点の中に $x$ に勝つものと $x$ に負けるものがともにあるような $x\in W$ があるとき：閉路を一周すると、$x$ に勝つ頂点から $x$ に負ける頂点へ移る箇所があるので、$v_i\to x$ かつ $x\to v_{i+1}$ となる $i$ がある（添字は $k$ を法とする）。$C$ の辺 $v_i\to v_{i+1}$ を $v_i\to x\to v_{i+1}$ に替えれば、$u$ を通る $(k+1)$-閉路が得られる。
そうでないとき：$W$ の各頂点は、$C$ の全頂点に負けるか（その全体を $W^-$ とする）、$C$ の全頂点に勝つ（その全体を $W^+$ とする）。$C$ の頂点から出る辺の行き先は $C$ か $W^-$ であり、$W^-$ の頂点から出る辺の行き先は $W^-$ か $W^+$ である。$W^+=\emptyset$ なら $W^-\ne\emptyset$ の頂点から $C$ へ戻れず、$W^-=\emptyset$ なら $C$ から $W^+\ne\emptyset$ の頂点へ行けないので、強連結性から $W^-$ と $W^+$ はどちらも空でない。$W^-$ から $W^+$ への辺がなければ、$u$ から行ける頂点は $C$ と $W^-$ の頂点に限られ、$W^+$ の頂点へ行けない。よって $s\to r$（$s\in W^-$、$r\in W^+$）となる辺がある。$k\ge3$ なので $v_2\ne v_0$ であり、
$$ v_0\to s\to r\to v_2\to v_3\to\dots\to v_{k-1}\to v_0 $$
は $u=v_0$ を通る $(k+1)$-閉路である（$v_0\to s$ は $C$ が $W^-$ に勝つこと、$r\to v_2$ は $W^+$ が $C$ に勝つことによる）。
$k$ についての帰納法により、$u$ は長さ $3,\dots,n$ のすべての閉路に含まれる。長さ $n$ の閉路は有向 Hamilton 閉路である。$\square$

相異なる強連結成分 $C,C'$ の間に、$C$ から $C'$ への辺と $C'$ から $C$ への辺がともにあれば、$C$ と $C'$ の頂点は互いに到達可能になり、同じ強連結成分に属してしまう。よって $C$ と $C'$ の間の辺はすべて同じ向きであり、どの 2 頂点も辺で結ばれるので、その向きの辺が少なくとも 1 本ある。したがって 有向グラフ の記事でいう凝縮 $T/{\sim}$ はトーナメントであり、同記事の命題「凝縮は非巡回である」により有向閉路をもたない。thm-tn-transitive の 3 ⇒ 4 により、成分を $C_1,\dots,C_r$ と並べて、$i< j$ なら凝縮で $C_i\to C_j$ となるようにできる。最初に述べたことから、このとき $C_i$ と $C_j$ の間の辺はすべて $C_i$ から $C_j$ へ向かう。$\square$

推移的なら、thm-tn-transitive の最後の主張により有向 Hamilton 道はただ 1 つである。推移的でないとする。強連結成分 $C_1,\dots,C_r$ を prop-tn-components のように並べる。どの成分も 1 頂点なら、成分の頂点をこの順に並べると $i< j$ でつねに前の頂点が後ろの頂点に勝つので、thm-tn-transitive の 4 ⇒ 1 により $T$ は推移的になり、仮定に反する。よってある $C_i$ は 1 頂点でなく、頂点が 2 個のトーナメントは強連結でないので $m:=|C_i|\ge3$ である。thm-tn-moon により $C_i$ は有向 Hamilton 閉路 $w_1\to w_2\to\dots\to w_m\to w_1$ をもつ。$s=1,\dots,m$ について、この閉路から辺 $w_{s-1}\to w_s$（$w_0:=w_m$）を除くと、$w_s$ から始まる $C_i$ の有向 Hamilton 道が得られ、始点が異なるのでこれらは相異なる。ほかの成分 $C_j$ の有向 Hamilton 道を 1 つずつ固定し、上の段落のように $C_1,\dots,C_r$ の順につなぐと、$T$ の有向 Hamilton 道が $m\ge3$ 本得られ、$C_i$ の部分が異なるので相異なる。$\square$

必要性は prop-tn-score-sum を、得点の小さい $k$ 頂点の集合に使えばよい。
十分性を示す。頂点を $1,\dots,n$ とし、次の二部グラフ $B$ を作る。一方の側 $X$ は 2 頂点の組（試合）$\{i,j\}$（$i\ne j$）の全体で $\binom n2$ 個、他方の側 $Y$ は組 $(i,r)$（$1\le i\le n$、$1\le r\le s_i$）の全体で、$\sum s_i=\binom n2$ 個である。試合 $\{i,j\}$ を、$(i,r)$ と $(j,r)$ の形のすべての元と辺で結ぶ。$(i,r)$ は「$i$ の $r$ 個目の勝ち」を表す。
$X$ の部分集合 $Q$ について、$Q$ の試合に現れる頂点の集合を $U$ とし $w:=|U|$ とする。$Q$ の試合はどれも $U$ の 2 頂点の組なので $|Q|\le\binom w2$ である。一方 $Q$ の $B$ での隣接頂点の全体は $\{(i,r)\mid i\in U\}$ で、その個数 $\sum_{i\in U}s_i$ は、$s$ の小さい方から $w$ 個の和以上なので、仮定により $\binom w2$ 以上である。よって $Q$ の隣接頂点は $|Q|$ 個以上あり、Hallの結婚定理 の記事の系「二部グラフの形」により、$X$ のすべての頂点を端点とするマッチング $M$ がある。$|X|=|Y|$ なので $M$ は $Y$ のすべての頂点も端点とする。
試合 $\{i,j\}$ が $M$ で $(i,r)$ と結ばれるなら $i\to j$、$(j,r)$ と結ばれるなら $j\to i$ と定める。これはトーナメントで、$i$ が勝つ試合は $M$ で $(i,1),\dots,(i,s_i)$ と結ばれる試合のちょうど $s_i$ 個なので、$i$ の得点は $s_i$ である。$\square$