瓦格納定理

在圖論中，瓦格納理論（英語：Wagner's theorem）是平面圖的禁圖表徵，以Klaus Wagner的命名。 該定理說：若且唯若有限圖的子式不包含完全圖K₅ 或完全二分圖K_3,3 時候，那麼該圖就是平面的。

K₅ (左) 和 K_3,3 (右) 是非平面彼得森圖的圖子式 (彩色小圓圈和黑色邊，刪除紅色頂點，收縮每個黃色圓圈內的邊)。

兩個平面圖以及瓦格納圖的「clique-sum」，創建無K₅圖。

這是圖子式論最早的結果之一，也是羅伯遜–西摩定理（Robertson-Seymour theorem）的先驅。

庫拉托夫斯基定理的關係

瓦格納1937年發表了證明。^[1] 庫拉托夫斯基以前1930年出版了自己庫拉托夫斯基理論。^[2]

根據該定理，若且唯若圖的子圖的細分不包含那些禁圖K₅ 和 K_3,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.