# Edge contraction Example of an edge contraction with the graphs (left) and (right).${\ displaystyle G_ {1}}$ ${\ displaystyle G_ {2}}$ 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. ${\ displaystyle G_ {1} = (V_ {1}, E_ {1})}$ ${\ displaystyle e = \ {u, v \}}$ ${\ displaystyle G_ {1}}$ ${\ displaystyle V_ {1}}$ ${\ displaystyle E}$ ${\ displaystyle \ {u, v \}}$ ${\ displaystyle w}$ • ${\ displaystyle E = {\ bigg \ {} \ {w, x \} {\ bigg |} \ forall _ {x \ in V_ {1} \ setminus \ {u, v \}} \ {u, x \ } {\ mbox {or}} \ {v, x \} {\ mbox {edge of G}} {\ bigg \}}}$ if there is a graph without multiple edges,${\ displaystyle G_ {1}}$ or.

• ${\ displaystyle E (\ {w, x \}) = E_ {1} (\ {u, x \}) + E_ {1} (\ {v, x \})}$ for all and for all if is a graph with multiple edges.${\ displaystyle x \ in V_ {1} \ {u, v \}}$ ${\ displaystyle E (\ {x, y \}) = 0}$ ${\ displaystyle x, y \ in V_ {1} \ {u, v \}}$ ${\ displaystyle G_ {1}}$ 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 . ${\ displaystyle G_ {2} = (V_ {2}, E_ {2})}$ ${\ displaystyle G_ {1}}$ ${\ displaystyle G_ {2} = G_ {1} - \ {u, v \} + w + E}$ ${\ displaystyle G_ {1}}$ ${\ displaystyle \ {u, v \}}$ ${\ displaystyle w}$ ${\ displaystyle G_ {2}}$ ${\ displaystyle G_ {1}}$ 