反证法,假设不存在.

给每个点赋予电量$c(v)=6-d(v)$,给每个面赋予电量$c(f)=6-2d(v)=0$,($d(f)$表示这个面的边界由几条边构成).

于是点上的总电量之和为

然后重新分配电量:把每个$5$度点的电量平均分给它的每个邻居.设新电量为$c'(u)$则:

• $d(u)=5 \Rightarrow c'(u)=0$(不存在相邻的5度点,分完之后成了$0$)
• $d(u)=6 \Rightarrow c'(u)=0$(不会接收到5度点的电量,且原来为$0$)
• $d(u)\ge 7 \Rightarrow c'(u)\le c(u)+\dfrac15 \lbrack \dfrac{d(u)}{2} \rbrack<0$.(这里除以$2$是因为是你是三角剖分图,所以$u$的邻居一定构成一个环,而不能有两个$5$度点相连,所以最多是$\dfrac {d(u)}2$)

你发现所有点的电量都成负的了.

所以如果不存在那两种边,你流动总电量从正的变成负的了,所以矛盾.就证明完了.

设$N(u)$表示$u$的所有相邻点.

考虑任取一条边$(u,v)$,则$N(u)\cap N(v)=\varnothing$,于是$d(u)+d(v)\le n$.

把每条边的式子加起来,得到:

因为

由柯西不等式

联立得$4e(G)^2\le e(G)n^2$,就得到$e(G)\le \dfrac{n^2}4$.