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