设
是竞赛图且
,其中
和
分别表示的最小出度和入度。证明: 含长至少为
的有向圈。
证:
一、定义与假设
设是一个竞赛图，
，其中 
和 
分别表示的最小出度和入度。
二、初始选择
从中选择任意顶点
。
三、路径构造
1.构造一个有向路径
，其中
是第
个顶点，且
。
2.路径在顶点 
停止，表示的所有出邻接点和入邻接点都已经在路径中。
四、路径延长
1.由于 
和 
,每个顶点至少有
个出邻接点和个入邻接点。
2.如果路径停止在，那么的所有出邻接点和入邻接点都在路径
中。
3.因此，路径的长度
至少需要
才能覆盖所有出邻接点和入邻接点。
五、寻找有向圈
1.因为的所有出邻接点和入邻接点都在路径中，而有至少个出邻接点和个入邻接点，路径至少有个顶点。
2.设 的出邻接点为
和入邻接点为
，其中
。
六、有向圈的长度
1.由于的出邻接点和入邻接点都在路径中，必定存在一个顶点使得
或
。
2.形成的有向圈从开始，经过
，再回到。
3.由于路径长度至少为，且有向圈包含路径中的顶点，圈的长度至少为。
七、结论
证明了竞赛图包含一个长度至少为的有向圈。
