题目

证明：若G是简单图,且δ≥2,则G包含长至少为δ+1的圈.

提问时间：2020-12-05

答案

证明 设G中最长的基本路为
V0,V1,V2,…,Vk
显然与V0邻结的点均在该基本路（路上结点均不同）上,否则它和最长的基本路矛盾,设Vl是该基本路上与V0邻结且足码最大的结点（或在该基本路上距V0最远的邻结结点）,则必有l≥δ,于是
V0,V1,V2,…,Vl,V0
就是长至少为δ+1的圈.