图Gₙ平面性判定的理论方法及n取值范围求解问询

我们需要分析顶点集为{1,2,…,n}的简单图Gₙ（两顶点相邻当且仅当一个是另一个的倍数）的平面性，核心依据平面图的欧拉公式推论和Kuratowski定理：

关键判定依据 #

1. 欧拉公式推论：对于n≥3的简单平面图，边数m满足 ( m \leq 3n - 6 )。这是平面图的必要条件（不满足则一定不是平面图）。
2. Kuratowski定理：一个图是平面图当且仅当它不含K₅（5顶点完全图）或K₃,₃（完全二分图）的细分图。

计算Gₙ的边数 #

Gₙ的边对应“一个数是另一个数的倍数”的有序对（去重后），边数公式为：
[ m = \sum_{d=1}^n \left( \left\lfloor \frac{n}{d} \right\rfloor - 1 \right) = \sum_{d=1}^n \left\lfloor \frac{n}{d} \right\rfloor - n ]
其中 ( \left\lfloor \frac{n}{d} \right\rfloor ) 表示d的倍数在1~n中的个数，减1是排除d自身。

分情况讨论 #

1. n≤35时，Gₙ是平面图 #

• 满足欧拉公式推论：通过计算验证，当n≤35时，边数m始终满足 ( m \leq 3n -6 )。例如：
  • n=12时，( m=23 \leq 3×12-6=30 )
  • n=35时，( m=96 \leq 3×35-6=99 )
• 不含K₅或K₃,₃的细分：
  • K₅不存在：Gₙ中任意5个顶点无法两两相邻——任意两个质数（如2和3）互不相邻，无法构成完全图。
  • K₃,₃的细分不存在：构造K₃,₃的细分需要两个独立集及9条内部不相交的路径，但Gₙ中无倍数关系的顶点（如2和3）的路径必须经过1，而1无法被多条路径共享（细分路径内部顶点需互不相交），因此无法构造符合要求的细分图。

2. n≥36时，Gₙ不是平面图 #

当n=36时，边数 ( m=106 )，而 ( 3×36-6=102 )，此时 ( m>3n-6 )，违反欧拉公式推论的必要条件，因此G₃₆不是平面图。

对于n>36，边数m的增长速度快于3n-6（倍数关系的数量随n增大呈对数增长，最终会超过线性的3n-6），因此所有n≥36的Gₙ均不满足平面图的必要条件，不是平面图。

结论 #

Gₙ是平面图当且仅当 ( \boldsymbol{n \leq 35} )。

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