HAMILTON CIRCUITS OF CONVEX TRIVALENT POLYHEDRA (UP TO 18 VERTICES) BY JOSHUA LEDERBERG Reprinted from the AmMeRicAN MATHEMATICAL MONTHLY Vol. 74, No. 5, May, 1967 HAMILTON CIRCUITS OF CONVEX TRIVALENT POLYHEDRA (UP TO 18 VERTICES) JOSHUA LEDERBERG, Stanford University School of Medicine In a study of the graphs of chemical structures [1, 2|, it became of interest to ascertain the Hamilton circuits (a closed circuit of edges through all the vertices) of trivalent graphs, and especially of the convex polyhedra. Tait [3] had conjectured that these polyhedra always had Hamilton circuits—for brevity we will now say had circuits. In [4], however, Tutte has demonstrated a counter-example with 46 vertices. Between about 12 or 14 vertices and 46, the territory has hardly been explored. Grace [5] has recently presented a computer tabulation of the polyhedra through 18 vertices, affording a convenient opportunity to scan them for cir- cuits, which were found in every instance. As Grace has noted, his criterion for isomorphism, “equisurroundedness” of the sets of faces is not strictly suf- ficient and his list may still be incomplete. As the isomorphism of circutts is fairly readily computed, this approach may be useful in further extensions of such studies. The work needed to demonstrate a circuit is curtailed by the reducibility of any triangular face: A circuit through a triangle is equivalent to that through a node: a ” That is to say, to describe a circuit a triangular face can be shrunk down to a node. In effect, by induction, if all #-hedra have circuits, so will all (#+2)- hedra with triangular faces, and we need only examine those without. Table 1 shows that only 55 forms need to be studied. Grace displayed the polyhedra as face-incidence lists. A computer program translated these into vertex-incidence lists. Mach vertex being identified as a face-triple, those vertices are joined which share two faces. The vertex-incidence un 1967] HAMILTON CIRCUITS OF CONVEX TRIVALENT POLYHIDRA Tae 1, Count of Trivalent Convex Polyhedra . Count Count Vertices Faces Total [5] No Triangles No 3-connected n f otal |> Present Regtons 4 4 1 0 0 6 5 1 0 0 8 6 2 1 1 10 7 5 1 l 12 8 14 2 2 14 9 50 5 4 16 10 233 12 10 18 11 1249 34 26 1555 55 44 list was then processed by a binary chained search of‘alternative paths; hence the search is always <2", in contrast to the m! scope of a systematic permutation of the vertices. (A much more efficient algorithm has been discovered and is outlined as an appendix.) Table 2 displays a circuit for each of the 55 polyhedra. The other polyhedra of order £18, and some of higher order can be developed from these by expand- ing nodes into triangles, a process that can be iterated. The circuits lend themselves to a compact code from which the graph of a polyhedron is quickly constructed. Draw a polygon with vertices marked 1(1)n. Each successive character of the code denotes the span of a chord drawn from the next vacani vertex. Thus the prism would be 2, 3, 2 or BCB, and Hamilton’s own example, the dodecahedron, is DJGDMJGDGD. There will be n/2 characters (to be sure the last one is redundant, being fixed by its predecessors). The letters A, B, C+--+stand for spans of 1, 2, 3--- vertices. A and B do not appear in our list; A would connote a self-looped edge and B a triangular face. Only one of the sometimes numerous circuits of each polyhedron is shown: it is merely the first one discovered by the computer search, but it has been placed in canonical form with respect to rotation and reflection of the poly- gon [2]. The complete list of the Hamilton circuits for each graph of Table 2 gives further insight into the composition of circuit-free graphs. F-xtracting one node from a polyhedron leaves a cut graph with three cut edges, e.g., a triangular region is the residue of a tetrahedron. In the first instance, in general such a residue will have the same facility for admitting a circuit as does an isolated node, depending on the set of circuits found in the polyhedron. Thus, except for CGDIGDFD (Grace's 16-55) all the polyhedra where »<16 have this property. Hence for finding circuits, any other 3-connected region can be re- placed by a single node. By induction only the 44 forms counted in Table 1 need be considered for 118. 524 HAMILTON CIRCUITS OF CONVEX TRIVALENT POLYHEDRA {May CGDIGD FD, (Fig. 1a) which is the same as Tutte’s graph N. [4], has three (symmetrically equivalent) edges that are obligatory in any Hamilton circuit It is the simplest with such a property. Tutte produced a 46-node circuit-free graph by replacing three nodes of a tetrahedron with 3 15-node residues so that 3 obligatory edges converged on one node in a self-contradictory way. Along the same lines a 38-node, circuit- free graph can be composed by replacing two nodes of CFDEC, the pentagonal prism, with two 15-node residues so as to confront two obligatory edges with two that, as pointed out by Tutte, are mutually exclusive. In an independent study, David Barnette has already discovered this graph [6]. + a ~~ ~ (a) (b) (c) @ Fic. 1. Composition of non-Hamiltonian polyhedra. (a) 16CGDIGDFD which is Tutte’s graph N,[4]. The marked edges are obligatory in any circuit. (b) a 15-node residue with an obliga- tory edge as marked. (c) and (d) are two non-Hamiltonian polyhedra of 46 and 38 nodes respec- tively. If we accept the enumeration of polyhedra for x16, on which Grace con- curs with Briickner [7 |, or merely that we know the 4-connected cases (as in table 2), a similar line of reasoning leads to an inferential argument for the conclusion that every 18-node polyhedron has a circuit. (We should say, more precisely, cyclically 4-connected as defined by Tutte [8]: “a cyclically k-connected graph cannot be broken up into two separate parts, each containing a polygon, by the removal of fewer than & edges.”) Each of the graphs was searched by a computer program for subgraphs obtained by extracting any node-pair, and the circuit-forming properties of the subgraphs examined. None of the subgraphs was of a kind that would disqualify a pairwise combination of them from con- taining a circuit (cf. Tutte’s arguments [8]). On the other hand, from Euler’s formula, every 18-node polyhedron must (a) contain no 3-connected and at least one 4-connected subgraph which has 14 or fewer nodes, and would therefore fall within the scope of the search, or (b) is derived from a graph with at least one 3-connected region, a case already disposed of through »=16. The further 1967] (Included are convex trivalent polyhedra with n $18 vertices. Only polyhedra with no triangular HAMILTON CIRCUITS OF CONVEX TRIVALENT POLYHEDRA TABLE 2. Listing of Hamilton circuits on tw on face are listed. See text for code. Each character group stands for one polyhedron.) * marks 3-connected forms; the remainder are 4-connected. Vertex Grace's Vertex pie Count Catalog Code Count Catalog Code [5] No. [5] Ne. 8 2 CECC 18 186 CNEMFCFCD 10 5 CFDEC 195 CNDMEGECE 12 6 CGEGEC 196 COLCGEIFC 11 CHFCFD 198 CNKHLECHE 14 6 CJHECGE 233 CNDFCGDED 7 CJGDHFC 326 COEMIFCFC* 8 CIGDHFD 328 CNDMDFDFC 15 CHFIGEC 329 CNLDHECH)D 46 CKEIECC* 347 CNLDHF DHF 16 42 CMJFDIFC 348 CNLIFDJHC 43 CLDKDECD 350 CODGEHFDE 44 CLIFJCGD 353 CLIGDRIGD 52 CLIFCIGC 354 CMJGLDIGD 54 CLDECEEC 356 CODGDHFCE 55 CGDIGDFD 362 CLJFDKIGC 60 CLJGECHF 376 CNJGEKIFD 61 CJHKDHFD 383 CNIFLJGEC 62 CKIECIGC 392 COMCIFCHC* 70 CMKDGECF* 393 CNKHFDJHE 88 CMDKFCEC* 401 COKHECJGC 112 CIGKIGEC 418 CMKGEKIGC 419 CMKHFDJHF 426 CNLIGECIG 427 CKIMKDHFD 428 CMKGECJHC 429 COCDGEHEC 477 CNLDGECHC* 493 COMELGECD* 505 COCCEIECC 508 CNGMKGECD* 509 CODMHECFD* 625 CODMCFCEC* 626 CODMIECFC* 887 CJHMKIGEC application of this technique should make it possible to anticipate the smallest non-Hamiltonian polyhedron from the properties of the 4- and 5-connected polyhedra of the next lower order. Since these, by definition, all have circuits, it would be feasible to generate them on the computer by reasonably efficient combinatorial schemes to whatever order is required. x 526 HAMILTON CIRCUITS OF CONVEX TRIVALENT POLYHEDRA [Mav Appendix: Algorithm for finding Hamilton circuits of a cyclic graph. This is illustrated for an undirected, trihedral graph but should be general- ized without difficulty in an obvious way. The input is a description of the con- nectivity of the graph. The essence of the routine is to build a table of sets of edges so that just two edges incident on each node appear in any row of the table. The first node is chosen arbitrarily. Its three incident edges are marked current and open. The circuit-fragment table is started with three rows by listing the 3 pairwise choices among the current edges. 1. Select an open edge. The two adjacent edges become the trial edges. 2. How manv trial edges match the current list: none, one, or two? a. If none match, close the selected edge and replace it on the current open list by the two trial edges. Scan the circuit-fragment table. Each row in which the selected edge appears is replaced by two rows, one for each trial edge. Each remaining row is replaced by one row showing both trial edges. Go to 1. b. If one matches, a circuit of the graph has been closed. Scan the circuit- fragment (c.f.) table contrasting the matched edge with the selected edge. Each c.f. where neither appears is deleted. If one of the two ap- pears on ac.f., this is augmented by the trial edge. If both appear, the c.f. row stands as is unless a tracing of the c.f. shows it to be prema- turely closed, whereupon it is deleted. Go to 1. c. If both match two adjacent faces of the graph have been closed. The preceding subroutine is revised in an obvious way to close out both matched edges: those c.f. rows are retained which are compatible with the indicated edge allocations. Go to 1. The process is terminated when the open edge list is vacated. If this leaves some nodes unused, no Hamilton circuit is possible. Otherwise, the final closure of circuit-fragments leaves a table of circuits. This must still be scanned to separate the Hamiltonian circuits from the set of pairwise disjoint circuits. The efficiency of the algorithm depends on keeping the current c.f. table as small as possible. This is accomplished by a lookahead routine which scans prospective choices of current edges to seek the promptest closure of a face. For an example, Tutte’s 46 node non-Hamiltonian graph has been searched exhaustively. This required a c.f. table of 12,477 rows consuming 29 seconds of a program on IBM 7090. Searches yielding all the circuits of other large Hamiltonian graphs required a comparable effort. This procedure may have some utility for studies on classification, iso- morphisms, and symmetries of abstract graphs and other network problems for which the set of Hamilton circuits is often an advantageous approach. A com- plete description of the computer program is available from the author. This work has been supported by a grant from NASA (NsG 81-60) for studies on automated experimental analysis. Computations were run on an 1BM 7090 at the Stanford Computation Cen- ter with support from the National Science Foundation, under grant NSF-GP-948. 1967] HAMILTON CIRCULTS OF CONVEX TRIVALENT POLYHEDRA 527 References 1. J. Lederberg, DENDRAL-64, A System for Computer Construction, Enumeration and Notation of organic Molecules as Tree Structures and Cyclic Graphs, Part I. (NASA Scientific and Technical Aerospace Report, STAR No. N65-13158, 1964, and CR 57029.) 2. ., Proc. Nat. Acad. Sci. U.S., 53 (1965) 134-139, 3. P. G. Tait, Phil. Mag. (Series 5), 17 (1884) 30. 4. W. T. Tutte, J. London Math. Soc., 21 (1946) 98. 5. D. W. Grace, Computer Search for Non-Isomorphic Convex Polyhedra, Stanford Compu- tation Center Technical Report No. C515 (1965). 6. V. Klee, Personal communication. 7. M. Briickner, Vielecke und Vielfliche, Teubner, Leipzig, 1900. 8. W. T. Tutte, Acta Math. (Hung.), 11 (1960) 371.