8 Vertex Elimination

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

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

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

  • The set of edges EE^{{\prime}} contains edges that connect all vertices in VGV(G) that were adjacent to vv.

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

  1. Removing vertex vv from VGV(G).

  2. Removing all edges that were incident upon vv from EGE(G).

  3. Adding edges to EGE(G) that connect all the vertices that were adjacent to vv.