证明竞赛图至少有一个长度不小于2k+1的有向圈

设是竞赛图且,其中和分别表示的最小出度和入度。证明: 含长至少为的有向圈。

证:

一、定义与假设

设是一个竞赛图，，其中 和 分别表示的最小出度和入度。

二、初始选择

从中选择任意顶点。

三、路径构造

1.构造一个有向路径，其中是第个顶点，且。

2.路径在顶点 停止，表示的所有出邻接点和入邻接点都已经在路径中。

四、路径延长

1.由于 和 ,每个顶点至少有个出邻接点和个入邻接点。

2.如果路径停止在，那么的所有出邻接点和入邻接点都在路径中。

3.因此，路径的长度至少需要才能覆盖所有出邻接点和入邻接点。

五、寻找有向圈

1.因为的所有出邻接点和入邻接点都在路径中，而有至少个出邻接点和个入邻接点，路径至少有个顶点。

2.设 的出邻接点为和入邻接点为，其中。

六、有向圈的长度

1.由于的出邻接点和入邻接点都在路径中，必定存在一个顶点使得或。

2.形成的有向圈从开始，经过，再回到。

3.由于路径长度至少为，且有向圈包含路径中的顶点，圈的长度至少为。

七、结论

证明了竞赛图包含一个长度至少为的有向圈。