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.