List all permutations which are symmetries of $K_5 \backslash e$ and calculate number of possible coloring

Question

One edge has been removed from a $K_5$ graph to form our $K_5 \backslash e$ graph. List all permutations which are the symmetries of such graph. Using Burnside's lemma, calculate the number of all possible different colorings of such graph's vertices using 3 colors.

I try to approach this problem, but have trouble understanding what the problem is really about and how to understand "symmetries" of a graph. I think this first part might be key to solving the second part with Burnside's lemma, but I'm not really sure.

Answer 1

Consider the problem of removing an edge from $K_q$ and asking about non-isomorphic vertex colorings using at most $N$ colors. This requires the cycle index $Z(G_q)$ of the group permuting the vertices. There are two possibilities. Fix the vertices $u$ and $v$ where the edge has been removed or flip them. The remaining $q-2$ vertices are not distinguishable and are permuted by the symmetric group $S_{q-2}$ with cycle index $Z(S_{q-2}).$ It follows that the cycle index $Z(G_q)$ is given by

$$Z(G_q) = \frac{1}{2} (a_1^2+a_2) Z(S_{q-2}).$$

When $q=5$ we have

$$Z(G_5) = \frac{1}{2} (a_1^2+a_2) \frac{1}{6} (a_1^3 + 3a_1 a_2 + 2a_3).$$

Remark. Adhering to the question as stated and supposing that the edge was between vertices $1$ and $5$ we get the permutations

$$12345, 12435, 13245, 13425, 14235, 14325, \\ 52341, 52431, 53241, 53421, 54231, 54321.$$

We then factor these into cycles to get the cycle index. For example, $53241$ yields $a_1 a_2^2.$ Burnside says we have to be constant on the cycles and here we have three of them and may choose a color for each.

Therefore we get for colorings with at most $N$ colors for $q=5$

$$\frac{1}{12} (N^2 + N) (N^3 + 3 N^2 + 2N)$$

which is the sequence

$$1, 12, 60, 200, 525, 1176, 2352, 4320, 7425, 12100, \ldots$$

In particular using at most three colors gives

$$\bbox[5px,border:2px solid #00A000]{ 60}$$

colorings.

Returning to the general problem, as an example, here is the cycle index for $K_7$ minus an edge:

$$Z(G_7) = {\frac {{a_{{1}}}^{7}}{240}} +{\frac {11\,{a_{{1}}}^{5}a_{{2}}}{240}} +{\frac {5\,{a_{{1}}}^{3}{a_{{2}}}^{2}}{48}} +1/12\,{a_{{1}}}^{4}a_{{3}}+1/6\,{a_{{1}}}^{2}a_{{2}}a_{{3}} \\ +1/16\,a_{{1}}{a_{{2}}}^{3} +1/8\,{a_{{1}}}^{3}a_{{4}}+1/8\,a_{{1}}a_{{2}}a_{{4}} \\+1/12\,{a_{{2}}}^{2}a_{{3}} +1/10\,{a_{{1}}}^{2}a_{{5}}+1/10\,a_{{2}}a_{{5}}.$$

With the number of permutations having $k$ cycles in the symmetric group $S_n$ being given by ${n\brack k}$ we get the closed form

$$\bbox[5px,border:2px solid #00A000]{ \frac{1}{2(q-2)!} (N+N^2) \sum_{p=0}^{q-2} {q-2\brack p} N^p.}$$

If you are interested in exploring these cycle indices there is the following Maple code.

with(combinat);

pet_cycleind_symm :=
proc(n)
local l;
option remember;

    if n=0 then return 1; fi;

    expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;

pet_cycleind_kn_minus_edge :=
proc(q)
    expand(1/2*(a[1]^2+a[2])*pet_cycleind_symm(q-2));
end;

COLS :=
proc(q, N)
    option remember;
    local subl, p;

    if q = 1 then return FAIL fi;

    subl := [seq(a[p]=N, p=1..max(2, q-2))];
    subs(subl, pet_cycleind_kn_minus_edge(q));
end;

COLSx :=
proc(q, N)
local p;

    if q = 1 then return FAIL fi;

    1/2/(q-2)!*(N+N^2)*
    add(abs(stirling1(q-2,p))*N^p, p=0..q-2);
end;

We can also ask about proper colorings using $k$ colors, where we require the corresponding orbital chromatic polynomial. These can be computed by inspection. We need to choose $q-2$ colors for the clique. These can be combined with either one or two colors for $u$ and $v.$ We find

$${k\choose q-2} \left({k-(q-2)\choose 1} + {k-(q-2)\choose 2}\right) \\ = \frac{1}{2(q-2)!} k(k-1)(k-2)\cdots(k-(q-3)) \times (k-(q-2)) (2+k-1-(q-2)) \\ = \frac{1}{2(q-2)!} k(k-1)(k-2)\cdots (k-(q-4))(k-(q-3))^2 (k-(q-2)).$$

This matches the output from the OCP algorithm.

Concluding remark. It is also possible to count non-isomorphic, non-proper colorings where exactly $N$ colors are used (all colors present) using Stirling numbers. This yields

$$\bbox[5px,border:2px solid #00A000]{ \frac{N!}{2(q-2)!} \sum_{p=0}^{q-2} {q-2\brack p} \left({p+1\brace N} + {p+2\brace N}\right).}$$

This is verified here.

COLSall :=
proc(q, N)
local M;

    if q = 1 then return FAIL fi;

    add(binomial(N,M)*(-1)^(N-M)*COLSx(q, M),
      M=1..N);
end;

COLSallx :=
proc(q, N)
local p;

    if q = 1 then return FAIL fi;

    N!/2/(q-2)!*
    add(abs(stirling1(q-2,p))*
    (stirling2(p+1,N)+stirling2(p+2,N)), p=0..q-2);
end;