8 Vertex Elimination

Eliminating a vertex $v$ from the graph $G=(V,E)$ creates a reduced graph $G^{{\prime}}=(V^{{\prime}},E^{{\prime}})$ with the following characteristics:

• The set of vertices $V^{{\prime}}$ is the subset of $V(G)$ that does not contain $v$.

• The set of edges $E^{{\prime}}$ does not contain any edges that were incident upon $v$.

• The set of edges $E^{{\prime}}$ contains edges that connect all vertices in $V(G)$ that were adjacent to $v$.

In other words, you get $G^{{\prime}}$ from $G$ by

1. Removing vertex $v$ from $V(G)$.

2. Removing all edges that were incident upon $v$ from $E(G)$.

3. Adding edges to $E(G)$ that connect all the vertices that were adjacent to $v$.