# 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?

-
You probably meant "not transitive" rather than "not commutative", although it would be better to say "not necessarily transitive", since I don't think you intend to exclude the transitive relations. (so: a -> b -> does not neccessarily imply a -> c.) –  Joel David Hamkins Mar 4 '10 at 13:39
@Joel Fixed thanks. –  Nick Johnson Mar 4 '10 at 16:02