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 smallest size in a given graph  can be found in the Wolfram Language using the function FindEdgeCut[g]. An edge cut set of size 1 corresponds to a graph bridge.

---

REFERENCES

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.

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength