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

KeyTo9_Fans

如题。给定顶点数$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$时的答案。

hujunhua

显然，楼主所说的是无圈、无二重边的简单图。

1、当图非可平面时，一定包含一个K3,3子图{{1,2,3}-{4,5,6}}(如图1中深色边)，剩下的边所关联的顶点集只能含于{1，2，3}和{4，5，6}之一，不妨设含于{1，2，3}，显然其中最大只许连2条边（图1中浅色边）。这时可得到的最大值M=11.

图1

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一种拓扑：

图2

可以证明只有这一种拓扑。由于不包含K4子图的最大图的V3=0（即不含3度点），N=6时顶点最大度数<6，所以
V=V4+V5
2E=4V4+5V5=4V+V5
将E=12，V=6代入可得V5=0，故图为4-正则图，又为最大图，故只有一种。

hujunhua

可以得到 $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)

hujunhua

虽然M(5)=8<3(N-2), 但对于较大的N，上述结论或许能成立。

hujunhua

錯了。对于较大的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).  三次增长很容易超越线性增长和二次增长。

hujunhua

“如果M总可以由可平面图取得，…… ”
这个如果永远也结不了果

hujunhua

N=7时，下图E=16不含K4，为一个K3,4+一个四边形。K3,4见深色边。

KeyTo9_Fans

已有的结果：

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

证明了该猜想。

KeyTo9_Fans

我将该结果提交到了《在线整数数列百科大全》

http://oeis.org/A000212

上，当天就被采纳了：

hujunhua

我还没有检查我在5#第2条的错误，第2条说M至少是N的3次方级