# How many ways can one paint the edges of a Petersen graph black or white?

How many ways can one paint the edges of a Petersen graph black or white?

I know that the symmetrygroup of the Petersen graph is $[S5][1]$. Furthermore this this seems like a case where I should use Burnside’s lemma. I’m sorry if the following is too verbose or uses non standard notation; I haven’t been acquainted with graph theory.

S5 has 7 conjugacy classes, namely those with cycle types: (1,1,1,1,1),(1,1,1,2),(2,2,1),(2,3),(1,1,1,3),(4,1),(5). S5 has 15 edges so the identity (1,1,1,1,1) would leave $2^{15}$ different colorings fixed. The n-cycle (5) is a rotation of the whole graph and as such would leave $2^3$ colorings fixed. The “outside” could be white or black, the connecting edges and the “inside” edges could both be either white or black. Rotation around one “connecting” edge involves the (2,2,1) cycles. I won’t tire you with the details but I found $2^9$ colorings.

From here I’m stuck however, I can’t find any more symmetries than these. How do I find the colorings left fixed by the other conjugacy classes?

#### Solutions Collecting From Web of "How many ways can one paint the edges of a Petersen graph black or white?"

I hope I can be of help here even if my approach is not the most sophisticated. I have written a Maple program to compute the action of the automorphism group $G$ of the Petersen graph on its edges (giving the edge permutation group $Q$), using properties that are documented at Wikipedia. My vertices are the number pairs that can be chosen from $\{1, 2, 3, 4, 5\}$. I used a brute force method going through all vertex permutations and checking that they preserve the property that two vertices are adjacent iff the two number pairs are disjoint, i.e. the Kneser graph property of the Petersen graph. That yields the automorphism group $G$ of the vertices. To conclude apply every permutation from $G$ to the edges, thereby obtaining $Q$ and its cycle index. At this point it remains to substitute $x+y$ into the cycle index according to Polya’s theorem to obtain the generating function of the orbits. There are $396$ of them.

This is the cycle index:
$$Z(Q) = {\frac {1}{120}}\,{a_{{1}}}^{15}+{\frac {5}{24}}\,{a_{{2}}}^{6}{a_{{1}}}^ {3}+1/6\,{a_{{3}}}^{5}+1/6\,a_{{3}}{a_{{6}}}^{2}+1/4\,{a_{{4}}}^{3}a_{{2} }a_{{1}}+1/5\,{a_{{5}}}^{3}.$$

Substituting $x+y$ into $Z(Q)$ yields
$$Z(Q)_{x+y} = {\frac {1}{120}}\, \left( x+y \right) ^{15}+{\frac {5}{24}}\, \left( {x}^ {2}+{y}^{2} \right) ^{6} \left( x+y \right) ^{3}\\ +1/6\, \left( {x}^{3}+{y} ^{3} \right) ^{5}+1/6\, \left( {x}^{3}+{y}^{3} \right) \left( {x}^{6}+{y }^{6} \right) ^{2} \\ +1/4\, \left( {x}^{4}+{y}^{4} \right) ^{3} \left( {x}^{ 2}+{y}^{2} \right) \left( x+y \right) +1/5\, \left( {x}^{5}+{y}^{5} \right) ^{3}.$$

Expanding we find the generating function that classifies the edge colorings according to the two colors:
$$Z(Q)_{x+y} = {x}^{15}+{x}^{14}y+3\,{x}^{13}{y}^{2}+9\,{x}^{12}{y}^{3}+19\,{x}^{11}{y}^ {4}+37\,{x}^{10}{y}^{5}+58\,{x}^{9}{y}^{6}+70\,{x}^{8}{y}^{7}\\ +70\,{x}^{7} {y}^{8}+58\,{x}^{6}{y}^{9}+37\,{x}^{5}{y}^{10}+19\,{x}^{4}{y}^{11}+9\,{x} ^{3}{y}^{12}+3\,{x}^{2}{y}^{13}+x{y}^{14}+{y}^{15}.$$

Setting $x=1$ and $y=1$ we find that the total count is equal to $$396.$$

