Existance of a vertex which is not cut-vertex in a simple connected graph

303 Views Asked by At

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$ ?

1

There are 1 best solutions below

0
On BEST ANSWER

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.