凸 n 边形及 n−3 条在 n 边形内不相交的对角线组成的图形称为一个剖分图.求证:当且仅当 3∣n 时,存在一个剖分图是可以一笔划的圈(即可以从一个顶点出发,经过图中各线段恰一次,最后回到出发点).
解析
因为 n−3 条在形内互不相交的对角线将凸 n 边形分为 n−2 个顶点均是 n 边形顶点的小区域,每个区域的内角和不小于 π,n 边形的内角和为 (n−2)π,所以每个小区域都是三角形.
必要性 用归纳法容易证明可将每个三角形区域涂成白蓝两色之一,使得有公共边的三角形不同色.假设已按照这样的要求染色,由于剖分图为可以一笔画的圈,所以由每个顶点引出的线段都是偶数条.从而每个顶点都是奇数个三角形的顶点,因此以原多边形外边界为一边的三角形区域有着相同的颜色,不妨设为白色;另一方面,剖分图的每条对角线都是两种不同颜色三角形的公共边,所以设白三角形有 m1 个,蓝三角形有 m2 个,则n=3m1−3m2⟹3∣n.
充分性 设 n=3m,多边形为 A1A2⋯A3m,连接 3m−3 条对接线,形成 m−1 个三角形 A1A3iA3i+2(i=1,2,⋯,m−1),然后由 A1 出发,依次走过这些三角形,再走过凸多边形的外边界即可一笔画并回到初始点 A1,命题得证.