Kőnig's theorem (graph theory)

number）只能为三或四。3-边着色又称Tait-着色，Tait-着色方式将边集分割为三个完美匹配。根据Kőnig's_theorem（英语：Kőnig%27s_theorem_(graph_theory)）每个二分立方图都有一个Tait-着色。 关于立方图是否具有哈密顿回路（英语：Hamiltonian

cover)，根据Kőnig定理（英语：Kőnig's theorem (graph theory)），G′的最小点覆盖等于最大匹配。因此G′包含一个大小为k的匹配，即找到了G中k条内部不相交的x,y-路径。证毕。 Gammoid k-顶点连通图 k-边连通图 West, Douglas

(1976), Theorem 5.3, p. 74; Cook et al. (2011). Diestel, Reinhard. 图论 Graph Theory. 由于, 青林翻译. 北京: 科学出版社. 2020: 32. ISBN 978-7-03-064807-5.  Biggs, E. K.; Lloyd;

perfect graph theorem, Algorithmic Graph Theory and Perfect Graphs, New York: Academic Press: 53–58, 1980, ISBN 0-12-289260-7, MR 0562306 . Kőnig, Dénes

克尼格定理（英语：Kőnig's theorem (graph theory)）：二部圖的最大匹配，與最小頂點覆蓋（英语：Vertex cover）等大。 克尼格-艾蓋瓦里定理（英语：König–Egerváry theorem）（1931年），得名自克尼格·代奈什（英语：Dénes Kőnig