Question

简单连通图G 满足顶点数n>2k,k是最小度,求证G中存在一条长至少为2k的路

Answer 1

用到这几个概念：
1、设F是图G的一个子图,对于F中的任意顶点u和v,只要uv是G中的边,则uv一定是F中的边,此时称F为G的一个诱导子图.
2、若S是图G的一个非空顶点集合,则由S诱导的G的子图就是以S为顶点集的诱导子图.
3、除第一个和最后一个顶点外,没有顶点重复的回路(circuit)称为圈(cycle).k圈是一个长度为k的圈,记作Ck其中k是下标(k≥3).
4、一个含图G的每个顶点的圈称为是G的一个Hamilton圈.一个含有Hamilton圈的图称为是一个Hamilton图(或称此图是Hamilton的).
要用到下述定理：
Th.设u和v是一个n阶图G的两个不邻接的顶点,并且degu+degv≥n.则G+uv是Hamilton的当且仅当G是Hamilton的.
此定理的证明见Gary.Chartrand的书《图论导引》
下面是对本题的证明.
证明：设P:x0,x1,...,xm是图G中最长的一条路(长为m),记由{x0,...,xm}诱导的G的子图为H.由P是G中最长路知,与x0以及xm相邻的点都在路P上(否则与P是G中最长路矛盾),因此由诱导子图定义知,在H中x0(或xm)的度数与在G中x0(或xm)的度数是一样的,不妨就将其简单记作deg(x0)及deg(xm). 我们采用反证法,假设m＜2k.显然n＞2k≥2,首先m＞0(否则G不连通)；若m=1,由G的顶点数n＞2知V(G)-{x0,x1}非空,由G连通知,存在一点y∈V(G)-{x0,x1}以及xi∈{x0,x1}使得yxi∈E(G),则y,x0,x1组成长为2的路,与x0x1是G中最长路矛盾,因此m＞1.从而x0与xm不相邻.又deg(x0)+deg(xm)≥2k≥m+1(由假设m＜2k知),而且H+x0xm包含有圈C(m+1)(m+1是下标):x0,x1,...,xm,x0.故H+x0xm是Hamilton的,由上面的定理知,H是Hamilton的.故H包含一个圈C(m+1).由于n＞2k≥m+1,因此V(G)-{x0,...,xm}非空,由G连通知,存在一点y∈V(G)-{x0,...,xm}以及xi∈{x1,...x(m-1)}使得yxi∈E(G).因此G中包含这样一个图形：一个圈C(m+1)以及圈外一点y与C(m+1)中的点xi相邻接,这样就找到G中一条长为m+1的路(在纸上画画图便知道了),与P:x0,...,xm是G中最长路矛盾.故m≥2k. 证毕.