0
$\begingroup$

Tutte proved the famous result: Every planar 4-connected graph has a hamiltonian cycle. But I read in Section 111.6.5 on book Eulerian Graphs and Related Topics that the author Herbert Fleischner places great importance on the impact of simplicity on this theorem. Even its proof in the end is based on refuting simplicity. What puzzles me is that multiple edges seem not to affect vertex connectivity and planarity. Why is the condition of simple graphs used here? enter image description here

Are there counterexamples to Tutte's results for 4-connected planar graphs with multiple edges? That is to say, are there 4-connected planar non-hamilton multi-graphs?

P.S. I have also asked this question on Mathematics Stack, but have not received a response yet, so I posted the same question on this platform.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ But if we ignore multiple edges, is not it still 4-connected and planar? $\endgroup$
    – Fedor Petrov
    Commented Mar 28 at 10:34
  • $\begingroup$ I think it keeps same connectivity and planarity. Maybe I miss something. That is also why I don't understand the proof considering simplicity. $\endgroup$
    – Licheng Zhang
    Commented Mar 28 at 13:06

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .