for a graph and an edge , the contraction of in is an operation that produces the graph , where
- , and
- the part of containing and the part of containing are merged (and is removed) to form a part .
the graph obtained from by contracting is denoted .
like deletions, the order of contractions of edges does not affect the result. for a set of edges, the graph obtained by contracting the edges of is denoted .