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 .
definition
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,
or.
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 .