# Counting distinct undirected, partially labelled graphs

Suppose I have a hexagonal tile. Each edge can be connected to any subset of the other edges (including none). Connections are undirected, so a->b implies b->a, but they're not necessarily transitive - eg, a->b, b->c does not imply a->c. The graph resulting from the connected edges need not be connected - there can be multiple distinct subgraphs.

As far as I can tell, this is a special case of counting undirected, labelled 6 vertex graphs. This would be simple - there are $5+...+1=15$ possible edges, each of which can be present or absent, leading to $2^{15}$ possible graphs.

However, tiles are isomorphic with respect to rotation, and the above formula will generate every distinct rotation. The number of isomorphic graphs varies with the symmetry of the graph, so we can't simply divide the total by 6, either.

How can I compute the number of distinct graphs for this problem?

This is a job for Burnside's lemma. What you're trying to count is orbits of 6-vertex graphs under a certain action of the 6-element cyclic group, which I'll denote $Z_{6}$. By Burnside's lemma, this is equal to the average number of fixed points of elements of $Z_{6}$, so really we just need to count those fixed points and then do some arithmetic.

It turns out that these numbers of fixed points are actually quite easy to describe. $Z_{6}$ has one element of order $1$, two of order $3$, two of order $6$, and one of order $2$. We consider them order by order.

• Order 1: All $2^{15}$ graphs are fixed by the identity.
• Order 2: There are three "diameter" edges which are sent to themselves by the rotation of order 2; the other twelve edges are interchanged in pairs. Thus, there are nine orbits of edges under the action of this element, and thus $2^{9}$ graphs which are fixed by it.
• Order 3: Every edge is part of a triple of distinct edges which are sent to each other cyclically by any rotation of order three. Thus, there are five of these orbits, so there are $2^{5}$ graphs fixed by such an element.
• Order 6: The diameters mentioned previously form an orbit of length 3 under the action of a rotation of order 6; the remaining edges form two orbits of length 6. Thus, there are three total orbits, and therefore there are $2^{3}$ graphs fixed by each of these elements.

Now we hit it with Burnside's lemma. Let $N$ be the total number of graphs up to $Z_{6}$-equivalence; by the lemma, we have

$N = \frac{1}{6} (2^{15} + 2^{9} + 2 \cdot 2^{5} + 2 \cdot 2^{3}) = 5560.$

(To do this in more generality, you'd want to bring in some algebraic heavy machinery; a combination of Pólya theory and generating functions is the usual way to go.)

• Venturing well beyond my grasp, unfortunately, but what I can follow sounds right, and a numerical answer is certainly nice. Thanks! – Nick Johnson Feb 1 '14 at 17:05

Wouldn't an inclusion-exclusion sort of method work here? You first count all labelled graphs. You then observe that you have overcounted: for example, every graph with rotational symmetry of order 3 has been counted three times when it should have been counted once, so you subtract twice the number of graphs with rotational symmetry 3 (which is easy to calculate because you can partition the edges into triples and each triple either goes in completely or not at all). But in doing this, you find that you have subtracted too much. For instance, if a graph has rotational symmetry of order 6 then it also has rotational symmetry of order 2 and 3 so you have subtracted a total of 1+2+5=8 instead of just 5. So you look at pairs of symmetry properties and add back in, and so on.

I haven't checked that this really does the job, but it feels like the sort of territory where inclusion-exclusion comes in.

• That seems like a reasonable approach. I'm not quite sure I understand how to count all graphs with a given rotational symmetry, though, or your comment about equilateral triangles. – Nick Johnson Mar 4 '10 at 11:54
• Sorry, I meant triples closed under the given rotation (some, but not all, of which give you triangles). If the vertices are 0,1,2,3,4,5, then some examples of such triples are 01,23,45 and 03,14,25, and also the equilateral triangles 02,24,40 and 13,35,51. In fact, there's one more triple, namely 14,25,30, and any graph with rotational symmetry of order 3 is a union of these triples, so there are 32 such graphs. – gowers Mar 4 '10 at 12:02
• The standard method is Burnside's Lemma, that the number of orbits equals the average number of fixed points for a uniformly chosen element of the group. That still leaves the problem of counting symmetric configurations. – Douglas Zare Mar 4 '10 at 12:19
• There's a proof of Pólya's theorem by Gian-Carlo Rota and David Smith using Möbius inversion along the lines that gowers suggests, but the usual proof of Burnside's lemma is much easier. See Rota, Gian-Carlo; Smith, David A. Enumeration under group action. Annali della Scuola Normale Superiore di Pisa - Classe di Scienze, Sér. 4, 4 no. 4 (1977), p. 637-646 numdam.org/item?id=ASNSP_1977_4_4_4_637_0 – Ira Gessel Apr 27 '15 at 20:14