TOPICS
Search

Edge Contraction


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

Edge contraction is implemented in the Wolfram Language as EdgeContract[g, e] or EdgeContract[g, elist].

Graph minors are defined in terms of edge contractions.


See also

Edge Splitting, Graph Minor, Vertex Contraction

Explore with Wolfram|Alpha

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.

Referenced on Wolfram|Alpha

Edge Contraction

Cite this as:

Weisstein, Eric W. "Edge Contraction." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/EdgeContraction.html

Subject classifications