Light 发表于 2012-7-4 19:53:43

请教图论题，求大神帮助！

本帖最后由 Light 于 2012-7-4 20:22 编辑

证明：一个有2n个顶点和n^2+1个边的图至少有一个K3子图？

然后证明一个有2n个顶点和n^2+1个边的图至少有n个K3子图

谢谢！

K3是complete graph，就是3个点，有3条线使他们两两相连
其实貌似如果能看懂，不用非得学过图论

洛阳狼王 发表于 2012-7-4 20:05:29

这个题我真看不懂。                                          

Light 发表于 2012-7-4 20:21:33

洛阳狼王 发表于 2012-7-4 20:05 static/image/common/back.gif
这个题我真看不懂。

额……不好意思，可能是我表达的不好……K3是complete graph，就是3个点，有3条线使他们两两相连

chuchudengren 发表于 2012-7-4 20:39:03

本帖最后由 chuchudengren 于 2012-7-4 21:09 编辑

第一个就是托兰定理的特例,一般图论书应该都该有这个定理的.第二个记得用归纳法证过,具体证法我再想想

Edit从书上抄了个证明：
当n=2 时，显然成立；
设n<k时成立，当n=k时:
由第一条知存在K3, 设三顶点A,B,C的度分别为n1+2, n2+2, n3+2. 如果n1+n2+n3>=3k-4时,考虑含有A、B、C中至少两个点的K3个数，此时K3个数>=(n1+n2+n3)-(2k-3) +1>=k； 当n1+n2+n3<=3k-5, n1+n2、n2+n2、n1+n3中必有一个小于等于2k-4, 不妨设为n1+n2, 这样移去这两个点以及与其相连的线,余下的图有归纳法假设知含有至少k-1个K3，因此原图含有至少k个K3
由归纳法知命题成立。

Light 发表于 2012-7-4 20:53:07

chuchudengren 发表于 2012-7-4 20:39 static/image/common/back.gif
第一个就是托兰定理的特例,一般图论书应该都该有这个定理的.第二个记得用归纳法证过,具体证法我再想想

恩，非常感谢！

Light 发表于 2012-7-4 21:18:24

chuchudengren 发表于 2012-7-4 20:39 static/image/common/back.gif
第一个就是托兰定理的特例,一般图论书应该都该有这个定理的.第二个记得用归纳法证过,具体证法我再想想

E ...

非常感谢！魔方吧上果然有大神！

则卷同学 发表于 2012-7-5 01:52:00

我能说我是把题目看成数论然后兴高采烈的进来的么...

只会十贰板 发表于 2012-7-5 08:45:57

仔细琢磨了下。没看懂。。。我悲剧了

PKUSMSBQ 发表于 2012-7-5 10:49:16

果然是用归纳法的
页: [1]
查看完整版本: 请教图论题，求大神帮助！