每日一题[1679]剖分

凸 $n$ 边形及 $n-3$ 条在 $n$ 边形内不相交的对角线组成的图形称为一个剖分图．求证：当且仅当 $3\mid n$ 时，存在一个剖分图是可以一笔划的圈（即可以从一个顶点出发，经过图中各线段恰一次，最后回到出发点）．

解析

因为 $n-3$ 条在形内互不相交的对角线将凸 $n$ 边形分为 $n-2$ 个顶点均是 $n$ 边形顶点的小区域，每个区域的内角和不小于 $\mathrm \pi$，$n$ 边形的内角和为 $\left(n-2\right)\mathrm \pi$，所以每个小区域都是三角形．

必要性     用归纳法容易证明可将每个三角形区域涂成白蓝两色之一，使得有公共边的三角形不同色．假设已按照这样的要求染色，由于剖分图为可以一笔画的圈，所以由每个顶点引出的线段都是偶数条．从而每个顶点都是奇数个三角形的顶点，因此以原多边形外边界为一边的三角形区域有着相同的颜色，不妨设为白色；另一方面，剖分图的每条对角线都是两种不同颜色三角形的公共边，所以设白三角形有 $m_1$ 个，蓝三角形有 $m_2$ 个，则

$$n=3m_1-3m_2\implies 3\mid n.$$

充分性    设 $n=3m$，多边形为 $A_1A_2\cdots A_{3m}$，连接 $3m-3$ 条对接线，形成 $m-1$ 个三角形 $A_1A_{3i}A_{3i+2}$（$i=1,2,\cdots,m-1$），然后由 $A_1$ 出发，依次走过这些三角形，再走过凸多边形的外边界即可一笔画并回到初始点 $A_1$，命题得证．