## Abstract

The twinned-circle problem is to pack 2*N* non-overlapping equal circles forming *N* pairs of twins (rigidly connected neighbours) on a sphere so that the angular radius of the circles will be as large as possible. In the case that the contact graph(s) of the unconstrained circle packing support(s) at least one perfect matching, a complete solution to the twinned circles problem is found, with the same angular radius as the unconstrained problem. Solutions for *N*=2–12 pairs of twins are counted and classified by symmetry. For *N*=2–6 and 12, these are mathematically proven to be the best solutions; for *N*=7–11, they are based on the best known conjectured solutions of the unconstrained problem. Where the contact graph of the unconstrained problem has one or more rattling circles, the twinned problem is most easily solved by finding perfect matchings of an augmented graph in which each rattling circle is supposed to be simultaneously in contact with all its contactable neighbours. The underlying contact graphs for the unconstrained packings for *N*=2–12 are all Hamiltonian, guaranteeing the existence of perfect matchings, but Hamiltonicity is not a necessary condition: the first solution to the twins problem based on an example of a non-Hamiltonian contact graph occurs at *N*=16.

## 1. Introduction

Many situations in the physical and life sciences are modelled by the archetypal problem of packing of circles on a sphere. The problem is to find the maximum angular radius, *r*(*n*), such that *n* equal circles (spherical caps) can be placed on the sphere without overlap. This is the Tammes (1930) problem. Proven solutions are available for *n*=1–12 and 24 (Fejes Tóth 1964), and conjectural solutions for other values of *n* up to 130 (Sloane *et al*. 2000). Configurations of *n* packed circles model, for example, the distribution of pores on spherical pollen grains (Tammes 1930), certain polyhedral borane frameworks (Greenwood & Earnshaw 1986), valence-shell electron-pair repulsion models of molecules (Gillespie & Nyholm 1957) and spherical codes in information theory (Conway & Sloane 1999). Apart from this unconstrained problem, there is also continuing interest in constrained versions of the packing problem: when circles are rigidly linked in antipodal pairs (Fejes Tóth 1965; Conway *et al*. 1996; Fowler *et al*. 2002), equilateral triangular triplets (Fowler *et al*. 2005) or regular tetrahedral quartets (Tarnai *et al*. 2003); for example, the solutions to the constrained problem are relevant to the construction of the gamma knife in brain surgery (Leksell 1983), the theory of triangle compounds or *nolids* (Holden 1991) and the Linnett quartet model of valency (Linnett 1964), respectively. The present note is concerned with a variant of the constrained packing problem where the circles are locally paired. In the *twinned-circle* problem, the objects to be packed are *N* rigidly connected contacting pairs of circles, i.e. pairs of ‘twins’. Packing of twinned circles can be used as a geometrical model of packing of dimers of protein molecules in core shells of spherical viruses such as hepatitis B (Wynne *et al*. 1999), and can also be seen as packing of ‘diatomic molecules’ rather than ‘atoms’ on the spherical shell. Thus, the problem to be solved is: How must 2*N* non-overlapping equal circles forming *N* twinned pairs be packed on a sphere so that the angular radius *r*^{*}(2*N*) of the circles will be as large as possible under the constraint that contact is maintained within each twinned pair? If the solution is not unique, how many (non-isomorphic) solutions with the same radius *r*^{*}(2*N*) exist?

The purpose of this note is to point out that solutions of the twinned-circle problem (*the twins problem*) can be obtained trivially from the solution of the unconstrained circle-packing problem (*the unconstrained problem*) if the contact graph for that case has at least one perfect matching. For a packing of *n* circles, the *contact graph* is drawn by taking each circle centre as a vertex, and joining by an edge those pairs of vertices that represent the circles in contact. When *n* circles are packed on the sphere, it is often the case that the contact graph is the skeleton of a contact polyhedron. If the graph supports a perfect matching (a set of disjoint edges that covers each vertex exactly once), then the edges of the matching can be considered as representing *n*/2 pairs of twinned circles in a solution of the *N*=*n*/2 twinned-circle-pair-packing problem. In such cases, it should be noted that the radius of circles in the twinned problem is the same as that in the unconstrained problem, *r*^{*}(2*N*)=*r*(*n*). Clearly, such a solution cannot be bettered in radius by removal of a constraint. As a given graph may have many perfect matchings, we may find multiple non-isomorphic solutions to the twins problem even when the solution to the unconstrained problem is unique.

