Definition:Cut-Vertex
Jump to navigation
Jump to search
Definition
Let $G = \struct {V, E}$ be a connected graph.
Let $v$ be a vertex of $G$.
Then $v$ is a cut-vertex of $G$ if and only if the vertex deletion $G - v$ is a vertex cut of $G$.
That is, such that $G - v$ is disconnected.
Thus, a cut-vertex of $G$ is a singleton vertex cut of $G$.
Example
In the graph below, $C$ is a cut-vertex.
The edges $AC, BC, CD, CF$ are the edges which would be removed if $C$ were cut.
The graph would be separated into the two components $AB$ and $DEF$.
Also see
Sources
- 1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): $\S 2.4$: Cut-Vertices and Bridges