Graph Theory, Lecture 45: Graph Minors I: The graph minor theorem, its proof for trees, and wqo скачать в хорошем качестве

Graph Theory, Lecture 45: Graph Minors I: The graph minor theorem, its proof for trees, and wqo

Recap: which graph properties can be characterised by excluding minors? Notion of Kuratowski set (of graphs for a given minor-closed property), 6:45. Statement (via minor-antichains) of graph minor theorem, Theorem 12.7.1 (7:00). Notion of excluded-minor theorems (8:25). The myth of Wagner's Conjecture (8:55). Algorithmic consequences of the graph minor theorem (10:40). Two applications of the graph minor theorem: surface embeddability, and knotless embeddability in 3-space. Notion of well-quasi-ordering (wqo, 17:25); expressing the graph minor theorem in these terms. Basic wqo properties. Higman's lemma (28:50), with false 'obvious' proof (32:00-35:00). Correct proof by minimal bad sequence method (37:00-45:00). Embeddings of rooted trees, strengthening the graph minor relation for trees. Proof of the 'graph minor theorem for trees': Kruskal's Theorem 12.2.1 that the trees are wqo by rooted-tree embedding. Covers Chapter 12.1-2. Based on R.Diestel, Graph Theory, Springer GTM173, 6th edition 2025. Ebooks available at https://diestel-graph-theory.com under links "Standard eBook" and "Professional Edition".