每个简单平面图都可以用直线段作为边来绘制

hbghlyj

Fáry's theorem
证明每个简单平面图都可以用直线段作为边来绘制，且边不相交。

图一是$K_4$用直线段作为边来绘制，不满足“边不相交”。
图二显示$K_4$为简单平面图（边不相交），但不用直线段作为边。
图三是$K_4$用直线段作为边来绘制，且边不相交。

hbghlyj

web.evanchen.cc/twitch/Ep064-Fary-theorem-Solution.tex
我们将仅对具有三个或更多顶点的极大平面图证明：即，绘制任何额外边都会破坏平面性的图。

断言：在极大平面图中，每条边都是一个圈的一部分，每个面都是一个三角形。

证明

对于第一部分，没有叶节点，所以每个顶点的度数至少为2，因此是一个圈的一部分。

对于第二部分，注意如果有一个面有四条或更多边，可以画一条弦。

我们通过归纳法证明以下断言：

断言：每个极大平面图 \( G \) 其无界面是一个三角形，可以仅用直线段绘制，使得面和内部点与原图保持相同。

证明

如果 \( G \) 是一个三角形，我们完成了。

否则，使用不等式 \( E \le 3n-6 \)，存在一个度数最多为5的顶点 \( v \)，除了无界面中的顶点。用直线段绘制 \( G-v \)。根据美术馆问题，\( v \) 可以连接到包含 \( v \) 的面的顶点，如所需。

由于任何平面图都可以重新绘制，使得一个三角形是无界面，得到了结果。

hbghlyj

hbghlyj 发表于 2025-1-23 22:39
由于任何平面图都可以重新绘制，使得一个三角形是无界面

这句话是什么意思