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

I’ve tried for more than two hours, but I can’t seem to think about this intuitively.

– The_Questioner

Oct 20 at 18:01

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

1 Answer

1

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

Let C1,…,CkC_1, …, C_k be components of G−SG-S, and suppose that k>|S|k \gt |S|. If G is not a connected graph, there is no Hamiltonian cycles. So suppose that G is connected. Hence, every component of G−SG-S must have a neighbor in S.

For sake of contradiction, suppose that C∗C^* is a Hamiltonian cycle of GG. Give an arbitrary orientation to edges of C∗C^* Let xix_i be the last vertex of SS, visited in C∗C^*, before visiting a vertex of CiC_i (1≤i≤k)(1 \leq i \leq k). x1,x2,…,xkx_1, x_2, …, x_k are distinct vertices in SS. A countradiction with k>|S|k \gt |S|.