華格納定理

維基百科,自由的百科全書
K5 (左) 和 K3,3 (右) 是非平面彼得森圖圖子式 (彩色小圓圈和黑色邊,刪除紅色頂點,收縮每個黃色圓圈內的邊)。
兩個平面圖以及華格納圖的「clique-sum」,創建無K5圖。

圖論中,華格納理論(英語:Wagner's theorem)是平面圖的禁圖表徵,以Klaus Wagner的命名。 該定理說:若且唯若有限圖的子式不包含完全圖K5完全二分圖K3,3 時候,那麼該圖就是平面的。

這是圖子式論最早的結果之一,也是羅伯遜–西摩定理(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 .