Given an edge xy of a graph G, the graph G/xy is obtained from G by contracting the edge xy; that is, to get G/xy we identify the vertices x and y and remove all loops and duplicate edges. A graph G obtained by a sequence of edge-contractions is said to be a contraction of G.

Adapted with permission of the author from by Béla Bollobás, published by Springer-Verlag New York, Inc., 1998.

Title edge-contraction
Canonical name Edgecontraction
Date of creation 2013-03-22 12:31:43
Last modified on 2013-03-22 12:31:43
Owner rspuzio (6075)
Last modified by rspuzio (6075)
Numerical id 5
Author rspuzio (6075)
Entry type Definition
Classification msc 05C99
Related topic TheoremOn3ConnectedGraphs
Defines contraction