设 D D D是竞赛图且 k = max { δ + , δ − } > 0 k=\max{\left \{δ^+,δ^-\right \} }>0 k=max{δ+,δ−}>0,其中 δ + δ^+ δ+和 δ − δ^- δ−分别表示 D D D的最小出度和入度。证明: D D D含长至少为 2 k + 1 2k+1 2k+1的有向圈。
证:
一、定义与假设
设 D D D是一个竞赛图， k = max { δ + , δ − } k=\max\{ \delta^+, \delta^-\} k=max{δ+,δ−}，其中 δ + \delta^+ δ+和 δ − \delta^- δ−分别表示 D D D的最小出度和入度。
二、初始选择
从 D D D中选择任意顶点 v 0 v_0 v0。
三、路径构造
1.构造一个有向路径 v 0 , v 1 , v 2 , … , v m v_0,v_1,v_2,\ldots, v_m v0,v1,v2,…,vm，其中 v i v_i vi是第 i i i个顶点，且 v i → v i + 1 v_i \rightarrow v_{i+1} vi→vi+1。
2.路径在顶点 v m v_m vm停止，表示 v m v_m vm的所有出邻接点和入邻接点都已经在路径中。
四、路径延长
1.由于 δ + ≥ k \delta^+\geq k δ+≥k和 δ − ≥ k \delta^-\geq k δ−≥k,每个顶点 v i v_i vi至少有 k k k个出邻接点和 k k k个入邻接点。
2.如果路径停止在 v m v_m vm，那么 v m v_m vm的所有出邻接点和入邻接点都在路径 v 0 , v 1 , … , v m − 1 v_0,v_1,\ldots,v_{m-1} v0,v1,…,vm−1中。
3.因此，路径的长度 m m m至少需要 2 k 2k 2k才能覆盖所有出邻接点和入邻接点。
五、寻找有向圈
1.因为 v m v_m vm的所有出邻接点和入邻接点都在路径中，而 v m v_m vm有至少 k k k个出邻接点和 k k k个入邻接点，路径至少有 2 k 2k 2k个顶点。
2.设 v m v_m vm的出邻接点为 { v i 1 , v i 2 , … , v i k } \{v_{i_1}, v_{i_2}, \ldots,v{i_k}\} {vi1,vi2,…,vik}和入邻接点为 { v j 1 , v j 2 , … , v j k } \{v_{j_1},v{j_2},\ldots,v{j_k}\} {vj1,vj2,…,vjk}，其中 0 ≤ i 1 , i 2 , … , j k < m 0 \leq i_1,i_2,\ldots,j_k<m 0≤i1,i2,…,jk<m。
六、有向圈的长度
1.由于 v m v_m vm的出邻接点和入邻接点都在路径中，必定存在一个顶点 v i v_i vi使得 v i → v m v_i\rightarrow v_m vi→vm或 v m → v i v_m \rightarrow v_i vm→vi。
2.形成的有向圈从 v i v_i vi开始，经过 v i + 1 , v i + 2 , … , v m v_{i+1},v_{i+2},\ldots,v_m vi+1,vi+2,…,vm，再回到 v i v_i vi。
3.由于路径长度至少为 2 k 2k 2k，且有向圈包含路径中的顶点，圈的长度至少为 2 k + 1 2k+1 2k+1。
七、结论
证明了竞赛图 D D D包含一个长度至少为 2 k + 1 2k+1 2k+1的有向圈。
