Hamiltonian graph and connected components 
Let $G = (V, E)$ be a Hamiltonian graph and $A \subseteq V$. Prove that the graph obtained from $G$ by removing all the vertices in $A$ has at most $|A|$ connected components.

This seems a bit counter-intuitive to me. How can removing $|A|$ vertices can produce a graph with $|A|$ of connected components? Any ideas?
 A: Note that this proposition can be false if $G$ is not hamiltonian. Consider a star with $n$ vertices. If you remove the center, you are left with $n-1$ connected components (the isolated vertices). 

Consider first a graph $G$ which is a cycle $C$ (then it is a hamiltonian graph). If you remove $A$ from $C$, the worse case scenario is that none of the vertices in $A$ is adjacent in $C$. In this case, you can check that removing $A$ from $C$ leaves $\vert A\vert$ connected components. You can prove this formally using induction. To get the idea, think for instance in a cycle with 4 vertices, what happens if you remove 2 nonadjacent vertices? and if you remove 2 adjacent vertices? or if you remove 3 vertices? or 1? or 4?
Now, if $G$ is a hamiltonian graph, it contains a cycle $C$ which has all the vertices. If you remove $A$ from $G$, we already know $C$ has at most $\vert A\vert$ connected components. Since there may be edges in $G-A$ between those components of $C-A$, the graph $G-A$ can only have less or equal connected components than the cycle $C-A$.
