Edge Contraction

In a graph , contraction of an edge  with endpoints  is the replacement of  and  with a single vertex such that edges incident to the new vertex are the edges other than  that were incident with  or . The resulting graph, denoted , has one less edge than .

Graph minors are defined in terms of edge contractions.

REFERENCES

Bollobás, B. Modern Graph Theory. New York: Springer-Verlag, 1998.Diestel, R. Graph Theory, 3rd ed. New York: Springer-Verlag, 1997.

West, D. B. Introduction to Graph Theory, 2nd ed. Upper Saddle River, NJ: Prentice Hall, p. 84, 2001.