Any Maximal Planar Graph With Two Separating Triangles Has A Hamilton Path

A graph is hamiltonian if it contains a hamiltonian cycle. It is well-known that A maximal planar graph with at least four vertices is 3-connected. The problem of determining whether a 3-connected planar graph is hamiltonian is NP-complete and Chvatal and Wigderson also had independently shown that the problem of determining whether a maximal planar graph is hamiltonian is NP-complete. So it is of certain interest that the problem of determining whether a maximal planar graph is hamiltonian. A classical theory 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 ) . It is well-known that Tutte proved that 4-connected planar graph is hamiltonian. Tutte's result can be views as a generalization of Whitney's result since any maximal planar graph with at least five vertices and with no separating triangles is 4-connected. Note that if a maximal planar graph has separating triangles, then it can not be 4-connected and therefore Tutte's result can not be applied. Chen Chuiyuan had proved that any maximal planar graph with only one separating triangle is still hamiltonian. This paper mainly researchs the maximal planar graph with two separating triangles. The main results are listed as follows:Theorem 3.1 If G is a maximal planar graph with two separating triangles, then G has a hamiltonian path.Theorem 3.2 If G is a maximal planar graph with two separating triangles and two separating triangles has a common edge, then G is hamiltonian.Theorem 3.3 If a triangulation T with only one separating triangle has at most seven boundary vertices, then it has a hamiltonian path.