A graph is a *minor* of a graph if is isomorphic to a graph obtained by contracting edges, removing edges and/or removing isolated vertices from . For example the graph with two vertices and one edge is a minor of any graph with at least one edge.

*Problem: *Fix a graph . Find a polynomial time algorithm that decides if a given graph has as one of its minors. The algorithm must be polynomial in the number of vertices of .

Notice that such an algorithm proves that planarity of a graph can be decided in polynomial time.

Advertisements