# Questions about an “almost” 4-connected graph

How would this graph be classified? And what properties does it have? What would be a natural thing to study with this graph? I know it has 40 nodes. It's undirected. It's planar if I'm not mistaken. Also this graph looks like it's 4-connected except for the 4 outer most nodes.

I read on Wikipedia that: "4-connected planar graphs are always Hamiltonian by a result due to Tutte, and the computational task of finding a Hamiltonian cycle in these graphs can be carried out in linear time." Are 4-connected planar graphs somehow easier to compute Hamiltonian cycles for?

I'm wondering if that result is valid for this graph because 4 nodes have degree 6, while the others have degree 4. Thanks for your help.

• It is very easy to find a Hamiltonian cycle in this graph. First find a cycle in the inner 6x6 grid graph. Then replace four of the outer edges with detours to the 4 extreme nodes. – Jaap Scherphuis May 29 '18 at 8:31
• Or add four edges to the outside connecting the extreme nodes? – Ultradark May 30 '18 at 0:27
• I don't understand what you mean - that would be changing the graph. I'm talking about finding a Hamiltonian cycle in the exact graph you pictured. If you want to to ask about a different graph, you should ask a different question. – Jaap Scherphuis May 30 '18 at 7:03