Definition:Edge Contraction

Definition

Let $G$ be an undirected graph.

Let $e \in \map E G$ be an edge of $G$.

Then the graph obtained by contracting $e$ in $G$, denoted by $G / e$, is the graph $H$ defined by:

$\map V H = \paren {\map V G \setminus e} \cup \set v$

$\map E H = \set {f \in \map E G: f \cap e = \O} \cup \set {u v: \exists f \in \map E G: u \in f \setminus e, f \cap e \ne \O}$

where $v \notin \map V G$ is a fresh object.

This article, or a section of it, needs explaining. In particular: A lot of the above - see talk page (in prep) You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Explain}} from the code.

Informally, it is the graph obtained from $G$ by replacing the vertices incident to $e$ with a single vertex adjacent to all their neighbors.

Also see

• Definition:Edge Deletion, which is the removal of an edge.

• Definition:Graph Minor, which is a graph obtained from another by contraction, edge deletion, or isolated vertex deletion.