Edge Cut

An edge cut (Holton and Sheehan 1993, p. 14; West 2000, p. 152), edge cut set, edge cutset (Holton and Sheehan 1993, p. 14), or sometimes simply "cut set" or "cutset" (e.g., Harary 1994, p. 38) of a connected graph, is a set of edges of which, if removed (or "cut"), disconnects the graph (i.e., forms a disconnected graph).

An edge cut set of size 1 corresponds to a graph bridge.

The size of a minimum edge cut in a connected graph G gives the edge connectivity lambda(G).

An edge cut set of smallest size in a given connected graph g can be found in the Wolfram Language using the function FindEdgeCut[g].

For a not-necessarily-connected graph G, an edge cut is an edge set S such that G-S has more connected components than G (Gross and Yellen 2006, p. 81).

See also

Cyclic Edge Connectivity, Disconnected Graph, Edge Connectivity, Graph Bridge, Minimum Edge Cut, Vertex Cut

Explore with Wolfram|Alpha


Gross, J. T. and Yellen, J. Graph Theory and Its Applications, 2nd ed. Boca Raton, FL: CRC Press, 2006.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, p. 38, 1994.Holton, D. A. and Sheehan, J. The Petersen Graph. Cambridge, England: Cambridge University Press, p. 14, 1993.Skiena, S. "Reconstructing Graphs from Cut-Set Sizes." Info. Proc. Lett. 32, 123-127, 1989.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, p. 152, 2000.

Cite this as:

Weisstein, Eric W. "Edge Cut." From MathWorld--A Wolfram Web Resource.

Subject classifications