Graph structure theorem

A minor of a graph {{mvar|G}} is any graph {{mvar|H}} that is isomorphic to a graph that can be obtained from a subgraph of {{mvar|G}} by contracting some edges. If {{mvar|G}} does not have a graph {{mvar|H}} as a minor, then we say that {{mvar|G}} is {{mvar|H}}-free. Let {{mvar|H}} be a fixed graph. Intuitively, if {{mvar|G}} is a huge {{mvar|H}}-free graph, then there ought to be a "good reason" for this. The graph structure theorem provides such a "good reason" in the form of a rough description of the structure of {{mvar|G}}. In essence, every {{mvar|H}}-free graph {{mvar|G}} suffers from one of two structural deficiencies: either {{mvar|G}} is "too thin" to have {{mvar|H}} as a minor, or {{mvar|G}} can be (almost) topologically embedded on a surface that is too simple to embed {{mvar|H}} upon. The first reason applies if {{mvar|H}} is a planar graph, and both reasons apply if {{mvar|H}} is not planar. We first make precise these notions.

The tree width of a graph {{mvar|G}} is a positive integer that specifies the "thinness" of {{mvar|G}}. For example, a connected graph {{mvar|G}} has tree width one if and only if it is a tree, and {{mvar|G}} has tree width two if and only if it is a series–parallel graph. Intuitively, a huge graph {{mvar|G}} has small tree width if and only if {{mvar|G}} takes the structure of a huge tree whose nodes and edges have been replaced by small graphs. We give a precise definition of tree width in the subsection regarding clique-sums. It is a theorem that if {{mvar|H}} is a minor of {{mvar|G}}, then the tree width of {{mvar|H}} is not greater than that of {{mvar|G}}. Therefore, one "good reason" for {{mvar|G}} to be {{mvar|H}}-free is that the tree width of {{mvar|G}} is not very large. The graph structure theorem implies that this reason always applies in case {{mvar|H}} is planar.

Corollary 1. For every planar graph {{mvar|H}}, there exists a positive integer {{mvar|k}} such that every {{mvar|H}}-free graph has tree width less than {{mvar|k}}.

It is unfortunate that the value of {{mvar|k}} in Corollary 1 is generally much larger than the tree width of {{mvar|H}} (a notable exception is when {{math|1=H = K{{sub|4}}}}, the complete graph on four vertices, for which {{math|1=k = 3}}). This is one reason that the graph structure theorem is said to describe the "rough structure" of {{mvar|H}}-free graphs.

Roughly, a surface is a set of points with a local topological structure of a disc. Surfaces fall into two infinite families: the orientable surfaces include the sphere, the torus, the double torus and so on; the nonorientable surfaces include the real projective plane, the Klein bottle and so on. A graph embeds on a surface if the graph can be drawn on the surface as a set of points (vertices) and arcs (edges) that do not cross or touch each other, except where edges and vertices are incident or adjacent. A graph is planar if it embeds on the sphere. If a graph {{mvar|G}} embeds on a particular surface then every minor of {{mvar|G}} also embeds on that same surface. Therefore, a "good reason" for {{mvar|G}} to be {{mvar|H}}-free is that {{mvar|G}} embeds on a surface that {{mvar|H}} does not embed on.

When {{mvar|H}} is not planar, the graph structure theorem may be looked at as a vast generalization of the Kuratowski theorem. A version of this theorem proved by {{harvtxt|Wagner|1937}} states that if a graph {{mvar|G}} is both {{math|K{{sub|5}}}}-free and {{math|K{{sub|3,3}}}}-free, then {{mvar|G}} is planar. This theorem provides a "good reason" for a graph {{mvar|G}} not to have {{math|K{{sub|5}}}} or {{math|K{{sub|3,3}}}} as minors; specifically, {{mvar|G}} embeds on the sphere, whereas neither {{math|K{{sub|5}}}} nor {{math|K{{sub|3,3}}}} embed on the sphere. Unfortunately, this notion of "good reason" is not sophisticated enough for the graph structure theorem. Two more notions are required: clique-sums and vortices.

