当前位置:   article > 正文

MT【144】托兰定理【图论】

图论托兰定理

平面上$2n$个点$(n>1,n\in N)$,无三点共线,任意两点连线段,将其中任意$n^2+1$条线段染红色.

求证:三边都为红色的三角形至少有$\left[\dfrac{2}{3}(n+\dfrac{1}{n})\right]$ 个.

证明:这里染红色的线段看成边,设第$k$个顶点 $v_k$ 引出的边有 $d_k$ 条 $(k=1,2,\cdots,2n)$. 记所有的边组成的集合为 $E$.若$v_iv_j\in E$,则$v_i,v_j$ 向其余$2n-2$个顶点引出$d_i+d_j-2$ 条边.所以至少有$d_i+d_j-2-(2n-2)$对分别由$v_i,v_j$引向同一顶点的边.它们和$v_iv_j$一起构成三角形.所以至少有$d_i+d_j-2n$个三角形包含边$v_iv_j$.又由于图中每个三角形被计算了三次,所以图中至少有$\dfrac{1}{3}\sum\limits_{v_iv_j\in E}{(d_i+d_j-2n)}$个三角形.上述和式中$d_i$ 出现了$d_i$次,条件中已知边数$|E|=n^2+1$,且各顶点引出的边数和边的总数的关系为$\sum\limits_{i=1}^{2n}{d_i}=2(n^2+1)$所以
\begin{align*}
\dfrac{1}{3}\sum\limits_{v_iv_j\in E}{(d_i+d_j-2n)}
&=\dfrac{1}{3}\left(\sum\limits_{i=1}^{2n}{d_i^2}-(n^2+1)2n\right) \\
&\ge\dfrac{1}{3}\left(\dfrac{1}{2n}\left(\sum\limits_{i=1}^{2n}{d_i}\right)^2-(n^2+1)2n\right)\\
&=\dfrac{1}{3}\left(\dfrac{1}{2n}\left

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/羊村懒王/article/detail/716490
推荐阅读
相关标签
  

闽ICP备14008679号