定义：个点的有向图，若满足任意两点都有且仅有一条有向边，就称此有向图为竞赛图。

为什么竞赛图要专门分析呢？因为竞赛图有很多非常有趣的性质。

将竞赛图缩点之后，缩成的所有强连通分量按照出度从小到大排成的序列，一定满足第个强连通分量与所有的强连通分量都有一条的边。

证明：考虑归纳，我们加进来一个新的强连通分量，如果当前所有强连通分量都连向它，那么将它放在序列尾；如果它连向所有强连通分量，那么将它放在序列头；否则，所有它连向的强连通分量一定在连向它的强连通分量的后面（否则就有环，矛盾），那么将它放在对应的分界点处即可。

竞赛图的所有强连通分量都存在一条哈密顿回路。

证明：考虑归纳，仍然考虑当前强连通分量构成的序列（即性质一所述的那个序列），目前所有强连通分量都满足存在一条哈密顿回路。现在我们加入一个点，如果它自己构成一个单独的强连通分量，那么将它直接加入序列（类似性质一）；否则，我们找到最左边的它连向的那个强连通分量，再找到最右边的连向它的强连通分量，那么所有之间的及当前这个点构成了一个新的强连通分量，那么显然这个新强连通分量也存在一条哈密顿回路（考虑从当前点走到最左边强连通分量某个点开始每次先把其内部的点走一遍再走到下一个强连通分量的某个点，一直走到最右边强连通分量，然后走到当前点本身）。

竞赛图存在一条哈密顿路径。

证明：因为每个强连通分量都有一条哈密顿回路，直接沿哈密顿回路走完每个强连通分量的所有点然后再走向下个强连通分量即可。

竞赛图里，任意大小为的强连通分量中，大小为的环均存在。

证明：首先，成立，那么时，我们只需证明存在大小为的环（即存在大小为的强强连通分量）即可。

考虑我们从强连通分量中提出一个点，如果剩下的只有一个强连通分量，那么大小为的环已经出现。

否则，剩下的强连通分量一定构成一个性质一所述的序列，根据性质三，这个序列存在一条哈密顿路径，我们按照原来构造的路径上某个联通分量的最后一个点不走，直接跳到下一个联通分量，这样一条新的路径加上我们提出来的这个点，就构成了一个大小为的环。