TOPICS
Search

Vertex Cut


A vertex cut, also called a vertex cut set or separating set (West 2000, p. 148), of a connected graph G is a subset of the vertex set S subset= V(G) such that G-S has more than one connected component. In other words, a vertex cut is a subset of vertices of a connected graph which, if removed (or "cut")--together with any incident edges--disconnects the graph (i.e., forms a disconnected graph).

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

A vertex cut of smallest size in a given connected graph G is called a minimum vertex cut and can be found in the Wolfram Language using the function FindVertexCut[G].

The size of a minimum vertex cut in a connected graph G gives the vertex connectivity kappa(G). However, because complete graphs have no vertex cuts (i.e., there is no subset of vertices whose removal disconnected a complete graph), a convention is needed to assign them a vertex connectivity. The convention of letting vertex connectivity kappa(K_n)=n-1 for the complete graph K_n allows most general results about connectivity to remain valid on complete graphs (West 2001, p. 149).

The number of vertex cuts in a connected graph G with vertex count |G| is related to the number of connected (non-null) vertex-induced subgraphs by

 |vertex cuts|=2^(|G|)-|connected induced subgraphs|-1.

For a not-necessarily-connected graph, a vertex cut of a graph G is a vertex set S such that G-S has more connected components than G (Gross and Yellen 2006, p. 81).


See also

Articulation Vertex, Disconnected Graph, Edge Cut, Graph Toughness, k-Connected Graph, Minimum Vertex Cut, Vertex Connectivity

Explore with Wolfram|Alpha

References

Gross, J. T. and Yellen, J. Graph Theory and Its Applications, 2nd ed. Boca Raton, FL: CRC Press, 2006.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. "Vertex Cut." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/VertexCut.html

Subject classifications