含有两个分离三角形的极大平图有一个Hamilton路

摘要

一个图若包含Hamilton圈,则这个图是Hamilton图.Whitney已经证明了没有分离三角形的极大平图是Hamilton图.一个三角形若删去其顶点后使图不连通,则这个三角形称为分离三角形.Chuiyuan Chen证明了仅含有一个分离三角形的极大平图仍然是Hamilton图.我们将证明含有两个分离三角形的极大平图有一个Hamilton路.%A graph is hamiltonian if it has a hamiltonian cycle. A classical theorem of Whitney indicates that any maximal planar graph with no separatining triangles is hamiltonian. Where a separating triangle is a triangle that removal separates the graph. Chuiyuan Chen proved that any maximal planar graph with only one separating triangle is still hamiltonian. It's proved that any maximal planar graph with two separating triangles has a hamiltonian path.