===== 竞赛图的性质 =====

竞赛图是指任意两点间恰有一条有向边的有向图。简记 $u\to v$ 表示 $u$ 到 $v$ 存在一条有向边。

==== 性质 1 ====

任意竞赛图都存在一条哈密顿通路。

**证明**：$n=1$ 时显然。$n\ge2$ 时，考虑归纳法，设 $n-1$ 时的哈密顿通路为 $p_{1},p_{2},\cdots,p_{n-1}$。新加入 $n$ 时，若存在 $i$ 使得 $p_{i}\to n$ 且 $n\to p_{i+1}$，那么将 $n$ 放在 $p_{i}$ 之后即可。

否则，假如所有点都向 $n$ 有边，将 $n$ 放在 $p_{n-1}$ 后即可，反之亦然。

否则，必然有 $p_{n-1}\to n$，$n\to p_{1}$，那么 $p_{2},\cdots,p_{n-1},n,p_{1}$ 满足要求。

==== 性质 2 ====

任意强连通的竞赛图都存在一条哈密顿回路。

**证明**：$n\le3$ 时显然。$n\ge4$ 时，考虑归纳法，设 $n-1$ 时的哈密顿回路为 $p_{1},p_{2},\cdots,p_{n-1}$。新加入 $n$ 时，若存在 $i$ 使得 $p_{i}\to n$ 且 $n\to p_{i+1}$，那么将 $n$ 放在 $p_{i}$ 之后即可。

否则，由于图强连通，不可能所有点都向 $n$ 有边或 $n$ 向所有点有边。因此必然有 $p_{n-1}\to n$，$n\to p_{1}$，那么 $p_{2},\cdots,p_{n-1},n,p_{1}$ 满足要求。

==== 性质 3 ====

任意竞赛图强连通分量缩点之后，所有边必然由拓扑序小的点指向拓扑序大的点。

**证明**：缩点之后的图存在一个哈密顿通路，这条通路显然是按拓扑序排序的。假如存在一条由拓扑序大的点指向拓扑序小的点的边，会产生一个环，与该图是 DAG 矛盾。

==== 性质 4 ====

若某个竞赛图存在一个长度为 $n(n\ge4)$ 的环，那么存在一个长度 $n-1$ 的环。

**证明**：设环为 $p_{1},\cdots,p_{n}$，若存在 $p_{i}\to p_{i+2}$，显然将 $p_{i+1}$ 删去即可。否则，我们证明将 $p_{1}$ 删除后，剩下的点仍然强连通。$p_{2}$ 可以走到所有的点，$p_{3}\to p_{4}\to p_{2}$，因此 $p_{3}$ 也可以走到所有的点。对于 $i\ge 4$，$p_{i}\to p_{i-2}$，因 此 $p_{i}$ 同样可以走到所有的点。由于它强连通，因此存在一个长度为 $n-1$ 的环。

===== 兰道定理 =====

定义一个竞赛图的比分序列 $s_{1},\cdots,s_{n}$ 为将图中所有点出度从小到大排序后的序列。$\{s\}$ 是一个度数序列当且仅当 $\forall 1\le i<n,\sum_{j=1}^{i}s_{j}\ge{i\choose2}$，$\sum_{i=1}^{n}s_{i}={n\choose2}$。

**证明**：我们从一个基础的竞赛图开始归纳地构造。不妨设已有一个竞赛图 $T$，其比分序列 $\{t\}$ 满足 $\forall 1\le i\le n,\sum_{j=1}^{i}t_{i}\le\sum_{j=1}^{i}s_{i}$。注意到 $\forall 1\le j<i\le n,i\to j$ 永远满足该条件。

设 $u$ 为第一个满足 $t_{u}<s_{u}$ 的 $u$，$v$ 为最后一个满足 $t_{v}=t_{u}$ 的 $v$，$w$ 为第一个满足 $t_{w}>s_{w}$ 的 $w$（如果不存在的话，$\sum_{i=1}^{n}s_{i}>\sum_{i=1}^{n}t_{i}$，矛盾）。如图所示：

$$
\begin{matrix}
&s_{1}&\cdots&s_{u-1}&s_{u}&\cdots&s_{v}&s_{v+1}&\cdots&s_{w-1}&s_{w}&s_{w+1}&\cdots&s_{n}\\
&\parallel&\vdots&\parallel&\lor&\vdots&\lor&\parallel\lor&\vdots&\parallel\lor&\land&?&\vdots&?\\
&t_{1}&\cdots&t_{u-1}&t_{u}&\cdots&t_{v}&t_{v+1}&\cdots&t_{w-1}&t_{w}&t_{w+1}&\cdots&t_{n}\\
\end{matrix}
$$

可见，$t_{w}>s_{w}\ge s_{v}>t_{v}$，即 $t_{w}\ge t_{v}+2$，$|\text{out}(w)|+|\text{in}(v)|=n-1+|\text{out}(w)|-|\text{out}(v)|\ge n+1$。考虑到可能存在 $w\to v$，从集合中删去 $w,v$ 后，有 $|\text{out}(w)|+|\text{in}(v)|\ge n-1$。根据抽屉原理，至少存在一个点 $a\neq w,v$， $w\to a\to v$。

考虑将 $w\to a\to v$ 反转为 $v\to a\to w$，会导致 $t_{w}=t_{w}-1,t_{v}=t_{v}+1$。注意到 $t_{v}<t_{v+1}$，$t_{w-1}<t_{w}$，因此这不会改变 $t$ 的排序，容易发现它仍然满足 $\forall 1\le i\le n,\sum_{j=1}^{i}t_{i}\le\sum_{j=1}^{i}s_{i}$。同时注意到，这会导致 $\{t\}$ 的字典序 变大，因而该过程不会永远继续下去，最终可以得到 $t=s$。