Edge contraction

from Wikipedia, the free encyclopedia
Example of an edge contraction with the graphs (left) and (right).

In graph theory , edge contraction or contraction denotes a basic operation on graphs . An edge e is removed and the two adjacent nodes are combined to form a new node w .


Let be an undirected graph, an edge of and w a vertex that does not belong to . Define as the set of edges between the remaining nodes of the graph and the nodes to be removed that are redirected to the new node, i.e.

  • if there is a graph without multiple edges,


  • for all and for all if is a graph with multiple edges.

It is said that the graph comes from by contraction of e to w if . The nodes and all involved edges are removed from, and then the new node and the deflected edges are added. The graph is a minor of the graph .