Show that graph G is not Hamiltonian

Question

Show that a graph G with vertex connectivity K(G) = 1 is NOT hamiltonian

How exactly can I do this?

Answer 1

The best way to go about it is to suppose it is Hamiltonian, think about what that implies and then arrive at a contradiction.

The contradiction will be arrived at if you think about the graph's connectivity.

Here is the proof:

Let $G $ be a Hamiltonian graph such that $\operatorname{K}(G) = 1$. By definition of Hamiltonian graph, there is a cycle in $G $ containing all vertices of $G $. Because $\operatorname {K}(G) = 1$ there exists a vertex that if removed, $G $ stops being connected. Let us delete that vertex from the graph. We just made the graph disconnected. But deleting that vertex from the cycle, we destroyed the cycle and leaving a path. Therefore any other two vertices remain connected and the path was not disconnected by deleting that vertex and $\operatorname {K}(G) \not= 1$ contradicting our hypothesis. Hence we cannot have that $G $ is Hamiltonian and $\operatorname {K}(G) = 1$.