由14個點組成的5-正則圖必不是平面圖
我們用反證法證明結論。假定存在 $5$-正則平面圖 $G_0$ 且 $|V(G_0)|=14$，不妨設 $G_0$ 已經嵌入(embed) $\mathbb{R}^2$ 裡了。首先觀察到 \[|E(G_0)| = \frac{1}{2} \cdot 5 \cdot 14 = 35.\] 另一方面，平面圖的邊數上限給出 $3|V(G_0)| - 6 = 36$，我們可以得到以下的引理： [引理 1] $G_0$ 恰包含一個 $4$ 邊組成的面 (face)。 我們加一條邊在 $G_0$ 唯一的 $4$ 邊組成的面，得到新的平面圖 $G$。$G$ 會滿足以下的性質： $G$ 有 $12$ 個點的度數為 $5$ 且有 $2$ 個點的度數為 $6$。 $G$ 上度數為 $6$ 的兩個點相鄰。 $G$ 的每個面都是三角形，且每條邊恰好夾在兩個面中間。 一個平面圖上的簡單環 $C$ 會將這個平面圖的點集合切成三塊：$C$ 內部的點 $V_\text{in}(C)$、$C$ 外部的點 $V_\text{out}(C)$、以及 $C$ 上的點 $V(C)$。我們有以下的兩個引理： [引理 2] $G$ 的每個三角形都是面。 假定引理為假，即 $G$ 有個三角形 $x_1x_2x_3$ 滿足 $|V_\text{in}(x_1x_2x_3)|$ 與 $|V_\text{out}(x_1x_2x_3)|$ 皆不為 $0$。 由於 $|V_\text{in}(x_1x_2x_3)| + |V_\text{out}(x_1x_2x_3)| = 11$，我們可以假設 $|V_\text{in}(x_1x_2x_3)| \le 5$。 另一方面，由於 $G$ 裡所有點的度數皆至少為 $5$，必須有 $|V_\text{in}(x_1x_2x_3)| \ge 3$。 情況 1：$|V_\text{in}(x_1x_2x_3)| = 3$ 由於對任意 $v \in V(G)$ 皆有 $\deg(v) \ge 5$，我們發現 導出子圖 (induced subgraph) $G[V_\text{in}(x_1x_2x_3)\cup\{x_1, x_2, x_3\}] \cong K_6$，包含了 $K_5$ 結