NOIP 提高组初赛 · NOIP 2011 提高组初赛试题 第 21 题

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

这题考平面图边数极限。别死磕画图的直觉，直接套欧拉公式变形出的结论——n≥3时，任何简单平面图边数都不超过3n-6。把n=5代进去，算数比画图快多了。

很多学生看到'最少'就慌了，以为要构造特例，或者被题目里4个点6条边的例子误导，觉得5个点是不是只要加一条边就行？其实平面图有个铁律：边数是有上限的。如果你试图画一个5个点、8条边还能平面的图，大概率会发现不得不有边交叉，那就不是平面图了。命题人就是盯着这个上限挖坑，让你以为'最少'是构造题，其实'最少'对应的是'最大可能值'（因为简单图里，边越多越容易交叉，能保持平面的最大边数就是下限里的'紧'值）。

这道题考查平面图的基本性质，核心是欧拉公式及其推论。平面图定义很简单：能画在平面上且边只在顶点处相交的图。题目给了4个顶点的例子，边数是6，这其实是完全图K4，也是4顶点时平面图能有的最大边数。现在问5个顶点，很多人会想'最少要几条边才能保持平面'，但这里有个反直觉的点：在简单图中，边越多越容易交叉，所以能保持平面的图，边数其实是有一个'天花板'的。这个天花板就是3n-6（n≥3）。为什么是3n-6？从欧拉公式V-E+F=2出发，对最大平面图（也就是三角剖分，每个面都是三角形），每个面至少3条边，每条边属于两个面，所以3F≤2E，代入欧拉公式就能推出E≤3V-6。反过来，只要边数不超过3n-6，就一定能构造出一个平面图（比如从K_n开始删边，删到满足条件为止）。因此，5个顶点的平面图，边数最多是3×5-6=9。题目问'至少'，结合上下文和4顶点的情况（4顶点平面图最多也是6，而K4恰好6），这里的'至少'其实是问'在保持平面的前提下，边数最多能是多少'（因为简单图里，边数越多越难平面，能平面的最大边数就是那个'紧'的下限）。答案就是9。