TOPICS

# 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 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

More things to try:

## 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