瓦格纳定理

图论中,瓦格纳理论(英:Wagner's theorem)平面图的禁图表征,以Klaus Wagner的命名。 该定理说:当且仅当有限图的子式不包含完全图K5完全二分图K3,3 时候,那么该图就是平面的。

K5 (左) 和 K3,3 (右) 是非平面彼得森图图子式 (彩色小圆圈和黑色边,删除红色顶点,收缩每个黄色圆圈内的边)。
两个平面图以及瓦格纳图的“clique-sum”,创建无K5图。

这是图子式论最早的结果之一,也是罗伯逊–西摩定理(Robertson-Seymour theorem)的先驱。

库拉托夫斯基定理的关系

瓦格纳1937年发表了证明。[1] 库拉托夫斯基以前1930年出版了自己库拉托夫斯基理论[2]

根据该定理,当且仅当图的子图的细分不包含那些禁图K5K3,3

瓦格纳定理意味着库拉托夫斯基,所以是更普遍的。[3]

参考资料

  1. ^ Wagner, K., Über eine Eigenschaft der ebenen Komplexe, Math. Ann., 1937, 114: 570–590, doi:10.1007/BF01594196 
  2. ^ Kuratowski, Kazimierz, Sur le problème des courbes gauches en topologie (PDF), Fund. Math., 1930, 15: 271–283 [2019-04-25], (原始内容 (PDF)存档于2018-07-23) (法语) .
  3. ^ Bondy, J. A.; Murty, U.S.R., Graph Theory, Graduate Texts in Mathematics 244, Springer: 269, 2008, ISBN 9781846289699 .