证明:若G是简单图,且δ≥2,则G包含长至少为δ+1的圈.
问题描述:
证明:若G是简单图,且δ≥2,则G包含长至少为δ+1的圈.
答
兄弟你是不是也是选图论的 用扩大路径法可以证明
《离散数学》第282页里有
答
证明 设G中最长的基本路为
V0,V1,V2,…,Vk
显然与V0邻结的点均在该基本路(路上结点均不同)上,否则它和最长的基本路矛盾,设Vl是该基本路上与V0邻结且足码最大的结点(或在该基本路上距V0最远的邻结结点),则必有l≥δ,于是
V0,V1,V2,…,Vl,V0
就是长至少为δ+1的圈.