A clique in a graph {{mvar|G}} is any set of vertices that are pairwise adjacent in {{mvar|G}}. For a non-negative integer {{mvar|k}}, a {{mvar|k}}-clique-sum of two graphs {{mvar|G}} and {{mvar|K}} is any graph obtained by selecting a non-negative integer {{math|m ≤ k}}, selecting clique of size {{mvar|m}} in each of {{mvar|G}} and {{mvar|K}}, identifying the two cliques into a single clique of size {{mvar|m}}, then deleting zero or more of the edges that join vertices in the new clique.

If {{math|G{{sub|1}}, G{{sub|2}}, …, G{{sub|n}}}} is a list of graphs, then we may produce a new graph by joining the list of graphs via {{mvar|k}}-clique-sums. That is, we take a {{mvar|k}}-clique-sum of {{math|G{{sub|1}}}} and {{math|G{{sub|2}}}}, then take a {{mvar|k}}-clique-sum of {{math|G{{sub|3}}}} with the resulting graph, and so on. A graph has tree width at most {{mvar|k}} if it can be obtained via {{mvar|k}}-clique-sums from a list of graphs, where each graph in the list has at most {{math|k + 1}} vertices.

Corollary 1 indicates to us that {{mvar|k}}-clique-sums of small graphs describe the rough structure {{mvar|H}}-free graphs when {{mvar|H}} is planar. When {{mvar|H}} is nonplanar, we also need to consider {{mvar|k}}-clique-sums of a list of graphs, each of which is embedded on a surface. The following example with {{math|1=H = {{math|K{{sub|5}}}}}} illustrates this point. The graph {{math|K{{sub|5}}}} embeds on every surface except for the sphere. However, there exist {{math|K{{sub|5}}}}-free graphs that are far from planar. In particular, the 3-clique-sum of any list of planar graphs results in a {{math|K{{sub|5}}}}-free graph. {{harvtxt|Wagner|1937}} determined the precise structure of {{math|K{{sub|5}}}}-free graphs, as part of a cluster of results known as Wagner's theorem:

Theorem 2. If {{mvar|G}} is {{math|K{{sub|5}}}}-free, then {{mvar|G}} can be obtained via 3-clique-sums from a list of planar graphs, and copies of one special non-planar graph having 8-vertices.

We point out that Theorem 2 is an exact structure theorem since the precise structure of {{math|K{{sub|5}}}}-free graphs is determined. Such results are rare within graph theory. The graph structure theorem is not precise in this sense because, for most graphs {{mvar|H}}, the structural description of {{mvar|H}}-free graphs includes some graphs that are not {{mvar|H}}-free.

One might be tempted to conjecture that an analog of Theorem 2 holds for graphs {{mvar|H}} other than {{math|K{{sub|5}}}}. Perhaps it is true that: for any non-planar graph {{mvar|H}}, there exists a positive integer {{mvar|k}} such that every {{mvar|H}}-free graph can be obtained via {{mvar|k}}-clique-sums from a list of graphs, each of which either has at most {{mvar|k}} vertices or embeds on some surface that {{mvar|H}} does not embed on. Unfortunately, this statement is not yet sophisticated enough to be true. We must allow each embedded graph {{mvar|G{{sub|i}}}} to "cheat" in two limited ways. First, we must allow a bounded number of locations on the surface at which we may add some new vertices and edges that are permitted to cross each other in a manner of limited complexity. Such locations are called vortices. The "complexity" of a vortex is limited by a parameter called its depth, closely related to pathwidth. The reader may prefer to defer reading the following precise description of a vortex of depth {{mvar|k}}. Second, we must allow a limited number of new vertices to add to each of the embedded graphs with vortices.

