1

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 Answers1

2

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.

Jaap Scherphuis
  • 13,660