$\nexists$ A hamiltonian closed trail $\Rightarrow $ $\exists x_0 \in V(G)$ such that $\textrm{#\{connected components of }G-\{x_0\}\} \geq 3 $

Question

I'm trying to characterize the hamiltonian paths with the following property:

Given $G$ a connected graph and $K(G)$ the number of connected components of $G$ then

$\exists x_0 \in V(G) \textrm{ s.t. } K(G-\{x_0\})\geq 3 \Leftrightarrow \nexists \textrm{ a hamiltonian trail}$

I've been able to prove the implication to the right but I've got stuck on the implication right to left.

Given $G=(V,A)$ a connected graph and let $K(G-\{x_0\})$ be the number of connected components of $G-\{x_0\}$. Then,

$\nexists$ A hamiltonian trail $\Rightarrow $ $\exists x_0 \in V(G)$ such that $K(G-\{x_0\}) \geq 3 $

To prove this, I've tried the following way, first, let's rewrite the statement to prove in a way that seems easier to work with.

What I need to prove is the same as,

$$\nexists x\in V(G) \textrm{ such that }K(G-\{x\})\geq3 \Rightarrow \exists \textrm { a hamiltonian trail}$$

Now, lets define $C:=\{x\in V(G) : K(G-\{x\})=2\}$ and $\{A_i\}_{i\in \{1,...,k\}}$ the connected components of $G-C$ (we know that #${C=k-1}$).

Now we know that for every vertex $x\in A_i$, $K(A_i-\{x\})=1$. Knowing this, is it possible to find a hamiltonian trail that starts and ends in any given two points of $A_i$?

Ive got stuck in this last part of the prove and I can't seem to continue from there or to disprove is.

Could anyone give me some tips on how to prove that or some counter examples on why that's not true?

Thanks in advance

Answer 1

The second implication is not true. It is enough to find a $2$-connected graph without a Hamiltonian trail. Can you find one?

For example, you can take two vertices and draw four internally disjoint paths between them.

Heuristically, we expect that it is "difficult" to decide whether there is a Hamiltonian trail in a given graph (that is, this is an NP-complete problem), while the condition on the left is "easy to verify" (that is, it can be done in polynomial time).