不包含K4子图的无向图最多可以有多少条边？

hujunhua · 发表于 2012-5-24 16:38:15

楼主帮我检查一下K3,3,4吧，N=10时，按8#应是M=33，但K3,3,4的E=3×3×4=36>33

KeyTo9_Fans · 发表于 2012-5-24 16:41:54

本帖最后由 KeyTo9_Fans 于 2012-5-24 16:43 编辑

“N=3n时，可以包含子图Kn,n,n”

这是对的。

“Kn,n,n的边数为n×n×n”

这里不对。应该是$3n^2$。

类似地，

$K_{n,n,n+1}$的边数为$n^2+2n(n+1)$，

$K_{n,n+1,n+1}$的边数为$(n+1)^2+2n(n+1)$。

分情况讨论$N$模$3$，即得$8$楼猜想。

#####

$K_{3,3,4}$的边数为$3*3+3*4+3*4=33$。

hujunhua · 发表于 2012-5-24 19:54:30

明天去做个体检，看看我的脑袋是不是进水了。

hujunhua · 发表于 2012-5-24 19:58:05

Kn的边数都只有n的2次方级，居然……

jsliyuan · 发表于 2012-6-5 19:25:36

这个问题的结论就是Turan定理
见http://en.wikipedia.org/wiki/Tur%C3%A1n's_theorem

账号		自动登录	找回密码
密码			欢迎注册

[提问] 不包含K4子图的无向图最多可以有多少条边？

评分