3
$\begingroup$

We know that graph is connected when there is a path between every pair of vertices. A graph that is not connected is disconnected. A graph G is said to be disconnected if there exist two nodes in G such that no path in G has those nodes as endpoints. A cut vertex is a vertex that when removed (with its boundary edges) from a graph creates more components than previously in the graph.

Do we have a graph that each vertex is a cut vertex??

$\endgroup$
  • $\begingroup$ An infinite graph with vertices $v_n$ and edges $v_nv_{n+1}$ for $n\in\mathbb Z.$ $\endgroup$ – bof Oct 7 '17 at 6:12
  • $\begingroup$ The graph with one vertex (its removal will cause you to go from a graph with one connected component to zero connected components). $\endgroup$ – benguin Oct 7 '17 at 6:17
3
$\begingroup$

The typical image of the number line, an infinite horizontal line formed from vertices at the integers and edges connecting each integer to its nearest two neighbors, has the property that every vertex is a cut vertex.

$\endgroup$
2
$\begingroup$

Assuming $G\;$is finite, it's not possible for every vertex to be a cut point.

Without loss of generality, we can assume $G\;$is connected, since the removal of a vertex only affects one component.

If $G\;$has order one, the solo vertex of $G\;$would not be a cut point, so the claim holds.

Next, suppose $G\;$has order at least $2$.

Choose vertices $p,q\;$such that $d(p,q)\;$is equal to the diameter of $G$.

Claim $p\;$is not a cut point of $G$.

Let $H = G-p,\;$and let $v \in H$.

Since $d(p,q)\;$is maximal in $G$, there must be a path in $G\;$from $q\;$to $v\;$which doesn't pass though $p$.

But then that path is still a path in $H$.

It follows that $H\;$is connected.

Thus, as claimed, $p\;$is not a cut point of $G$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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