A graph minor 
of a graph 
is a graph for which a copy of 
can be obtained from 
via repeated edge deletion
and/or edge contraction.
Wagner's theorem states that a graph is nonplanar iff it has the complete graph 
or the complete
bipartite graph 
as a minor. Tutte three-edge-coloring
conjecture asserts that every snark has the Petersen
graph as a minor.
The determination of graph minors is an NP-hard problem for which no good algorithms are known, although brute-force methods such as those due to Robertson, Sanders, and Thomas exist.
For any fixed graph 
,
it is possible to test whether 
is a minor of an given graph 
in polynomial time, so if a forbidden minor characterization
is available, then any graph property which is preserved by deletions and contractions
may be recognized in polynomial time (Fellows and Langston 1988, Robertson and Seymour
1995).
As of 2022, the plane and projective plane are the only surfaces for which a complete list of forbidden minors is known for graph embedding (Mohar and Škoda 2020).
A graph 
is called a topological minor of a graph 
if a graph expansion of
is isomorphic to a subgraph of 
. Every topological minor is also a minor,
but the converse is not necessarily true.
