### Abstract

A graph is hamiltonian if it has a hamiltonian cycle. It is well-known that Tutte proved that any 4- connected planar graph is hamiltonian. It is also well-known that the problem of determining whether a 3-connected planar graph is hamiltonian is NP-complete. In particular, Chvatal and Wigderson had independently shown that the problem of determining whether a maximal planar graph is hamiltonian is NP-complete. A classical theorem of Whitney says that any maximal planar graph with no separating triangles is hamiltonian, where a separating triangle is a triangle whose removal separates the graph. Note that if a planar graph has separating triangles, then it can not be 4-connected and therefore Tutte's result can not be applied. In this paper, we shall prove that any maximal planar graph with only one separating triangle is still hamiltonian.

Original language | English |
---|---|

Pages (from-to) | 79-86 |

Number of pages | 8 |

Journal | Journal of Combinatorial Optimization |

Volume | 7 |

Issue number | 1 |

DOIs | |

State | Published - 1 Mar 2003 |

### Keywords

- Hamiltonian cycle
- Maximal planar graph
- NP-complete
- Planar graph
- Separating triangle