Just one vertex not in a cycle means there is a vertex cut?

Question

I saw this assertion:

Any connected graph $G$ with $|V(G)| \geq 3$ and at least $2$ vertices that are not in a cycle must have a vertex cut

and realise that we just need one vertex not in any cycle. I don't know if I made a mistake or my claim is ok:

• First, if $G$ does not have a cycle we are done because every vertex that is not a leaf is a vertex cut
• So let $C$ be a cycle and $v_1$ a vertex such that $v_1u_1 \in E(G)$ for some $u_1 \in C$ and $v_1$ is not in any cycle. These $C$,$v_1$ exists because if we have any vertex $v$ out of a cycle, we take a path $P$ between $v$ and some cycle $C$, minimal in this sense (so $P$ does not go through any other cycle). Then $P \cap C =\{u_1\}$ with $u_1 \in C$ and $u_1v_1 \in E\,$ for some $v_1\in P$, that is not in any cycle.
• For any $u_2 \in C$ there is no $(v_1,u_2)-$path that do not use $u_1$. Otherwise $u_1v_1Pu_2u_1$ would be a cycle that contains $v_1$. Then $u_1$ is a vertex cut (it separates $v_1$ from $C$)

is this ok? or am I missing something?

Answer 1

You are correct, and to make it even easier:

• For the graph $G$ with $|V(G)|\geq 3$ find a vertex $a$ not in any cycle.
• If $a$ has degree $1$ (a leaf), its sole adjacent vertex is a cut vertex, separating $a$ from the rest of $G$
• If $\text{deg}(a)>1$, $a$ is a cut vertex, since there is no other path between any two of its adjacent vertices, otherwise $a$ would be in a cycle.

Answer 2

Your claim is correct.

I suspect that the result you are thinking of is the following:

In a connected graph with $|V(G)|\ge 3$ and no cutpoints, there is a cycle containing any two given points. (Whitney 1927) .

This is actually consistent with your claim since if a connected graph with $|V(G)|\ge 3$ has no cycle through a vertex $u$ then it can have no cycle through a pair of vertices $u,v$ and therefore it is not 2-connected i.e. it has a cutpoint.