Some general considerations are discussed in §2 and then the cases of even *n*=4, 6, 8, …, 24 circles, i.e. *N*=2–12 pairs of twins, are examined in detail. We count and classify by symmetry the solutions obtainable from all perfect matchings of the known and conjectured contact graphs of the unconstrained problem in this range.

## 2. Preliminaries

### (a) Existence of solutions derived from perfect matchings

Can we expect *all* unconstrained contact graphs for even *n* to support at least one perfect matching? Figure 1 shows the contact graphs for *n*=4, 6, 8, …, 24 and table 1 summarizes some of their properties, which illustrate some general characteristics of contact graphs. For example, all contact graphs are planar (i.e., they can be embedded on the sphere or plane without edge crossings) and have maximum vertex degree of at most 5 (Fejes Tóth 1964).

Vertex degrees of 3, 4 and 5 are observed in the proven and conjectured solutions for these and larger values of *n*. A vertex degree of 2 occurs if the solution includes a rattling circle (as for *n*=20): the vertex corresponding to a rattler can be considered to have degree 2, as it is always possible to let the circle move into contact with at least two neighbours within the range of its two-dimensional rattling motion. Exceptionally, a solution may also have one-dimensional freedom, as in the contact graph for *n*=5, where two circle centres are fixed at the poles and the other three circle centres lie on the equator, along which they are able to move, in contact with the polar circles, but not necessarily with each other (Tarnai & Gáspár 1983). Once this addition of supplementary edges is allowed, all contact graphs become connected.

Another empirical observation about contact graphs is that all known examples are bridgeless, and indeed, it is difficult to see how a bridge (an edge whose removal disconnects the graph) could exist, as contact graphs with *n*>3 and *n*≠5 are all believed to be rigid in the Danzerian sense. Danzer (1963) represents the contact graph as a special bar-and-joint assembly in which the bars may change length but only in a concerted fashion where all bars stretch/shrink by the same amount, accommodated by local rotations at the joints such that all joints remain on the spherical surface. The generic freedom of such an object on the sphere isand the object is rigid (or overconstrained) if *f*≤0. Values of *f* are listed in table 1. As proved by Tarnai & Gáspár (1983), a triangle-free graph cannot be rigid in the Danzerian sense. It is a matter of empirical observation that in the contact graphs for the unconstrained problem in the cases studied till date, no faces of more than six sides have been encountered.

Necessary and sufficient conditions for a graph to have a perfect matching are known from Tutte's (1947) 1-factor theorem, but do not seem to offer an immediate connection with the foregoing summary of known properties of contact graphs. Other theorems help to prove the existence of perfect matchings in some classes of contact graphs. Petersen's theorem (e.g. Biggs *et al*. 1986; Tutte 1998) states that every bridgeless cubic graph has a perfect matching. Among our contact graphs, *N*=2 (the tetrahedron) is covered by this theorem.

Another useful idea comes from the consideration of Hamiltonian walks and circuits. A *walk* of length *l* is an alternating sequence such that *v*_{j−1} and *v*_{j} are the endpoints of edge *e*_{j}, and a *Hamiltonian walk* is one that includes no edge more than once and every vertex of the graph exactly once. A *Hamiltonian circuit* includes an additional edge *e*_{l+1} joining *v*_{l} back to *v*_{0}. A graph is said to be *Hamiltonian connected* if every pair of vertices are the ends of some Hamiltonian walk, and a graph is said to be *Hamiltonian* if it contains a Hamiltonian circuit. The connection with perfect matchings is that, if a graph with an even number of vertices is Hamiltonian, two perfect matchings are immediately available, as we may take alternate edges of the Hamiltonian circuit as the set of independent edges for a matching. If the even-vertex graph has a Hamiltonian walk, then one perfect matching is available by selecting every second edge of that walk, starting from *e*_{1}.

A theorem of Tutte (1956) states that every 4-connected planar graph is Hamiltonian connected, and hence Hamiltonian. (A *k*-connected graph is one where *k* is the minimum number of vertices whose removal either disconnects the graph or reduces it to the trivial one-vertex graph.) Our contact graphs are all planar and some are 4-connected. The connectivities are listed in table 1. Whether 4-connected or not, all the contact graphs for the even numbers in the range *n*=4–24 are Hamiltonian and hence have perfect matchings (see figure 1).

However, Hamiltonicity is not a necessary condition for the possession of a perfect matching. Figure 2 shows the contact graph for *n*=32 circles (Danzer 1963), which on checking is found to be non-Hamiltonian (and in fact does not even support a Hamiltonian path). Nevertheless, it has multiple perfect matchings and hence gives solutions to the twins problem at *r*^{*}(32)=*r*(32)≈37.4752140° (see Sloane *et al*. 2000).