A face of an embedded graph is an open 2-cell in the surface that is disjoint from the graph, but whose boundary is the union of some of the edges of the embedded graph. Let {{mvar|F}} be a face of an embedded graph {{mvar|G}} and let {{math|v{{sub|0}}, v{{sub|1}}, ..., v{{sub|n – 1}}}}, {{math|1=v{{sub|n}} = v{{sub|0}}}} be the vertices lying on the boundary of {{mvar|F}} (in that circular order). A circular interval for {{mvar|F}} is a set of vertices of the form {{math|{v{{sub|a}}, v{{sub|a+1}}, …, v{{sub|a+s}}} }} where {{mvar|a}} and {{mvar|s}} are integers and where subscripts are reduced modulo {{mvar|n}}. Let {{math|Λ}} be a finite list of circular intervals for {{mvar|F}}. We construct a new graph as follows. For each circular interval {{mvar|L}} in {{math|Λ}} we add a new vertex {{mvar|v{{sub|L}}}} that joins to zero or more of the vertices in {{mvar|L}}. Finally, for each pair {{math|{L, M} }} of intervals in {{math|Λ}}, we may add an edge joining {{mvar|v{{sub|L}}}} to {{mvar|v{{sub|M}}}} provided that {{mvar|L}} and {{mvar|M}} have nonempty intersection. The resulting graph is said to be obtained from {{mvar|G}} by adding a vortex of depth at most {{mvar|k}} (to the face {{mvar|F}}) provided that no vertex on the boundary of {{mvar|F}} appears in more than {{mvar|k}} of the intervals in {{math|Λ}}.

Graph structure theorem. For any graph {{mvar|H}}, there exists a positive integer {{mvar|k}} such that every {{mvar|H}}-free graph can be obtained as follows:

1. We start with a list of graphs, where each graph in the list is embedded on a surface on which {{mvar|H}} does not embed
2. to each embedded graph in the list, we add at most {{mvar|k}} vortices, where each vortex has depth at most {{mvar|k}}
3. to each resulting graph we add at most {{mvar|k}} new vertices (called apices) and add any number of edges, each having at least one of its endpoints among the apices.
4. finally, we join via {{mvar|k}}-clique-sums the resulting list of graphs.

Note that steps 1. and 2. result in an empty graph if {{mvar|H}} is planar, but the bounded number of vertices added in step 3. makes the statement consistent with Corollary 1.

Strengthened versions of the graph structure theorem are possible depending on the set {{mvar|H}} of forbidden minors. For instance, when one of the graphs in {{mvar|H}} is planar, then every {{mvar|H}}-minor-free graph has a tree decomposition of bounded width; equivalently, it can be represented as a clique-sum of graphs of constant size.Graph Minors V. When one of the graphs in {{mvar|H}} can be drawn in the plane with only a single crossing, then the {{mvar|H}}-minor-free graphs admit a decomposition as a clique-sum of graphs of constant size and graphs of bounded genus, without vortices.{{harvtxt|Robertson|Seymour|1993}}; {{harvtxt|Demaine|Hajiaghayi|Thilikos|2002}}).

A different strengthening is also known when one of the graphs in {{mvar|H}} is an apex graph.{{harvtxt|Demaine|Hajiaghayi|Kawarabayashi|2009}}.

• Robertson–Seymour theorem

{{reflist}}

• {{citation

| last1 = Demaine | first1 = Erik D. | author1-link = Erik Demaine

| last2 = Hajiaghayi | first2 = Mohammad Taghi

| last3 = Kawarabayashi | first3 = Ken-ichi | author3-link = Ken-ichi Kawarabayashi

| contribution = Approximation algorithms via structural results for apex-minor-free graphs

| doi = 10.1007/978-3-642-02927-1_27

| pages = 316–327

| publisher = Springer-Verlag

| series = Lecture Notes in Computer Science

| title = Proc. 36th International Colloquium Automata, Languages and Programming (ICALP '09)

| url = http://erikdemaine.org/papers/ApexMinorFree_ICALP2009/paper.pdf

| volume = 5555

| year = 2009

| isbn = 978-3-642-02926-4 | mr = 2544855}}.

• {{citation

| last1 = Demaine | first1 = Erik D. | author1-link = Erik Demaine

| last2 = Hajiaghayi | first2 = Mohammad Taghi

| last3 = Thilikos | first3 = Dimitrios M.

| contribution = 1.5-Approximation for treewidth of graphs excluding a graph with one crossing as a minor

| doi = 10.1007/3-540-45753-4_8

| pages = 67–80

| publisher = Springer-Verlag

| series = Lecture Notes in Computer Science

| title = Proc. 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX 2002)

| volume = 2462

| year = 2002

| mr = 2091577| hdl = 2117/97497

| isbn = 978-3-540-44186-1 | hdl-access = free

}}.

