一、计算顶点数n #

首先，我会用平面图的两个核心定理来推导n的值：

1. 欧拉公式：对于任意连通平面图，顶点数V、边数E、面数F满足 V - E + F = 2
2. 握手引理：所有顶点的度数之和等于边数的2倍，即 $\sum_{v \in V} deg(v) = 2|E|$

题目里给出每个顶点度数为4，顶点数是n，代入握手引理可得：
4n = 2|E|，直接化简得到边数 |E| = 2n

接下来把E=2n、F=10代入欧拉公式：

n - 2n + 10 = 2

整理计算：-n = 2 - 10，解得 n = 8

所以唯一可能的顶点数是8，我们需要找的是8个顶点的4-正则简单连通平面图，且面数为10。

二、分析面的度数分布 #

为了进一步缩小图的范围，我们可以计算面的度数信息：平面图中所有面的度数之和等于边数的2倍（每条边属于两个面），即 $\sum_{f \in F} deg(f) = 2|E|$

代入已知的E=16，可得所有面的度数之和为32。设k_i表示度数为i的面的数量，结合F=10，我们有：

• $k_3 + k_4 + k_5 + ... = 10$
• $3k_3 + 4k_4 + 5k_5 + ... = 32$

联立两个式子消去k_4及更高次项，得到：
k_3 = 8 - 4k_5 - ...

由于k_3不能为负数，k_5及更高度数的面数只能为0，因此唯一可行的面度数分布是：8个三角形面（度数3）和2个四边形面（度数4）。

三、枚举所有非同构的符合条件的图 #

满足条件的8顶点4-正则连通平面图共有2个非同构的，具体描述如下：

1. 分离四边形型4-正则平面图 #

这个图的结构包含两个完全不相交的四边形面，其余8个面都是三角形：

• 先构造两个独立的4-圈（四边形）：设第一个圈为$v_1-v_2-v_3-v_4-v_1$，第二个圈为$v_5-v_6-v_7-v_8-v_5$
• 对每个圈的顶点，连接到另一个圈的两个顶点：$v_1$连$v_5$、$v_6$；$v_2$连$v_6$、$v_7$；$v_3$连$v_7$、$v_8$；$v_4$连$v_8$、$v_5$
• 这样每个顶点的度数为2（来自自身4-圈）+2（跨圈连接）=4，正好满足4-正则的要求，同时形成8个三角形面和2个独立的四边形面。

2. 共享边四边形型4-正则平面图 #

这个图的两个四边形面共享一条公共边，其余8个面都是三角形：

• 先构造两个共享一条边的四边形：比如共享边$v_1-v_2$，第一个四边形是$v_1-v_2-v_3-v_4-v_1$，第二个四边形是$v_1-v_2-v_5-v_6-v_1$
• 此时$v_1$、$v_2$的度数为3，$v_3$、$v_4$、$v_5$、$v_6$的度数为2，剩下两个顶点$v_7$、$v_8$需要补充连接：
  • 连接$v_7$到$v_3$、$v_5$、$v_8$、$v_4$；连接$v_8$到$v_1$、$v_2$、$v_6$、$v_7$（具体连接方式需保证所有顶点度数为4，且形成三角形面）
• 最终的图中，两个四边形共享一条边，其余所有面都是三角形，满足面数10的要求。

这两个图的核心区别在于两个四边形面的位置关系：一个是完全分离，一个是共享边，因此它们是非同构的。

内容的提问来源于stack exchange，提问作者Leo Lien