Vertex and edge deletion, edge contraction, graph minors, subdivisions and topological minors

Let $G=(V,E)$ be a graph. For $v\in V$, vertex deletion gives $G-v:=G[V\setminus \{v\}]$. For $e\in E$, edge deletion gives $G-e:=(V,E\setminus \{e\})$. The same notation is used for deleting a set of vertices or edges.

For an edge $e=\{u,v\}$, contracting $e$ identifies $u$ and $v$. More precisely, take a new vertex $x_e$, put $V^{\mathrm{\prime }}=(V\setminus \{u,v\})\cup \{x_e\}$, and let $q:V\to V^{\mathrm{\prime }}$ send $u,v$ to $x_e$ and fix every other vertex. Then

$G\mathrm{/}e:=(V^{\mathrm{\prime }},\{q[f]:f\in E\setminus \{e\},\mathrm{\mid }q[f]\mathrm{\mid }=2\})\mathrm{.}$

The condition $\mathrm{\mid }q[f]\mathrm{\mid }=2$ deletes loops, while writing the edge family as a set merges parallel edges. Thus contraction returns a simple graph.

A graph $H$ is a minor of $G$ when it can be obtained by vertex deletions, edge deletions and edge contractions. Subdividing an edge $\{u,v\}$ replaces it by $\{u,x\}$ and $\{x,v\}$ for a new vertex $x$. A subdivision repeats this operation zero or more times. The graph $H$ is a topological minor of $G$ when some subdivision of $H$ is isomorphic to a subgraph of $G$ (Subgraphs, induced subgraphs and spanning subgraphs).