• {{citation

| last1 = Kawarabayashi | first1 = Ken-ichi | author1-link = Ken-ichi Kawarabayashi

| last2 = Mohar | first2 = Bojan | author2-link = Bojan Mohar

| doi = 10.1007/s00373-006-0684-x

| issue = 1

| journal = Graphs and Combinatorics

| mr = 2292102

| pages = 1–46

| title = Some recent progress and applications in graph minor theory

| volume = 23

| year = 2007| s2cid = 7237484 }}.

• {{citation

| last = Lovász | first = László | authorlink = László Lovász

| doi = 10.1090/S0273-0979-05-01088-8

| issue = 1

| journal = Bulletin of the American Mathematical Society

| mr = 2188176

| pages = 75–86

| title = Graph minor theory

| volume = 43

| year = 2006| doi-access = free

}}.

• {{citation

| last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)

| last2 = Seymour | first2 = P. D. | author2-link = Paul Seymour (mathematician)

| doi = 10.1016/0095-8956(83)90079-5

| issue = 1

| journal = Journal of Combinatorial Theory | series = Series B

| mr = 723569

| pages = 39–61

| title = Graph minors. I. Excluding a forest

| volume = 35

| year = 1983| doi-access = free

}}.

• {{citation

| last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)

| last2 = Seymour | first2 = P. D. | author2-link = Paul Seymour (mathematician)

| doi = 10.1016/0196-6774(86)90023-4

| issue = 3

| journal = Journal of Algorithms

| mr = 855559

| pages = 309–322

| title = Graph minors. II. Algorithmic aspects of tree-width

| volume = 7

| year = 1986}}.

• {{citation

| last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)

| last2 = Seymour | first2 = P. D. | author2-link = Paul Seymour (mathematician)

| doi = 10.1016/0095-8956(84)90013-3

| issue = 1

| journal = Journal of Combinatorial Theory | series = Series B

| mr = 742386

| pages = 49–64

| title = Graph minors. III. Planar tree-width

| volume = 36

| year = 1984| doi-access = free

}}.

• {{citation

| last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)

| last2 = Seymour | first2 = P. D. | author2-link = Paul Seymour (mathematician)

| doi = 10.1016/0095-8956(90)90120-O

| issue = 2

| journal = Journal of Combinatorial Theory | series = Series B

| mr = 1046757

| pages = 227–254

| title = Graph minors. IV. Tree-width and well-quasi-ordering

| volume = 48

| year = 1990| doi-access = free

}}.

• {{citation

| last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)

| last2 = Seymour | first2 = P. D. | author2-link = Paul Seymour (mathematician)

| doi = 10.1016/0095-8956(86)90030-4

| issue = 1

| journal = Journal of Combinatorial Theory | series = Series B

| mr = 854606

| pages = 92–114

| title = Graph minors. V. Excluding a planar graph

| volume = 41

| year = 1986| doi-access = free

}}.

• {{citation

| last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)

| last2 = Seymour | first2 = P. D. | author2-link = Paul Seymour (mathematician)

| doi = 10.1016/0095-8956(86)90031-6

| issue = 1

| journal = Journal of Combinatorial Theory | series = Series B

| mr = 854607

| pages = 115–138

| title = Graph minors. VI. Disjoint paths across a disc

| volume = 41

| year = 1986| doi-access =

}}.

• {{citation

| last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)

| last2 = Seymour | first2 = P. D. | author2-link = Paul Seymour (mathematician)

| doi = 10.1016/0095-8956(88)90070-6

| issue = 2

| journal = Journal of Combinatorial Theory | series = Series B

| mr = 961150

| pages = 212–254

| title = Graph minors. VII. Disjoint paths on a surface

| volume = 45

| year = 1988| doi-access =

}}.

