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