性质

性质一：

竞赛图的强连通分量构成一个链状结构（任意两\(SCC\)间都有边）

性质二：

一个竞赛图如果是强连通的，那么必然存在一条哈密顿回路，并且可以在 \(O(V^2)\) 的时间内找到

证明：数学归纳法
只有一个点时肯定成立
拆掉多的那个点，由于强连通，这个点必然能把剩下的哈密顿路径接起来

推论1：翻转不在哈密顿路径上的边不会影响原竞赛图强连通分量个数
推论2：翻转哈密顿路径上的边，增加的强连通分量个数等于删掉这条边后，形成的哈密顿路径上没被反向边覆盖的边数

性质三

一个竞赛图是强连通图等价于将出度序列排序，不存在长度为 \(i(1 ≤ i < M)\) 的前缀，其和为 \(i·(i−1)\)

证明:由性质一推得

性质四：

当 \(n\ge4\) 时，\(n\) 个点的强连通竞赛图一定有一个 \(n-1\) 个点的导出子图，满足他也是强连通竞赛图

证明:根据性质一简单分讨删掉一个点的情况可得

性质五：

当 \(n>6\) 时，\(n\) 个点的竞赛图可以通过至多一次翻转连接某个点的所有边，使得竞赛图强连通

证明：
情况1：存在一个大小 \(≥ 4\) 的强连通分量。则由性质二，我们可以找到一个点 \(t\)，满足去掉 \(t\) 后这个强连通分量仍然强连通。又因为 \(t\) 到这个强连通分量中所有点的边方向一定不完全相同，所以我们对 \(t\) 进行一次翻转操作后，这个强连通分量仍然是强连通的。而在操作后，可以发现，这个强连通分量现在可以到达所有强连通分量，也可以从所有强连通分量到达，于是整个图强连通。
情况2：存在至少三个强连通分量，在中间的强连通分量中任意取一个点进行操作。操作后每个点都可以先走到最后一个强连通分量，然后通过中间这个点走到第一个强连通分量，进而到达所有点。

如果上面两个条件都不满足，即每个强连通分量都 \(≤ 3\)，且只有两
个强连通分量，于是总点数 \(≤ 6\) 时不合法。

性质六

竞赛图如果有环，那么一定有三元环

证明：手模可得

大部分解法

分析性质，分析性质，分析性质