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

图论问题，急!!!~

反证法：
假设图G不连通
那么必然可以在G中取一对节点u和v且这两个节点不连通
设u和v所在连通块的节点数量分别为n1和n2
显然n1+n2<=n
u的度数>[n/2]-1,那么u所在的连通块就至少包含u和所有与u相连的节点，那么n1>[n/2]-1+1=[n/2]，即n1>=[n/2]+1
同理n2>=[n/2]+1
两个连通块的节点总数n1+n2>=2*[n/2]+2>2*[n/2]+1
n为奇数时，[n/2]=(n-1)/2,2*[n/2]+1=n，那么n1+n2>n
n为偶数时，[n/2]=n/2,2*[n/2]+1=n+1，那么n1+n2>n
无论n为奇数还是偶数，都有n1+n2>n，与n1+n2<=n矛盾

因此图G是个连通图

这是由一道数学竞赛题改编过来的。
第一种情况：存在三人相互不认识，很显然结论是成立的。

第二种情况：任意三人中至少有两人认识。（这种情况就是原题）
抽象成点，全部连接，若认识边染成红色，否则染成蓝色。
由假设，这个图中没有蓝色三角形。

分两种情况。1，若某个顶点发出的蓝边至少有四条（以四条为例），那么分析就可知道存在存在红色的完全图K4；

2，若任一顶点发出的蓝线至多三条，那么存在某个顶点A的发出了（至少）六条边，然后在考察这六个顶点，在运用拉姆塞定理（二染色的K6中存在同色三角形），知道这六个顶点中存在红色的三角形。这三点再加A就是完全认识的人了。

以上就是问题解答的核心部分，细枝末节你就自己添加吧。

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

---

平陆县19692376161： 简单连通图G 满足顶点数n>2k,k是最小度,求证G中存在一条长至少为2k的路 - ？
揣武薯蓣：[答案] 用到这几个概念: 1、设F是图G的一个子图,对于F中的任意顶点u和v,只要uv是G中的边,则uv一定是F中的边,此时称F... 此定理的证明见Gary.Chartrand的书《图论导引》 下面是对本题的证明. 证明:设P:x0,x1,...,xm是图G中最长的一条路(长为m...

平陆县19692376161： 设无向连通图G有n个顶点,证明G至少有(n - 1)条边. - ？
揣武薯蓣： 设连通图G有(n+1)个顶点,若每个顶点连出至少两条边,那么此时至少有n+1条边(任意图上所有顶点度数和等于边数的两倍),结论已经成立.否则,那么至少有一个顶点只连出一条边. 不妨设为A,由于去掉这条边AB后不影响其他点的...

平陆县19692376161： 求一条图论基础题？
揣武薯蓣： 因为p(G)=顶点数-连通分支数,而在连通图中,e=n-1(即连通分支数=顶点数-1)所以,代进去算得 p(G) = 1

平陆县19692376161： 问一道图论题: - ？
揣武薯蓣： 我对图论也不是很熟悉,我试一下吧.提供给你参考. 证明:首先,根据条件得到:边数为:(4*8+6*6+8)/2=38 假设G是平面图 根据欧拉定理知道,面数等于:38+2-15=25 根据假设,面的总长度是:38*2=76 所以,G的面有24个长度为3,1个长...

平陆县19692376161： 图论:设图有10个4度顶点,8个5度顶点,其余为7度顶点,求7度顶点的最大数量,使得G保持可平面性. - ？
揣武薯蓣： 由平面图的点线面公式(Euler 公式):(顶点数)n+(面数)f-(边数)m=2,d(v1)+d(v2)+d(vn)=2m,及2m≥3f,可得:2=n+f-m ≤n+2/3m-m =n-1/3m=n-1/3[40+7/2(n-18)] 化简得:n≤36,所以7度顶点的最大数量是18.

平陆县19692376161： 设G是无向简单图,有6个顶点,7条边,证明G的连通分支个数不超过2 - ？
揣武薯蓣： 用反证法证明: 假设有3个连通分支 那么只能以下三种情况: 1. 两个孤立结点,和4个结点7条边 显然这不是简单图 2. 一个孤立结点,和2结点和3结点的连通分支 2结点的连通分支最多1条边 3结点的连通分支最多3条边 显然不满足条件 3. 3个2结点图,最多只能有3条边 综上,G的连通分支个数不超过2

平陆县19692376161： 图论:证明若G为简单连通图,且G中任意一对不相邻顶点u和v满足:d(u)+d(v)>=n - 1,则G有Hanmilton路. - ？
揣武薯蓣： http://web.nuist.edu.cn/courses/lssx/longtime/part4/chapter15/15_02_03_01.htm 记得采纳啊

平陆县19692376161： 关于离散数学中图论的一个问题题目:具有6个顶点,12条边的连通简单平面图中,每个面都是由()条边围成?? 急需解决... - ？
揣武薯蓣：[答案] 每个面都是三角形,所以都是三条边组成

平陆县19692376161： 图论问题无向图G中恰好只有2个度数为奇数的顶点证明:这两个顶点间必定存在一条路 - ？
揣武薯蓣：[答案] 若不然,则这两个顶点将分别属于两个简单图,也即G中包含两个简单图,每个简单图都只有一个奇顶点,这显然是不可能的.