Editing Graph minor (section)

==Minor-closed graph families== <!-- "Minor-closed graph family" redirects here -->
{{details|topic=minor-closed graph families, including a list of some|Robertson–Seymour theorem}}

Many families of graphs have the property that every minor of a graph in ''F'' is also in ''F''; such a class is said to be ''minor-closed''. For instance, in any [[planar graph]], or any [[graph embedding|embedding]] of a graph on a fixed [[2-manifold|topological surface]], neither the removal of edges nor the contraction of edges can increase the [[genus (mathematics)|genus]] of the embedding; therefore, planar graphs and the graphs embeddable on any fixed surface form minor-closed families.

If ''F'' is a minor-closed family, then (because of the well-quasi-ordering property of minors) among the graphs that do not belong to ''F'' there is a finite set ''X'' of minor-minimal graphs. These graphs are [[Forbidden graph characterization|forbidden minors]] for ''F'': a graph belongs to ''F'' if and only if it does not contain as a minor any graph in ''X''. That is, every minor-closed family ''F'' can be characterized as the family of ''X''-minor-free graphs for some finite set ''X'' of forbidden minors.<ref name="rst"/>
The best-known example of a characterization of this type is [[Wagner's theorem]] characterizing the planar graphs as the graphs having neither K<sub>5</sub> nor K<sub>3,3</sub> as minors.<ref name="w"/>

In some cases, the properties of the graphs in a minor-closed family may be closely connected to the properties of their excluded minors. For example a minor-closed graph family ''F'' has bounded [[pathwidth]] if and only if its forbidden minors include a [[tree (graph theory)|forest]],<ref>{{harvtxt|Robertson|Seymour|1983}}.</ref> ''F'' has bounded [[tree-depth]] if and only if its forbidden minors include a disjoint union of [[path graph]]s, ''F'' has bounded [[treewidth]] if and only if its forbidden minors include a [[planar graph]],<ref>{{harvtxt|Lovász|2006}}, Theorem 9, p.&nbsp;81; {{harvtxt|Robertson|Seymour|1986}}.</ref> and ''F'' has bounded local treewidth (a functional relationship between [[diameter (graph theory)|diameter]] and treewidth) if and only if its forbidden minors include an [[apex graph]] (a graph that can be made planar by the removal of a single vertex).<ref>{{harvtxt|Eppstein|2000}}; {{harvtxt|Demaine|Hajiaghayi|2004}}.</ref> If ''H'' can be drawn in the plane with only a single crossing (that is, it has [[crossing number (graph theory)|crossing number]] one) then the ''H''-minor-free graphs have a simplified structure theorem in which they are formed as clique-sums of planar graphs and graphs of bounded treewidth.<ref>{{harvtxt|Robertson|Seymour|1993}}; {{harvtxt|Demaine|Hajiaghayi|Thilikos|2002}}.</ref> For instance, both ''K''<sub>5</sub> and ''K''<sub>3,3</sub> have crossing number one, and as Wagner showed the  ''K''<sub>5</sub>-free graphs are exactly the 3-clique-sums of planar graphs and the eight-vertex [[Wagner graph]], while the ''K''<sub>3,3</sub>-free graphs are exactly the 2-clique-sums of planar graphs and&nbsp;''K''<sub>5</sub>.<ref>{{harvtxt|Wagner|1937a}}; {{harvtxt|Wagner|1937b}}; {{harvtxt|Hall|1943}}.</ref>