I came across two definitions which operations are allowed to construct a minor from a given graph.
One definition allows edge contractions and edge deletions, the other additionally vertex deletions.
- Can any vertex deletion also be achieved by edge deletions and edge contractions ?
- If not, which definition is the proper one to recognize, for example, planar graphs ?
The wikipedia page on graph minors states "$H$ is called a minor of the graph $G$ if $H$ can be formed from $G$ by deleting edges and vertices and by contracting edges."
I'd say the deleting vertex part is mostly redundant, since you can effectively delete through edge deletions and contractions: delete all of its edges except one, then contract along that final edge. However, technically you can't get rid of an isolated vertex in this manner, so the vertex deletion is necessary in that rather trivial case.