TOPICS

# 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 gives the edge connectivity .

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

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

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

## Explore with Wolfram|Alpha

More things to try:

## References

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. https://mathworld.wolfram.com/EdgeCut.html