查看: 2081|回复: 8

请教图论题，求大神帮助！ [复制链接]

Light

红魔

Rank: 4

积分: 1041
帖子: 559
精华: 4
UID: 1241121
性别: 男

电梯直达

1^#

发表于 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条线使他们两两相连
其实貌似如果能看懂，不用非得学过图论

收藏0

Why...so...seriouS!!!

使用道具举报

洛阳狼王

铜魔

非著名魔方评论家

Rank: 8 Rank: 8

积分: 9548
帖子: 8704
精华: 0
UID: 104435

2^#

发表于 2012-7-4 20:05:29 |只看该作者

这个题我真看不懂。

河南省魔方学院：42752277

使用道具举报

Light

红魔

Rank: 4

积分: 1041
帖子: 559
精华: 4
UID: 1241121
性别: 男

3^#

发表于 2012-7-4 20:21:33 |只看该作者

洛阳狼王发表于 2012-7-4 20:05
这个题我真看不懂。

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

Why...so...seriouS!!!

使用道具举报

chuchudengren

红魔

Rank: 4

积分: 2052
帖子: 1452
精华: 5
UID: 84402
性别: 男

4^#

发表于 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
由归纳法知命题成立。

contact me by email: chutianxiang at gmail.com

使用道具举报