Minor theorem

The minor theorem is considered to be one of the most profound theorems of graph theory . Neil Robertson and Paul Seymour proved it in a series of 20 publications with over 500 pages. Part 1 “Excluding a Forest” was published in 1983, part 20 “Wagner's Conjecture” with the conclusion of the proof was published in 2004. In the meantime there are further sequels, in 2010 part 23 “Nash-Williams' immersion conjecture” was published. The proof is not constructive and also provides proof of Wagner's conjecture.

sentence

The finite graphs are well- quasi-ordered by the minor relation .

As simple as this sentence appears, its proof is complex. With a few lemmas, Wagner's hypothesis can be inferred from the minor sentence.

Wagner's Hypothesis (Robertson-Seymour Theorem)

Every infinite, countable set of finite graphs that is closed with regard to the formation of minors (i.e. all minors of graphs in should also belong to) can be defined by a finite set of "forbidden minors", i.e. H. there is a finite set of finite graphs such that it agrees with the set of all finite graphs that do not contain a graph from as a minor. ${\displaystyle {\mathcal {G}}=\{G_{1},G_{2},\dotsc \}}$ ${\displaystyle {\mathcal {G}}}$ ${\displaystyle {\mathcal {G}}}$ ${\displaystyle {\mathcal {H}}=\{H_{1},\dotsc ,H_{n}\}}$ ${\displaystyle {\mathcal {G}}}$ ${\displaystyle {\mathcal {H}}}$

example

An example is the set of all graphs that can be embedded in the plane (i.e. the planar graphs ). The planar graphs are closed with regard to the formation of minors, so there is a finite set of forbidden minors by which all planar graphs can be characterized. In this case it is according to Kuratowski's theorem . ${\displaystyle {\mathcal {G}}}$ ${\displaystyle {\mathcal {H}}=\left\{K_{5},K_{3,3}\right\}}$

The set of graphs that can be embedded in embeddable graphs is also closed for every other surface with regard to the formation of minors, so there is a finite set of “forbidden minors” that characterize all graphs that can be embedded. ${\displaystyle {\mathcal {S}}}$ ${\displaystyle {\mathcal {G}}}$ ${\displaystyle {\mathcal {S}}}$ ${\displaystyle {{\mathcal {H}}_{\mathcal {S}}}}$ ${\displaystyle {\mathcal {S}}}$

The only surface , apart from plane and sphere , for which the amount could previously be determined explicitly, is the projective plane . Here consists of 103 forbidden minors. ${\displaystyle {\mathcal {S}}}$ ${\displaystyle {\mathcal {H}}}$ ${\displaystyle {\mathcal {H}}}$

literature

• Reinhard Diestel: graph theory . Springer 2006, ISBN 3-540-21391-0 ( online version of the English edition )
• Laszlo Lovasz: Graph Minor Theory , Bulletin AMS, Volume 43, 2005, pp. 75-86, PDF

Individual evidence

1. ^ Robertson, Seymour: Graph Minors. I. Excluding a Forest , Journal of Combinatorial Theory B, Volume 35, 1983, pp. 39-61
2. ^ Graph Minors. XX. Wagner's Conjecture , Journal of Combinatorial Theory B, Volume 92, 2004, pp. 325-357
3. ^ Graph Minors. XXIII. Nash-Williams' immersion conjecture , Journal of Combinatorial Theory B, Volume 100, 2010, pp. 181-205
4. ^ Dan Archdeacon: A Kuratowski Theorem for the Projective Plane. Graph Theory, Vol. 5, 1981, pp. 243-246