# Graph minors

A graph $H$ is a minor of a graph $G$ if $H$ is isomorphic to a graph obtained by contracting edges, removing edges and/or removing isolated vertices from $G$. 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 $H$. Find a polynomial time algorithm that decides if a given graph $G$ has $H$ as one of its minors. The algorithm must be polynomial in the number of vertices of $G$.

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