### (b) Completeness of solutions derived from perfect matchings

The basis of the present approach is the connection between perfect matchings in the unconstrained contact graph and circle pairing in the twins problem. It is straightforward to derive the conditions under which such an approach will recover all solutions.

Suppose that we have found the contact graph for the unconstrained problem on an even number of circles. If this graph has a perfect matching, then by taking the independent edges of the matching to represent twinned circles, we have a solution of the twins problem with the same angular radius *r*^{*}(2*N*)=*r*(*n*). Every perfect matching of leads to such a solution. Furthermore, *every* solution of the twins problem can be obtained in this way. If there were another twins solution at the same radius, the contacts internal to the twin pairs would form an independent set of edges of a graph, which would also be a contact graph for the unconstrained problem. Thus, if the contact graph of the solution of the constrained problem is unique, the complete solution of the twins problem is given by the set of perfect matchings of . If the unconstrained problem has more than one solution, with graphs , ′, ″, etc., then the complete solution of the twins problem is given by the union of the sets of perfect matchings of these graphs. A corollary is that if *no* contact graph for the unconstrained problem has a perfect matching, then the solution for the twins problem has *r*^{*}(2*N*)<*r*(*n*). As yet, we have no example of such a case.

Cases where the contact graph is not unique but ‘toggles’ between possibilities and ′ are known. One pair of solutions was found at *n*=15 (Kottwitz 1991). For 2*N*=22, there are several *local* optima (Leech & Tarnai 1988), although the global optimum turns out to be unique (Sloane *et al*. 2000). Buddenhagen & Kottwitz (2001) found cases of toggles for *n*=117 and the even cases 2*N*=62 and 2*N*=76. In all these cases, a vertex of degree 3 lies inside a hexagonal cycle 1-2-3-4-5-6-1 of vertices and in the toggle it jumps between 1,2,4 and 1,4,5 coordination to vertices of the hexagon. We have checked that both contact graphs support perfect matchings for both 2*N*=62 and 2*N*=76, and so the twins problem shares both its circle radius and the toggling property with the unconstrained solutions for these values of 2*N*.

### (c) Method

Contact graphs for the solutions of the unconstrained problem on even numbers of circles from *n*=4, 6, 8, …, 24 were constructed from literature data and the sources listed in table 1. In a graph of *n* vertices and *e* edges, a perfect matching is equivalent to the selection of *n*/2 independent edges and, with some canonical ordering of the edges, can be represented by a {0,1} string of length *e*, containing *n*/2 entries 1 for the edges in the independent set and *e*−*n*/2 entries 0 for the excluded edges. Although sophisticated techniques are available for counting Kekulé structures in trivalent graphs and perfect matchings in more general graphs, here, the graphs are all small, and no special algorithms or compressed representations are needed. For these 11 graphs, the full set of perfect matchings, represented as sets of strings, was constructed by simple exhaustion. All 11 contact graphs were found to have multiple perfect matchings and therefore to give multiple solutions to the twins problem with *r*(*n*)=*r*^{*}(2*N*). The elements of the automorphism group of the contact graph (the point group of the contact polyhedron) were represented as permutations of the edges and were used to reduce the grand list of perfect matchings to the shortlist of non-isomorphic, symmetry unique cases and to identify their individual point-group symmetries. The results are shown in table 2.

## 3. Results

### (a) *N*=2

The contact graph of the solution of the unconstrained problem for *n*=4 circles is the skeleton of the regular tetrahedron (figure 1, table 1). This graph has three isomorphic perfect matchings, each consisting of opposite edges of the tetrahedron, and so yields the unique solution, of *D*_{2d} symmetry, for the twins problem (figure 3*a*, table 2).

### (b) *N*=3

The contact graph of the solution of the unconstrained problem for *n*=6 circles is the skeleton of the regular octahedron (figure 1, table 1). This graph has eight isomorphic perfect matchings—choose one of four edges from the North Pole to the equator, choose one of the two possibilities for the side of the equatorial square, and then the remaining edge to the South Pole is forced. All have the chiral *D*_{3} symmetry and the unique (up to enantiomerism) solution for the twins problem (figure 3*b*, table 2).

### (c) *N*=4

The contact graph of the solution of the unconstrained problem for *n*=8 circles is the skeleton of the square antiprism (figure 1, table 1). This graph has three non-isomorphic perfect matchings—the opposite square faces each contain 0, 1 or 2 matching edges. All are chiral, and the individual symmetries are *D*_{4}, *D*_{2} and *C*_{2}, respectively, giving the three non-isomorphic solutions to the twins problem (figure 3*c*, table 2).