• {{citation

| last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)

| last2 = Seymour | first2 = P. D. | author2-link = Paul Seymour (mathematician)

| doi = 10.1016/0095-8956(90)90121-F

| issue = 2

| journal = Journal of Combinatorial Theory | series = Series B

| mr = 1046758

| pages = 255–288

| title = Graph minors. VIII. A Kuratowski theorem for general surfaces

| volume = 48

| year = 1990| doi-access =

}}.

• {{citation

| last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)

| last2 = Seymour | first2 = P. D. | author2-link = Paul Seymour (mathematician)

| doi = 10.1016/0095-8956(90)90063-6

| issue = 1

| journal = Journal of Combinatorial Theory | series = Series B

| mr = 1056819

| pages = 40–77

| title = Graph minors. IX. Disjoint crossed paths

| volume = 49

| year = 1990| doi-access = free

}}.

• {{citation

| last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)

| last2 = Seymour | first2 = P. D. | author2-link = Paul Seymour (mathematician)

| doi = 10.1016/0095-8956(91)90061-N

| issue = 2

| journal = Journal of Combinatorial Theory | series = Series B

| mr = 1110468

| pages = 153–190

| title = Graph minors. X. Obstructions to tree-decomposition

| volume = 52

| year = 1991| doi-access = free

}}.

• {{citation

| last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)

| last2 = Seymour | first2 = P. D. | author2-link = Paul Seymour (mathematician)

| contribution = Excluding a graph with one crossing

| editor1-last = Robertson | editor1-first = Neil

| editor2-last = Seymour | editor2-first = Paul

| pages = 669–675

| publisher = American Mathematical Society

| series = Contemporary Mathematics

| title = Graph Structure Theory: Proc. AMS–IMS–SIAM Joint Summer Research Conference on Graph Minors

| volume = 147

| year = 1993

| mr = 1224738

| doi = 10.1090/conm/147/01206| isbn = 978-0-8218-5160-9 }}.

• {{citation

| last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)

| last2 = Seymour | first2 = P. D. | author2-link = Paul Seymour (mathematician)

| doi = 10.1006/jctb.1994.1007

| issue = 1

| journal = Journal of Combinatorial Theory | series = Series B

| mr = 1256585

| pages = 72–106

| title = Graph minors. XI. Circuits on a surface

| volume = 60

| year = 1994| doi-access = free

}}.

• {{citation

| last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)

| last2 = Seymour | first2 = P. D. | author2-link = Paul Seymour (mathematician)

| doi = 10.1006/jctb.1995.1034

| issue = 2

| journal = Journal of Combinatorial Theory | series = Series B

| mr = 1339851

| pages = 240–272

| title = Graph minors. XII. Distance on a surface

| volume = 64

| year = 1995| doi-access = free

}}.

• {{citation

| last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)

| last2 = Seymour | first2 = P. D. | author2-link = Paul Seymour (mathematician)

| doi = 10.1006/jctb.1995.1006

| issue = 1

| journal = Journal of Combinatorial Theory | series = Series B

| mr = 1309358

| pages = 65–110

| title = Graph minors. XIII. The disjoint paths problem

| volume = 63

| year = 1995| doi-access = free

}}.

• {{citation

| last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)

| last2 = Seymour | first2 = P. D. | author2-link = Paul Seymour (mathematician)

| doi = 10.1006/jctb.1995.1042

| issue = 1

| journal = Journal of Combinatorial Theory | series = Series B

| mr = 1347339

| pages = 23–50

| title = Graph minors. XIV. Extending an embedding

| volume = 65

| year = 1995| doi-access = free

}}.

• {{citation

| last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)

| last2 = Seymour | first2 = P. D. | author2-link = Paul Seymour (mathematician)

| doi = 10.1006/jctb.1996.0059

| issue = 1

| journal = Journal of Combinatorial Theory | series = Series B

| mr = 1405708

| pages = 112–148

| title = Graph minors. XV. Giant steps

| volume = 68

| year = 1996| doi-access = free

}}

