8 Vertex Elimination

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

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

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

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

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

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

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

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