TOPICS
Search

Minimum Vertex Cut


A minimum vertex cut of a graph is a vertex cut of smallest possible size.

A vertex cut set of size 1 in a connected graph corresponds to an articulation vertex.

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

Complete graphs have no vertex cuts since there is no subset of vertices whose removal disconnected a complete graph.

A single minimum vertex cut of a connected graph G can be found in the Wolfram Language using the function FindVertexCut[G].


See also

Articulation Vertex, Disconnected Graph, Edge Cut, k-Connected Graph, Mincut, Minimal Vertex Cut, Vertex Connectivity, Vertex Cut

Explore with Wolfram|Alpha

References

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. 149, 2000.

Cite this as:

Weisstein, Eric W. "Minimum Vertex Cut." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/MinimumVertexCut.html

Subject classifications