不包含K4子图的无向图最多可以有多少条边？
如题。给定顶点数$N$，求边数$M$的最大值。注：$K4$子图就是$4$个顶点的完全图。
例$1$：当$N=1$时，没有边可连，所以$M=0$。
例$2$：当$N=2$时，可连$1$条边，所以$M=1$。
例$3$：当$N=3$时，可连$3$条边，所以$M=3$。
例$4$：当$N=4$时，由于不能连成$4$个顶点的完全图，最多可连$5$条边，所以$M=5$。
例$5$：当$N=5$时，由于不能包含$4$个顶点的完全图，最多可连$8$条边，所以$M=8$。
求$N>5$时的答案。
N=6时，M=12
显然，楼主所说的是无圈、无二重边的简单图。1、当图非可平面时，一定包含一个K3,3子图{{1,2,3}-{4,5,6}}(如图1中深色边)，剩下的边所关联的顶点集只能含于{1，2，3}和{4，5，6}之一，不妨设含于{1，2，3}，显然其中最大只许连2条边（图1中浅色边）。这时可得到的最大值M=11.
2、当图可平面时，由欧拉公式可得E=V+F-2=F+4，所以F越多，E越大。又2E=3F3+4F4+5F5+6F6=3F+F4+2F5+3F6
将F=E-4代入得E=12-F4-2F5-3F6<=12.
可见E最大值M=12，并且在形成最大图时E最大，这时F=F3=8。以下是M=12一种拓扑：
可以证明只有这一种拓扑。由于不包含K4子图的最大图的V3=0（即不含3度点），N=6时顶点最大度数<6，所以
V=V4+V5
2E=4V4+5V5=4V+V5
将E=12，V=6代入可得V5=0，故图为4-正则图，又为最大图，故只有一种。
M>=3(N-2)
可以得到 E=3(N-k)-(F4+2F5+3F6+...+(N-3)F_N)所以不论k取什么，总是在最大图（即F4以上皆为0）时E最大。
由于k的最大值为2，所以最大值M>=3(N-2).
如果M总可以由可平面图取得，那么M=3(N-2) 虽然M(5)=8<3(N-2), 但对于较大的N，上述结论或许能成立。 錯了。对于较大的N, M可以轻易超过3(N-2).
1、比如N=2n时，可以包含子图Kn,n，Kn,n的边数为n×n, 当N=2n+1时，可以包含子图Kn,n+1,而Kn,n+1的边数为n×(n+1).二次增长很容易超越线性增长。
2、N=3n时，可以包含子图Kn,n,n，而Kn,n,n的边数为n×n×n; 当N=3n+1时，可以包含子图Kn,n,n+1,而Kn,n,n+1的边数为n×n×(n+1); 当N=3n+2时，可以包含子图Kn,n+1,n+1,而Kn,n+1,n+1的边数为n×(n+1)×(n+1).三次增长很容易超越线性增长和二次增长。 “如果M总可以由可平面图取得，…… ”
这个如果永远也结不了果:L
N=7时，M>=16
N=7时，下图E=16不含K4，为一个K3,4+一个四边形。K3,4见深色边。 本帖最后由 KeyTo9_Fans 于 2012-5-23 22:47 编辑已有的结果：
N=0: 0
N=1: 0
N=2: 1
N=3: 3
N=4: 5
N=5: 8
N=6: 12
N=7: 16
与整数数列百科大全上的一个数列：
http://oeis.org/A000212
的前$8$项相同。
于是得到一个猜想：
$M = f l o o r (N^2/3)$
这个猜想是否成立呢？
#####
Google了一下，发现
http://en.wikipedia.org/wiki/Tur%C3%A1n%27s_theorem
证明了该猜想。 我将该结果提交到了《在线整数数列百科大全》
http://oeis.org/A000212
上，当天就被采纳了：
我还没有检查我在5#第2条的错误，第2条说M至少是N的3次方级
页:
[1]
2