The Maple program follows for all group theory enthusiasts who are also programmers! If there are any concrete questions as to what the individual functions do I will be happy to answer them. I can also resend the program if there are problems with the formatting. Enjoy! Comments are welcome.

with(group):
with(combinat):

pet_verts := convert(choose({seq(k, k=1..5)}, 2), list);

pet_edges_set := {};

for v1 in pet_verts do
for v2 in pet_verts do
if v1 intersect v2 = {} then
pet_edges_set := pet_edges_set union {{v1, v2}};
fi;
od;
od;

pet_edges := convert(pet_edges_set, list);

pet_is_autom :=
proc(vperm)
local allsubs, e, eperm, el;

allsubs :=
[seq(pet_verts[pos]=vperm[pos], pos=1..nops(vperm))];

eperm := subs(allsubs, pet_edges);

for e in eperm do
el := convert(e, list);
if el[1] intersect el[2] <> {} then
return false;
fi;
od;

return true;
end;

pet_vautom := [];

pet_compute_vautom :=
proc()
option remember;
global pet_vautom;
local perm, vperm, pos, count;

count := 0; perm := firstperm(nops(pet_verts));

while type(perm, list) do
vperm :=
[seq(pet_verts[perm[q]], q=1..nops(pet_verts))];

if pet_is_autom(vperm) then
count := count+1;
printf("automorphism %d\n", count);

pet_vautom := [op(pet_vautom), vperm];
fi;

perm := nextperm(perm);
od;

pet_vautom;
end;
pet_compute_vautom():

pet_autom2cycles :=
proc(src, aut)
local numa, numsubs;
local marks, pos, cycs, cpos, clen;

numsubs := [seq(src[k]=k, k=1..nops(src))];
numa := subs(numsubs, aut);

marks := [seq(true, pos=1..nops(aut))];

cycs := []; pos := 1;

while pos <= nops(aut) do
if marks[pos] then
clen := 0; cpos := pos;

while marks[cpos] do
marks[cpos] := false;
cpos := numa[cpos];
clen := clen+1;
od;

cycs := [op(cycs), clen];
fi;

pos := pos+1;
od;

return mul(a[cycs[k]], k=1..nops(cycs));
end;

pet_vperm2eperm :=
proc(vperm)
local allsubs, e, eperm, el;

allsubs :=
[seq(pet_verts[pos]=vperm[pos], pos=1..nops(vperm))];

return subs(allsubs, pet_edges);
end;

pet_cycleind_petersen_edges :=
proc()
option remember;
local vperm, eperm, s;

s := 0;

for vperm in pet_vautom do
eperm := pet_vperm2eperm(vperm);
s := s + pet_autom2cycles(pet_edges, eperm);
od;

s/nops(pet_vautom);
end;

pet_varinto_cind :=
proc(poly, ind)
local subs1, subs2, polyvars, indvars, v, pot, res;

res := ind;

polyvars := indets(poly);
indvars := indets(ind);

for v in indvars do
pot := op(1, v);

subs1 :=
[seq(polyvars[k]=polyvars[k]^pot,
k=1..nops(polyvars))];

subs2 := [v=subs(subs1, poly)];

res := subs(subs2, res);
od;

res;
end;

pet_cycleind_petersen_edges();
latex(%);

gf := pet_varinto_cind(x+y, pet_cycleind_petersen_edges());

latex(gf);

latex(expand(gf));

subs({x=1, y=1}, gf);


Addendum Mar 24 2016. A much improved solution to this problem is at the following MSE link which renders the above obsolete.

Using Burnside’s lemma is the right idea.

Each element of $S_5$ determines a permutation of the 15 edges of the Petersen graph. If this permutation has exactly $r$ cycles on edges, then it fixes exactly $2^r$ 2-colorings of the edge set. If $a$ and $b$ are conjugate elements of $S_5$, then the permutations of the edges they determine have the same cycle structure.
(To proof this, observe that the induced permutations are conjugate in $S_{15}$,
and hence have the same cycle structure.)

So you just have to compute $r$ for one element in each conjugacy class, which is mildly tedious at worst, and then apply Burnside.