Prove about Hamiltonian

Question

I need to prove if graph $G$ contains a cut vertex, then it is not Hamiltonian. I get that it wouldn't be Hamiltonian because to be Hamiltonian you have to have a Hamiltonian cycle and if you have a cut vertex there's no possible way to have a cycle including that vertex. Is it true argument ?

Answer 1

Let $v$ be any cut vertex of a graph $G$. Then $G-v$ is not connected, so there are vertices $x$ and $y$ that are in different components of $G-v$. Suppose that $G$ has a Hamiltonian cycle; we can start the cycle at $v$, and since it must pass through both $x$ and $y$, we may as well assume that after leaving $v$, it passes through $x$ before it reaches $y$. The part of the cycle from $x$ to $y$ is then a path in $G$ from $x$ to $y$, and since the cycle is Hamiltonian, that path does not pass through $v$. This path is not affected by the removal of $v$, so $x$ and $y$ are in the same component of $G-v$, contradicting our choice of $x$ and $y$. Thus, $G$ cannot have a cut vertex.

With a little rearrangement you can turn this into a direct proof of the contrapositive of your theorem, i.e., a proof that if $G$ has a Hamiltonian cycle, and $v$ is any vertex of $G$, then $G-v$ is connected, so $v$ cannot be a cut vertex of $G$. This actually seems to me to be a slightly easier way to think about it: removing a vertex from a cycle does not disconnect the cycle, and if the cycle contains every vertex of the graph, then removing a vertex cannot disconnect the graph.

Answer 2

Basically, yes. If you remove the cut vertex, the graph falls into disconnected pieces. But any Hamiltonian cycle may be converted to a Hamiltonian path (in a different graph) by removing any single vertex; remove the cut vertex and we get a disconnected graph, which cannot have a Hamiltonian path.