3.设G为n阶有向简单图,每个点的入度大于等于3,证明G中存在长度大于等于4的圈.

分类: 作业答案 • 2022-07-28 21:42:54

问题描述：

答

设AB为G的一条最长路径
设C、D、E为A的3个前驱结点,
则C一定在AB上(否则路径CAB比最长路径AB还长)
同理D、E也在AB上,
不失一般性,存在路径 A->C->D->E->B （E和B也可能是同一点,不过不影响结论）
故存在长度至少为4的环 A->C->D->E->A