0
$\begingroup$

Is there any graph that all its vertices are cut vertices? I couldn't find a graph with this property? and if there is no such graph how can i prove that it does not exist.

$\endgroup$
  • $\begingroup$ The earlier question is about connected graphs, but it’s clear that if very connected graph has a non-cut vertex, then every graph has a non-cut vertex. $\endgroup$ – Brian M. Scott Apr 9 '15 at 18:25
1
$\begingroup$

There is no such (finite) graph.

Suppose such a graph $G$ existed. We may assume WLOG it is connected. For each vertex $v$, let $f(v)$ be the minimum number of vertices in the connected components of the graph $G - v$ obtained by deleting $v$. Take $v$ that minimizes $f$, and let $C$ be a connected component of $G - v$ with $f(v)$ vertices. At least one vertex $w$ of $C$ is adjacent to $v$. Now in $G - w$, one connected component must contain $v$, and this will also contain all other vertices not in $C$. Any other connected component of $G - w$ will therefore be a proper subset of $C$, so $f(w) < f(v)$, contradiction.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.