Graphs on Six Vertices

Worked solution

The answer is 156. Let $S_6$ act on the 15 possible edges. By Burnside, the count is $\frac{1}{720}\sum_{\sigma} 2^{c(\sigma)}$, where $c(\sigma)$ is the number of cycles $\sigma$ induces on edges. This depends only on the cycle type of $\sigma$: an edge inside a $k$-cycle of vertices lies in $\lfloor k/2 \rfloor$ edge cycles, and the edges between a $j$-cycle and a $k$-cycle form $\gcd(j, k)$ cycles. Working through the 11 cycle types, for example the identity contributes $2^{15} = 32768$, the 15 transpositions contribute $15 \cdot 2^{11}$, the 120 six-cycles contribute $120 \cdot 2^{3}$ and so on, gives a total of $112320 = 156 \times 720$. So there are 156 graphs on six vertices (the sequence for $n = 1, \dots, 6$ is 1, 2, 4, 11, 34, 156).