本帖最后由 abababa 于 2014-7-23 19:07 编辑
发一位网友的解答，经过他的讲解终于看懂了
当$n = 4$时$G$中有$4$个顶点和$5$条边，而$4$点间可连$C_{4}^{2} = 6$条边，共$4$个三角形
去掉一条边至多减少$2$个三角形，所以$4$顶点连$6-1 = 5$条边时必有$4-2 = 2$个有公共边的三角形
假设当$n=k > 2$时命题成立，即$2n=2k$个点连$n^2+1=k^2+1$条边时命题成立
当$n=k+1$时，$2n=2k+2$个点连$n^2+1=k^2+2k+2$条边
设度数最小和次小的点分别为$A,B$，总度数为$d$
则$d(A) \le d(B) \le \cdots$，若$d(B) \ge k+2$，则$d \ge d(A)+(k+2)(2k+2-1) \ge (k+2)(2k+1)=2k^2+5k+2$
但$d=2E=2(k^2+2k+2)=2k^2+4k+4$，所以$2k^2+4k+4 \ge 2k^2+5k+2$，于是$k \le 2$，与$k > 2$矛盾，所以$d(B) < k+2$，由离散性知$d(B) \le k+1$
下面分两步，他用了enumerate环境，这里显示不出来，只好改一下
第一步：
若$d(A)=k+1$，则$d(B)=k+1$，图中每个点至少都为$k+1$度，设原图为$G$
若所有点都为$k+1$度则$2k^2+4k+4=d=(k+1)(2k+2)$，矛盾，所以必有一个点至少为$k+2$度，设这点为$T$
设与$T$相邻的$k+2$个点为$P_1 \to P_{k+2}$，考察点$T,P_1 \to P_{k+2}$及它们间的边构成的图$G'$，设$G''=G-G'$，$G''$中有$2k+2-(k+3)=k-1$个点
在$G'$中，若$P_1$只与$T$相邻，则$d(P_1) \le 1+(k-1)=k$，与$d(P_1) \ge k+1$矛盾
所以在$G'$中$P_1$必与除$T$外的某点相邻，不妨设$P_1, P_2$相邻，则只要考察$P_1$与$P_3 \to P_{k+2}$都不相邻的情况，否则构成两三角形$AP_1P_2, AP_1P_i$有公共边$AP_1$，即在图$G'$的$k+3$个点中，$P_1$至多为$2$度，而在图$G''$中有$k-1$个点，所以$P_1$至多为$k-1+2=k+1$度，但$P_1$至少为$k+1$度，所以$d(P_1)=k+1$，即$P_1$与图$G''$中$k-1$个点都相邻，同理$P_2$与$G''$中$k-1$个点都相邻
由于$k \ge 3$，$k-1 \ge 2$，所以$G''$中的$k-1$个点能选出一个点$M$
于是$P_1, P_2$都与$M$相邻，也都与$T$相邻，构成有公共边$P_1P_2$的两个三角形
第二步：
若$d(A) \neq k+1$，则由于$d(A) \le d(B) \le k+1$，所以$d(A) \le k$
此时从$2k+2$个点中删除点$A, B$和它们连出的边，还有$2k$个点和至少$k^2+2k+2-(k+1)-(k) = k^2+1$条边，由归纳假设知命题成立 |
新浪微博
QQ空间
人人网
腾讯微博
Facebook
Google+
Plurk
Twitter
Line
发表于 2014-7-18 09:01
| 
QQ空间
腾讯微博
腾讯朋友