NOIP 提高 2011 第一轮 第 21 题：平面图是可以画在平面上，且它的边仅在顶点上才能相交的简单无向图

题目

平面图是可以画在平面上，且它的边仅在顶点上才能相交的简单无向图。4个顶点的平面图至多有6条边，如下图所示。那么，5个顶点的平面图至多有_条边。

答案

9

题解

考点定位

本题考「平面图边数上界」，对应大纲 3.3.1 平面图（难度【4】）。

解题过程

欧拉公式的推论：顶点数 $n \geq 3$ 的简单平面图满足 $e \leq 3n - 6$。

• 验证题面例子：$n = 4$ 时 $e \leq 3 \times 4 - 6 = 6$，$K_4$（4 顶点 6 边）确实可平面，题图正是取到上界的情形；
• 本题：$n = 5$ 时 $e \leq 3 \times 5 - 6 = 9$；
• 上界取得到：$K_5$（10 条边）非平面，但去掉任意一条边得 9 条边的图，可以平面嵌入。

所以 5 个顶点的平面图至多有 9 条边。

易错提醒

① 公式前提是简单图（无重边、无自环）且 $n \geq 3$； ② 原卷问的是「至多」（边数上界，考欧拉公式）；若问「至少」，连通图最少只需生成树的 $n-1$ 条边——读题别混淆方向。