Graph Minors

Take a graph and remove some edges. Then contract some edges so that their ends become fused. What you get is a minor of the original graph.

There are some interesting results about graph minors. K5 is the graph made of 5 vertices which are all connected (requiring 10 edges). K3,3 is two sets of three vertices, each vertex in one set connected to each vertex in the other (requires 9 edges).

• Neither K5 nor K3,3 can be drawn on a plane without crossing edges.
• Clearly any graph with K5 as a minor also cannot be embedded in a plane.
• Clearly the same is true for any graph with K3,3 as a minor.
• Kuratowski's theorem says that the converse is also true, that any graph that has neither K5 nor K3,3 as a minor can be drawn on a plane without any edges crossing.
  • This is an astonishing result.

An even deeper result says that in any infinite sequence of finite graphs you can always find one graph that is a minor of another.

Deciding whether G1 is a minor of G2 is NpHard.

References:

• http://mathworld.wolfram.com/GraphMinor.html
• http://planetmath.org/encyclopedia/MinorOfAGraph.html
• http://planetmath.org/encyclopedia/GraphMinorTheorem.html
• http://mathworld.wolfram.com/KuratowskiReductionTheorem.html

This paper gives some concrete algorithmic implications of the work:

• http://www.cs.utk.edu/~langston/courses/cs594-fall2003/BL.pdf

---

CategoryMath