# Proving non-existance of a Hamiltonian circuit when separated into multiple components

The Theorem I have to prove is the following

Prove that if there exists a non-empty proper subset S of graph G such that G-S has more components than |S|, then G is non-Hamiltonian

I’m not sure where to start.

Attempt

A graph is Hamiltonian if it contains a Hamiltonian cycle. i.e. If there exists a path in G (for |G| = n) of the form:
1-2-3-4-……-n-1

where 1,2,3,… are the vertices of the graph

I’m thinking of maybe doing a proof by contradiction:

Assume that there is a Hamiltonian graph such that when it is separated by S, there are more than |S| components.

I don’t know where to go from here.

I would appreciate any help.

Thank You

=================

You must distinguish whether, in your case, Hamiltonian mean containing a Hamiltonian path or cycle. I think you mean a path. Have you first come up with an intuition about why the statement is true? This is the 1st step, then comes the writing. Try drawing a set SS, with more components, and look at what a Hamiltonian path must do. It has to enter each component through a vertex of SS, then exit through a different vertex of SS.
– Manuel Lafond
Oct 20 at 17:52

Yeah, sorry. I meant to say cycle.
– The_Questioner
Oct 20 at 17:54