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).
See also Cyclic Edge Connectivity ,
Disconnected Graph ,
Edge
Connectivity ,
Graph Bridge ,
Minimum
Edge Cut ,
Vertex Cut
Explore with Wolfram|Alpha
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
Subject classifications