Pairs of edge disjoint Hamiltonian circuits in 5-connected planar graphs (Q1124606): Difference between revisions

B. Grünbaum and J. Malkevitch asked in a 1976 paper whether a 5- connected planar graph can have a pair of edge-disjoint Hamiltonian circuits. This paper shows the answer is negative: A procedure is provided for constructing infinitely many 5-connected, 5-regular planar graphs in which every two Hamiltonian circuits have edges in common. The construction starts with a cubic, 3-connected, cyclically 5-connected planar graph H. A graph is cyclically k-connected if at least k edges must be removed to create two components each with a cycle. By the Four Color Theorem, H is factorizable into three 1-factors \(F_ 1\), \(F_ 2\) and \(F_ 3\). We replace each edge of \(F_ 1\) and \(F_ 2\) by a pair of parallel edges and obtain a 5-regular multigraph \(H_ 5\). In turn each vertex of \(H_ 5\) is replaced in a specified way by a 5-connected 5- regular planar graph with a vertex g deleted. This new graph, denoted \(H(G_ g)\), is a counterexample if H is non-Hamiltonian. It is known that there are infinitely many such H. A typographical correction is needed in Lemma 3.