• {{citation

| last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)

| last2 = Seymour | first2 = P. D. | author2-link = Paul Seymour (mathematician)

| doi = 10.1016/S0095-8956(03)00042-X

| issue = 1

| journal = Journal of Combinatorial Theory | series = Series B

| mr = 1999736

| pages = 43–76

| title = Graph minors. XVI. Excluding a non-planar graph

| volume = 89

| year = 2003| doi-access =

}}.

• {{citation

| last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)

| last2 = Seymour | first2 = P. D. | author2-link = Paul Seymour (mathematician)

| doi = 10.1006/jctb.1999.1919

| issue = 1

| journal = Journal of Combinatorial Theory | series = Series B

| mr = 1710538

| pages = 162–210

| title = Graph minors. XVII. Taming a vortex

| volume = 77

| year = 1999| doi-access = free

}}.

• {{citation

| last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)

| last2 = Seymour | first2 = Paul | author2-link = Paul Seymour (mathematician)

| doi = 10.1016/S0095-8956(03)00067-4

| issue = 1

| journal = Journal of Combinatorial Theory | series = Series B

| mr = 1999737

| pages = 77–108

| title = Graph minors. XVIII. Tree-decompositions and well-quasi-ordering

| volume = 89

| year = 2003| doi-access =

}}.

• {{citation

| last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)

| last2 = Seymour | first2 = P. D. | author2-link = Paul Seymour (mathematician)

| doi = 10.1016/j.jctb.2003.08.005

| issue = 2

| journal = Journal of Combinatorial Theory | series = Series B

| mr = 2034033

| pages = 325–385

| title = Graph minors. XIX. Well-quasi-ordering on a surface

| volume = 90

| year = 2004| doi-access =

}}.

• {{citation

| last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)

| last2 = Seymour | first2 = P. D. | author2-link = Paul Seymour (mathematician)

| doi = 10.1016/j.jctb.2004.08.001

| issue = 2

| journal = Journal of Combinatorial Theory | series = Series B

| mr = 2099147

| pages = 325–357

| title = Graph minors. XX. Wagner's conjecture

| volume = 92

| year = 2004| doi-access = free

}}.

• {{citation

| last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)

| last2 = Seymour | first2 = Paul | author2-link = Paul Seymour (mathematician)

| doi = 10.1016/j.jctb.2008.08.003

| issue = 3

| journal = Journal of Combinatorial Theory | series = Series B

| mr = 2507943

| pages = 583–616

| title = Graph minors. XXI. Graphs with unique linkages

| volume = 99

| year = 2009| doi-access = free

}}.

• {{citation

| last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)

| last2 = Seymour | first2 = Paul | author2-link = Paul Seymour (mathematician)

| title = Graph minors. XXII. Irrelevant vertices in linkage problems

| volume = 102

| issue = 2

| pages = 530–563

| journal = Journal of Combinatorial Theory | series = Series B

| doi = 10.1016/j.jctb.2007.12.007

| mr = 2885434

| year = 2012| doi-access = free

| url = http://www.math.princeton.edu/~pds/papers/GM22/GM22.pdf

}}.

• {{citation

| last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)

| last2 = Seymour | first2 = Paul | author2-link = Paul Seymour (mathematician)

| doi = 10.1016/j.jctb.2009.07.003

| issue = 2

| journal = Journal of Combinatorial Theory | series = Series B

| mr = 2595703

| pages = 181–205

| title = Graph minors XXIII. Nash-Williams' immersion conjecture

| volume = 100

| year = 2010| doi-access = free

}}.

• {{citation

| last = Wagner | first = Klaus | author-link = Klaus Wagner (mathematician)

| journal = Deutsche Mathematik

| pages = 280–285

| title = Über eine Erweiterung des Satzes von Kuratowski

| volume = 2

| year = 1937}}.

Category:Graph minor theory

Category:Theorems in graph theory