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.
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:
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.
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.
Oct 20 at 17:54
I’ve tried for more than two hours, but I can’t seem to think about this intuitively.
Oct 20 at 18:01
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|.