Prove that no hamilton circuit for the graph exists

370 Views Asked by At

enter image description here

To prove this, I decided to start with vertex e, then two cases occur

Case 1: Use d-e-f, delete b-e and e-h at e. Use a-b-c and g-h-i. Delete at d, d-a (prevent subcircuit). Use g-d-e. Then at g, delete n-g and g-l. Use k-n-a and i-l-j. Delete at i, i-k and i-f. Use h-i-l and c-k-n. At a, delete a-j, use n-a-b and c-j-l. Now at c, there are 4 edges incident to c and nothing can be done about it so no hamilton circuit exists.

Case 2: Use b-e-f so at e, delete d-e and e-h. Use a-d-g and g-h-i. So at g, delete g-n and g-l. Use k-n-a and i-l-j. So at i, delete i-f and i-k. Use c-f-e and c-k-n. At a, delete a-j and a-b. Use c-j-l and e-b-c. Now c is required to be incident to 4 vertices and nothing can be done about it so no hamilton circuit exists.

So in both possible cases, no hamilton circuit exists so no hamilton circuit exists.

Is this correct? Is my reasoning okay?

1

There are 1 best solutions below

0
On BEST ANSWER

Your reasoning seems ok to me.

There is a much nicer way to prove this. It relies on the fact that apart from the two edges $km$ and $jl$ the graph is bipartite.

Consider the eight nodes $A=\{b,d,f,h,j,k,l,m\}$. There are only 5 other nodes $B=\{a,c,e,g,i\}$. Whichever order those A-nodes are visited during the Hamilton circuit, at most 5 times can they be separated by a B-node. Therefore there must be at least 3 occasions where an A-node is followed by another A-node. There are however only two edges connecting A-nodes together ($km$, $jl$) so no Hamilton circuit can exist.