Prove that if a graph $G$ has an independent vertex subset $X \subseteq V G$ such that $|X| > |N (X)|$ then $G$ is non-Hamiltonian.

Question

Prove that if a graph $G$ has an independent vertex subset $X \subseteq V G$ such that $|X| > |N (X)|$ then $G$ is non-Hamiltonian.

I have tried to delete m vertices in order to produce m component, but it doesn't work. can someone please help!

Answer 1

@bof

Choose an orientation for the cycle, making it a directed cycle. Then you can match each vertex of the independent set X with its neighbor in the forward direction, which shows that $|X|≤|N(X)|$