关于竞赛图中各种长度的路的一点注记

设T=(V,A)是竞赛图。以△~ 、△~-表示T的最大出次、最大入次。p=|V|是T的点数。令R={υ|d~ (υ)=△},S={υ|d(υ)=△} 定理设T是竞赛图,则总存在r∈R,s∈S从r到s有长度为l的路(l=2,3,…p-1)。证明不妨设T不是正则竞赛图,并且p≥5。于是△~ ≥p/2,△≥p/2。任取 r∈R,s∈S,则T中总存在长度≤2的路P,若(r,s)∈A, 记σ(r)={υ|(r,υ)∈A},I(s)={υ|(υ,s)∈A} 若σ(r)∩I(s)≠φ,则存在从r到s的长度为2的路。