### (d) *N*=5

The contact graph of the solution of the unconstrained problem for *n*=10 circles can be derived (in a combinatorial sense) from the skeleton of the square antiprism by subdividing opposite edges of one square face and joining the two additional vertices to make a polyhedron of *C*_{2v} symmetry (figure 1, table 1). The 20 perfect matchings of the graph reduce to six non-isomorphic cases, of which two preserve the twofold rotational axis and four have no symmetry. All yield chiral solutions to the twins problem (figure 3*d*, table 2).

### (e) *N*=6

The contact graph of the solution of the unconstrained problem for *n*=6 circles is the skeleton of the regular icosahedron (figure 1, table 1). This graph has 120 symmetry operations and its perfect matchings appear in many copies. The five non-isomorphic cases, where the matchings have *T*_{h}, *D*_{3d}, *D*_{3}, *D*_{2} and *C*_{2} symmetries, respectively, generate 5+10+20+30+60=125 copies. They correspond to the solutions of the twins problem (figure 4, table 2), and include the smallest centrosymmetric set of optimally packed twinned circles (*T*_{h}).

### (f) *N*=7

The contact graph of the solution of the unconstrained problem for *n*=14 circles (figure 1, table 1) is the skeleton of a *D*_{2d} polyhedron with eight triangular and eight quadrilateral faces arranged in a manner reminiscent of the tennis ball, with the quadrilateral faces forming the continuous ‘seam’, and two chains of four triangles in the positions of the two staggered panels separated by the seam. This graph has eight non-isomorphic perfect matchings, each with only the trivial *C*_{1} symmetry and, hence, each appearing in eight copies (figure 5, table 2). Thus, *N*=7 is the smallest case where no solution of the twins problem has a non-trivial symmetry.

### (g) *N*=8

The contact graph of the solution of the unconstrained problem for *n*=16 circles (figure 1, table 1) is the skeleton of a *D*_{4d} polyhedron with eight triangular and 10 quadrilateral faces (two are square). This polyhedron is one of the series of 4-valent polyhedra with skeletons known as Conway graphs (Kawauchi 1996). The Conway graph (*k*×*m*)^{*} is a generalization of the graph of the *m*-gonal antiprism: it has two *m*-gonal, 2*m* triangular and (*k*−2)*m* quadrangular faces, constructed from a single *m*-cycle by successively inscribing a further *k*−1 *m*-gons, the vertices of each new *m*-gon being the edge midpoints of its predecessor, finally adding *m* edges to link the consecutive vertices of the original cycle. Our example here is (4×4)^{*}. Its 92 perfect matchings reduce to 11 non-isomorphic cases, with symmetries *D*_{4}, *S*_{8}, *D*_{2}, *C*_{2} and *C*_{1} (figure 6, table 2), all solving the twins problem.

### (h) *N*=9

The contact graph of the solution of the unconstrained problem for *n*=18 circles (figure 1, table 1) is the skeleton of a *C*_{2}-symmetric polyhedron with four triangular and 14 quadrilateral faces. Of the 76 non-isomorphic perfect matchings, 10 preserve the *C*_{2} axis and 66 have only trivial *C*_{1} symmetry (table 2). Examples of perfect matchings and hence twinned-circle solutions of each of the two symmetry types are given in figure 7.

### (i) *N*=10

In the solution of the unconstrained problem for *n*=20 circles, two circles are rattling about positions at the North and South Poles (van der Waerden 1952). The geometric configuration of the centres of the remaining 18 fixed circles has *D*_{3h} symmetry, with two hexagonal ‘holes’ within which the rattling circles are accommodated. Each hole has a threefold rotational symmetry. It can be seen from geometrical considerations that the contained rattling circle can come into simultaneous contact with at most two of the circles that make up the perimeter of the hexagonal hole. In the 18-vertex contact graph (figure 8*a*), the centres of the contactable circles define the vertices of degree 4 each common to three triangles (marked by filled circles in the figure). Thus, in the physical situation appropriate to the twins problem, each originally rattling circle is twinned with one of the three filled circles in its local hexagon and the rattling motion is reduced to a pendulum-like wagging motion of the twinned pair.

One approach to counting solutions of the twins problem for *N*=10 would therefore be to construct all non-isomorphic versions of a contact graph consisting of the 18-vertex graph and two pendant vertices inside the hexagonal holes (figure 8*b*), then count all perfect matchings of each member of this set of graphs, and then reduce to a final non-isomorphic set.

