Robertson–Seymour theorem

The Minorentheorem is one of the most profound results 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 " released in 1983, Part 20, "Wagner 's Conjecture " with the completion of the proof appeared in 2004. Meanwhile, there are more sequels, was released in 2010 Part 23 " Nash -Williams ' immersion conjecture ". The proof is not constructive, and also provides a proof of Wagner 's conjecture.

Set

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

So simple anmutet this sentence, so complex is its proof. With some lemmas can be deduced from the Minor set Wagner's conjecture.

Wagner's conjecture ( set of Robertson - Seymour )

Every infinite countable set of finite graphs, completed with respect to the education of minors (that is, all minors of graphs in are also intended to include ) can be defined by a finite set of "forbidden minors ", ie there is a finite set of a finite graph so that matches the set of all finite graph containing no graph of the minor.

Example

An example is the set of all the level embeddable graph ( that is, the planar graph ). The planar graphs are closed under Minor education, so there is a finite set of forbidden minors, can be characterized by all planar graphs. In this case, by the theorem of Wagner.

Also, for any other area is the set of graphs embeddable completed in respect of the formation of the minors, so there is a finite set of "forbidden minors ", all characterize embeddable graphs.

The only area except plane and sphere, for which anyone would have the quantity explicitly determine the projective plane. This consists of 103 minors prohibited.