证明：任何阶数至少是4且有ε条边的三角剖分图都含有条边的二部分子图。
证：
1.应用欧拉公式:
-
根据欧拉公式，对于任何平面图，我们有
，其中
是顶点数.
是边数，
是面数。对于三角剖分图
,我们有
。
-
对于三角剖分图，每个面都是三角形，每个三角形有3条边，而每条边被两个面共享。因此，我们有
，从而得到
。
2.代入欧拉公式:
- 将
代入欧拉公式中，我们得到
，整理得到
。
3.构造二部分子图:
- 根据 König定理，任何平面图的最大匹配数
满足
。
-由于是三角剖分图，且每个面都是三角形，我们可以利用Hajós定理:任何平面图的最大匹配数
满足
。
4.分析最大匹配与二部分图:
-
对于任何平面图，最大匹配数
满足
。
-
由于我们可以找到一个最大匹配
-
对于三角剖分图
条边。因此，我们可以将这些匹配边和剩余的边构成一个二部分子图。
5.总结:
- 通过构造一个包含最大匹配
条边的二部分子图。
综上，证明了任何阶数至少是4且有条边的三角剖分图都含有
条边的二部分子图。
网友评论