关于连通平面二分图存在性判定及边数不等式适用场景的技术疑问

嘿，我来给你掰扯清楚这两个不等式的适用边界，核心区别就在于图是否为二分图：

先明确两个公式的来龙去脉：

• m ≤ 3n - 6：这是所有简单连通平面图的通用边数上限，推导时默认图里允许存在三角形这类奇环，每个面至少由3条边围成。它的适用范围最广，但上限也最宽松——不管你的图是不是二分图都能用，但对二分图来说这个约束太“松”，体现不了其特性。
• m ≤ 2n - 4：这是简单连通平面二分图的专属紧上限！因为二分图里不存在奇环，所以图里的任何一个面（区域）至少得是4条边围成的（比如四边形），基于这个更严格的前提推导出来的上限更精准，完全贴合二分平面图的特性。

回到你的问题：你这里讨论的是二分平面图，所以必须用m ≤ 2n -4，不能用3n-6。原因很直白：

你用欧拉公式推导区域数上限的时候，需要的是二分图对应的精准边数约束。如果误用通用的3n-6，算出来的区域数上限会是r = (3n-6) -n +2 = 2n-4，这比你用二分图专属公式得到的n-2松太多了，根本体现不出二分平面图的真实区域数上限。

举个直观的小例子：比如4个顶点的完全二分图K₂,₂（就是个四边形），它的边数m=4，用2n-4算刚好是4，完美匹配；但用3n-6算的话是6，这个上限对它来说毫无意义——它根本不可能有6条边。

备注：内容来源于stack exchange，提问作者toru