Let $G=(V,E)$ be a simple connected graph with at least two vertices. Is it true that there always exist a vertex which is not cut-vertex in $G$ ?
2026-04-19 13:00:37.1776603637
Existance of a vertex which is not cut-vertex in a simple connected graph
303 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
Do you know about the block structure of a graph? Each block is a maximal $2$-connected component, two blocks intersect in at most one vertex, which then has to be a cut-vertex of the graph. If $G$ is simple each block contains at least $2$ vertices. The block structure is tree. A block that corresponds to a leaf of the tree contains only one cut-vertex and hence has to contain a vertex which is not a cut-vertex. So yes, there always exist non cut-vertices in a simple graph.
This is no longer true for non-simple graphs, simple counter example: 2 vertices, a single edge between them and a loop at each vertex.