Question

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?

Answer 1

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.