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

来源：学生作业帮编辑：大师作文网作业帮分类：数学作业时间：2024/11/18 06:49:54

用到这几个概念：
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. 证毕.

离散数学证明题:设连通图G有k个奇数度的结点,证明在图G中至少要添加k/2条边才能使其成为欧拉图．设G是有n个结点n条边的简单连通图,且G中存在度数为3的结点,证明G中至少有一个度数为1的结点连通无向图G有k个奇顶点,如果把G变成无奇顶点的图,则在G中至少需要加___ ___条边若图G的最小度数大于等于K,则G有K长路图论：证明若G为简单连通图,且G中任意一对不相邻顶点u和v满足d(u)+d(v)>=n-1,则G有Hamilton路. 已知三角形abc中,三边长为k平方+k+1,k平方—1,2k+1,求证三角形的最大角的度数是? 求最大的正整数k使得存在正整数n满足2^k整除3^n+1 三角形ABC中,三边长分别为 k^2+k+1,k^2-1,2k+1 求证：三角形最大内角度数为120度求证：lim1^k+2^k+3^k+4^k+.n^k/n^(k+1)=1/k+1 简单图G有n个结点,e条边,设e>(n-1)(n-2)/2,证明G是连通的证明!图论!证明：图G是连通的平面图,其点数为n,边数为e,则n-e+f=2 已知k∈N,求证:k²+k²(k+1)²+(k+1)是一个完全平方数