However, exactly equivalent results are obtained rather more easily if we connect the rattler vertices to all three of their filled-circle neighbours and deal with the resulting *D*_{3h}-symmetric 20-vertex graph (figure 8*c*). Counting and symmetry reduction of perfect matchings can then proceed in the usual way, taking advantage of the full symmetry. This is the method adopted here. A total of 558 perfect matchings was found and reduced with the 12 operations of the *D*_{3h} group to 54 non-isomorphic cases, 15 preserving a *C*_{2} axis and 39 of *C*_{1} symmetry (table 2). These give the solutions to the twins problem for *N*=10, all containing two wagging circle-pairs and the same radius as that of the best unconstrained packing of 20 circles. An example of each type is shown in figure 9*a*,*b*.

### (j) *N*=11

The contact graph of the solution of the unconstrained problem for *n*=22 circles (figure 1, table 1) is the skeleton of a polyhedron with 10 triangular, six quadrilateral and six pentagonal faces. This is the smallest even number of circles for which the unconstrained solution has no symmetry. All 120 of its perfect matchings are therefore non-isomorphic and provide 120 solutions of the twins problem for *N*=11 (table 2). An example is given in figure 10.

### (k) *N*=12

The contact graph of the solution of the unconstrained problem for *n*=24 circles is the skeleton of an Archimedean solid, the snub octahedron (figure 1, table 1). This is one of the two known cases where the unconstrained best packing is one that realizes for every vertex the maximum possible degree available to a contact graph; the other being the icosahedron.

The count of 385 non-isomorphic perfect matchings (table 2) includes one with the full *O* symmetry of the contact graph, but 276 with only trivial symmetry. Figure 11 shows the 11 perfect matchings and hence the solutions of the twins problem that have symmetry groups of order 6 or more.

## 4. Discussion

By examining contact graphs for proven and conjectural literature solutions (see table 1 for a list of references) for the unconstrained packing problem for *n*=2*N* circles, we have found solutions for the twinned-circle-packing problem for *N*=2–12 pairs. As the solutions for the unconstrained problem for *n*=2*N*=4, 6, 8, 10, 12 and 24 are mathematically proven, the twins solutions are exact in these cases. For *N*=7, 8, 9, 10 and 11 pairs, the solutions have the same conjectural status as the underlying solution of the unconstrained problem. From the discussion of perfect matchings given here, if we have found one solution, then we have found all solutions at the given radius, and the set of non-isomorphic solutions has been classified by the point-group symmetry in all cases.

A strategy for dealing with cases where the solution to the unconstrained includes a rattling circle is illustrated by *N*=10. A single rattling circle equates to a wagging pair in the twins problem, comprising the rattler and any one of its contactable neighbours. An augmented contact graph is constructed by joining each rattler simultaneously to all its individually contactable neighbours (feasibility of the contact requiring a geometric calculation) and the set of solutions of all the possible twins problems is given by the perfect matchings of the augmented contact graph.

We note that the packing graphs of the solutions of all investigated cases for even numbers of circles (*n*=4–24) are Hamiltonian. However, the case of *n*=32 shows that it is possible for the graph of the best unconstrained packing of an even number of equal circles to be non-Hamiltonian. The 32-circle case is in fact the smallest example of a non-Hamiltonian contact graph for the unconstrained problem for an even number of circles *n*=2*N*: exploration of the cases *n*=26, 28 and 30 (data from Sloane *et al*. (2000)) shows that all are Hamiltonian (in the cases of 26 and 28 circles, rattling has to be dealt with by augmentation of the contact graph, as described earlier).

In all the cases that we have examined, we have been able to find a solution of the twins problem with the same circle diameter as that in the solution of the corresponding unconstrained problem. If all the contact graphs for the unconstrained problem have one or more perfect matchings, then it will always be possible to find such a solution. However, in the absence of a proof that *all* unconstrained contact graphs are of this type, there is an open question: What is the smallest number of pairs of twins of circles (if any) for which the solution of the twins problem is *not* obtained from a perfect matching in the contact graph of the unconstrained problem?

## Acknowledgements

This research was partially supported by the Hungarian Scientific Research Funds (OTKA) grant no. T046846. P.W.F. thanks The Royal Society/Wolfson Research Merit Award Scheme for financial support.

## Footnotes

- Received February 16, 2006.
- Accepted May 22, 2006.

- © 2006 The Royal Society