Graph automorphism group

Question

Let $A_w$ denote such set of positive integer $n$ that: for any two permutations $\pi_0,\pi_1\in S_n$, if $\pi_1$ is not a power of $\pi_0$, then there exists a (labeled non oriented) graph $G$ of size $n$ such that $\pi_0\in Aut(G)$ and $\pi_1\notin Aut(G)$.

Let $A_s$ denote such set of positive integer $n$ that: for any permutation $\pi \in S_n$, there exists a (labeled non oriented) graph $G$ of size $n$ with $Aut(G) = \langle\pi\rangle$. (Pointed by @Ycor.)

Q1: Is $A_w$ or even $A_s$ infinite?

Q2: Does $A_w$ or even $A_s$ contain almost all positive integers?

Q3: What are the smallest elements in these two sets?

Is there any known results? (Papers on this subjects are welcomed.)

Answer 1

Here is a complete answer.

• The answer to Q1 is 'no, because $A_w=\{1,2\}$ and $A_s=\{1\}$'.

• The answer to Q2 is 'no, $A_w$ contains merely two, while $A_s$ contains merely one element.

• The answer to Q3 is 'the smallest element of $A_w$ and $A_s$ is 1'.

This will follow from Propositions 1 and 2 below.

Digression with a view towards future research.

The question is easy primarily because the OP used universal quantifiers in the definitions of the sets, instead of

asking to characterize which permutations 'force' which.

While a complete answer to the OP's question will be given below, a more ambitious interpretation of the OP's question is another, not quite literal one: to formulate it, first define, for any $(\pi_0,\pi_1)\in\mathfrak{S}_n\times\mathfrak{S}_n$,

$\pi_0$ forces $\pi_1$

to mean:

for every graph $G$ on $n$, if $\pi_0$ is an automorphism of $G$, then $\pi_1$ is an automorphism of $G$ too.

(Obviously, 'forces' is a reflexive and transitive binary relation; it is not symmetric whenever $n\geq 3$. It is also not in general antisymmetric: e.g., if for any $t$ coprime to $n$, the cycle $\pi:=(0,1,\dotsc,n-1)$ forces $\pi^t$, but $\pi^t\neq\pi$ also forces $\pi$. So 'forces' in general is neither an equivalence relation nor a partial order.)

The obvious ambitious interpretation is:

Given $n\in\omega$, characterize the relation 'forces', i.e., characterize the set $F(n) = \{ (\pi_0,\pi_1)\in\mathfrak{S}_n\times\mathfrak{S}_n\colon\ \pi_0\ \mathrm{forces}\ \pi_1\}$

Moreover:

Analyze the decision-problem of deciding membership in $F(n)$.

This seems a difficult research question. E.g., it is very doubtful whether in general there is a polynomially-sized certificate for membership in $F(n)$.

Answer to the question.

Let $n=\{0,1,\dotsc,n-1\}$, and if $E\subseteq[n]^2:=\{ e\mid e\subseteq n, \lvert e\rvert=2\}$, then we write $\mathrm{Aut}(n,E)$ for the automorphism group of the graph $(n,E)$.

For any $n\in\omega$ let

$S(n) := \{ (\pi_0,\pi_1)\in\mathfrak{S}_n\times\mathfrak{S}_n\colon\quad \pi_1\notin\langle\pi_0\rangle \}\subsetneq\mathfrak{S}_n\times\mathfrak{S}_n$.

Define the formula

$\xi(\pi_0,\pi_1)$ $\qquad:=\qquad$ $\exists E\subseteq[n]^2\quad\pi_0\in\mathrm{Aut}(n,E)$ $\wedge$ $\pi_1\notin\mathrm{Aut}(n,E)$.

(The only free variables are $\pi_0$ and $\pi_1$.)

Your question concerns the set

$A_w$ $:=$ $\biggl\{\ n\in\omega\biggl|\quad \forall (\pi_0,\pi_1)\in S(n) \qquad \xi(\pi_0,\pi_1) \biggr\}$

$\textbf{Proposition 1.}$ $A_w=\{1,2\}$.

Proof of Proposition 1. For $n\in\{1,2\}$, any permutation of $n$ is cyclic, hence $S(n)=\emptyset$, hence the universal quantifier in $A_w$ vacously satisfied. Hence $\{1,2\}\subseteq A_w$.

To prove $\{1,2\}\supseteq A_w$, we prove the equivalent statement $\{ a\in\omega\mid\ a\geq 3\}\cap A_w = \emptyset$.

Let any $n\geq 3$ be given. Let $\cdot\ \text{m}\ n$ be an abbreviation for $\cdot\ \text{mod}\ n$, i.e., the function

$\mathbb{Z}\longrightarrow n$

$a\longmapsto$ unique smallest non-negative element of the set $\{ a+ nz\mid z\in\mathbb{Z}\}$.

Let $\pi_0\colon n\to n$ be defined by

$\pi_0(i)=(i+1)\ \mathrm{m}\ n$.

(Needless to say, the usual notation is $\pi_0=(0,1,\dotsc,n-1)$. We'll have use for the above formulation later.)

Define

$\pi_1\colon n\longrightarrow n$

$i\longmapsto (n-i)\ \text{m}\ n$.

Then $\pi_1$ is not a power of $\pi_0$ (because if there was $e\in\omega$ with $\pi_1=\pi_0^e$, then in particular $\pi_1(0)=\pi_0(0)^e$ and $\pi_1(1)=\pi_0(1)^e$, i.e. $(n-0)\ \mathrm{m}\ n = e\cdot(0+1)\ \mathrm{m}\ n$ and $(n-1)\ \mathrm{m}\ n = e\cdot(1+1)\ \mathrm{m}\ n$, i.e. $0=e\ \mathrm{m}\ n$ and $(n-1)\ \mathrm{m}\ n=2e\ \mathrm{m}\ n$, which implies the contradiction $0=(n-1)\ \mathrm{m}\ n$).

Hence $(\pi_0,\pi_1)\in S(n)$; thus, if we prove that $\xi(\pi_0,\pi_1)$ is false, then $n\notin A_w$ and the proof is complete.

Now, $\xi(\pi_0,\pi_1)$ being false is equivalent to

$\forall E\subseteq[n]^2\quad\pi_0\notin\mathrm{Aut}(n,E)$ $\vee$ $\pi_1\in\mathrm{Aut}(n,E)$ $\hspace{50pt}$ (N).

We now prove (N); let any $E\subseteq[n]^2$ be given. If $\pi_0\notin\mathrm{Aut}(n,E)$, there is nothing to show; so we may assume

$\pi_0\in\mathrm{Aut}(n,E)$ $\hspace{170pt}$ (cir)

We now show that (cir) implies $\pi_1\in\mathrm{Aut}(n,E)$; to this end, let any $\{i,j\}\in E$ be given.

We'll show

$\{\pi_1(i),\pi_1(j)\}\in E$ $\hspace{160pt}$ (h) .

No matter whether $n$ is even or odd,

$s:=s(i,j):= i+j - \frac{n - ( n \ \mathrm{m}\ 2)}{2}$

is an integer, and

$E$ $\ni$ $\{\pi_0^{\frac{n + ( n \ \mathrm{m}\ 2)}{2}-s}(i),\pi_0^{\frac{n + ( n \ \mathrm{m}\ 2)}{2}-s}(j)\}\hspace{50pt}$ (because of (cir) and $\{i,j\}\in E$, and since powers of automorphisms are automorphisms)

$=$ $\{ \ (i + \frac{n + ( n \ \mathrm{m}\ 2)}{2}-s)\ \mathrm{m} \ n,\ (j + \frac{n + ( n \ \mathrm{m}\ 2)}{2}-s)\ \mathrm{m} \ n \ \}\hspace{40pt}$ (by definition of $\pi_0$)

$=$ $\{ \ i + \frac{n + ( n \ \mathrm{m}\ 2)}{2}-(i+j-\frac{n - ( n \ \mathrm{m}\ 2)}{2})\ \mathrm{m} \ n\ ,\ j + \frac{n + ( n \ \mathrm{m}\ 2)}{2}-(i+j-\frac{n - ( n \ \mathrm{m}\ 2)}{2}) \ \mathrm{m} \ n\ \}\hspace{25pt}$ (by definition of $s$)

$=$ $\{ \ (n-j)\ \mathrm{m} \ n\ ,\ (n-i)\ \mathrm{m} \ n \ \}$

$=$ $\{ \ \pi_1(j)\ ,\ \pi_1(i) \ \}\hspace{50pt}$ (by definition of $\pi_1$)

$=$ $\{ \ \pi_1(i)\ ,\ \pi_1(j) \ \}\hspace{50pt}$ (axiom of extensionality)

proving (h). We have completed the proof that $\xi(\pi_0,\pi_1)$ is false, i.e. $n\notin A_w$. Since $n\geq 3$ was arbitrary, the proof of Proposition 1 is complete.

$\textbf{Proposition 2.}$ $A_s=\{1\}$.

Proof of Proposition 2. It is evident that $1\in A_2$. Moreover, $2\notin A_s$, because there does not exist a graph on two vertices with trivial automorphism group, but the definition of $A_s$ in partiular demands that there be a graph $(n,E)$ with $\mathrm{Aut}(n,E)=\langle\mathrm{id}\rangle$. Furthermore, if $n\geq 3$, then the exact same argument as given in the proof of Proposition 1 above proves that the defining-condition of the set $A_s$ is false at least for the permutation $\pi:=(0,1,\dotsc,n-1)$, which because of the universal quantifier already implies $n\notin A_s$. This completes the proof of Proposition 2.

Remark 1. Obviously, the above argument would not work for directed graphs, essentially because $( \ \pi_1(j)\ ,\ \pi_1(i) \ )$ $\neq$ $(\ \pi_1(i)\ ,\ \pi_1(j) \ )$.

Remark 2. The condition (cir) is equivalent to $(n,E)$ being a circulant graph. The argument in the proof of Proposition 1 is the simplest argument I can imagine that circulants never have cyclic automorphism group.

Remark 3. As predicted in an earlier version of this answer, circulant graphs are sufficient to answer the OP's question, but for the more ambitious interpretation, considering circulant graphs is not enough.

Remark 4. (added March 26, 2018) I worked out the sets $F_{\mathrm{ct}}(1)$, $F_{\mathrm{ct}}(2)$, $F_{\mathrm{ct}}(3)$, $F_{\mathrm{ct}}(4)$, $F_{\mathrm{ct}}(5)$ in full. To describe the results, it is useful to reduce to cycle types. We prepare by:

Remark 5. (added April 6, 2018) I worked out the set $F_{\mathrm{ct}}(6)$ in full.

Data relevant to the research problem of understanding $F_{\mathrm{ct}}(n)$.

A pdf containing a superset of the data given in this thread can be found here. (The hosting service permits downloading the---with 2,6 MB rather large--- pdf-file via the icon on the left-hand side.) The pdf in particular contains a table of the 78 isomorphism types of graph pairs of complementary unlabelled graphs on six vertices, together with all cycle types of permutations of $n=6$. Please use these data sceptically; while I checked the tables once, I was going rather fast and it is not improbable that an error remains. In particular the largest table required working through 858 decisions of whether a cycle type occurs or not, hence even if my probablity of getting a cell of table perfectly right is, say, 99%,the expectation of the number of mistakes is still 8.58. I would appreciate to be be notified of errors and will correct them.

Let me also mention that so far I did not get round to checking the data with a computer; the most serious reason for why I didn't is that

it seems not to be trivial to calculate the conjugacy classes of an arbitrary given permutation group; this is a recognized problem in computer algebra, but from what I gather from the specialized literature, good algorithms are known only under additional hypotheses about the permutation group. Remarkably, for generic permutation groups, the literature has nothing better to offer except some sort of Las Vegas algorithm (choosing elements of the permutation group randomly until a generating set has been found). I did not try to program this yet; the table was constructed manually.

$\textbf{Lemma 1.}$ For any $n\in\omega$, any graph $G=(n,E)$ on $n$, and any permutation $\sigma\in\mathfrak{S}_n$, for any automorphism $\pi$ of $G$, the permutation $\sigma \pi \sigma^{-1}$ is an automorphism of the graph $\sigma G:=(n,\sigma E)$, where $\sigma E:=\{\{\sigma(i),\sigma(j)\}\colon \{i,j\}\in E\}$.

Proof. We have to show that $\{i,j\}\in \sigma E$ iff $ \{ ( \sigma \pi \sigma^{-1} )(i) , ( \sigma\pi \sigma^{-1} )(j) \} \in \sigma E$.

First assume

(1) $\{i,j\}\in \sigma $.

Then there is $\{i',j'\}\in E$ with $i = \sigma(i')$ and $j = \sigma(j')$. So, $\{ ( \sigma \pi \sigma^{-1} )(i) , ( \sigma \pi \sigma^{-1} )(j) \}$ $=$ $\{ ( \sigma \pi \sigma^{-1} )(\sigma(i')) , ( \sigma \pi \sigma^{-1} )(\sigma(j')) \}$ $=$ $\{ \sigma (\pi(i')) , \sigma (\pi(j'))\}$. Since (1) together with $\pi$ being a homomorphism imply $\{\pi(i'),\pi(j')\}\in E$, it now follows that $\{ \sigma (\pi(i')) , \sigma (\pi(j')) \} $ is an edge of $\sigma E$, as required.

Conversely, consider an any $i,j\in n$ with

(2) $ \{ ( \sigma \pi \sigma^{-1} )(i) , ( \sigma\pi \sigma^{-1} )(j) \} \in \sigma E$.

We have to show that $\{i,j\}$ $\in$ $\sigma E$. By definition of $\sigma E$, it follows that $ \{ ( \pi \sigma^{-1} )(i) , ( \pi \sigma^{-1} )(j) \}$ $\in$ $E$. Since $\pi$ is an automorphism of $(n,E)$, it follows that $\{ \sigma^{-1}(i) , \sigma^{-1}(j) \}$ $\in$ $E$; by definition of $\sigma E$ it follows that $\{ i , j\}$ $=$ $\{ \sigma(\sigma^{-1}(i)) , \sigma(\sigma^{-1}(j)) \}$ $\in$ $\sigma E$, as required. This completes the proof of Lemma 1.

Now, let us repeat the definition of $F(n)$ from the digression at the beginning, together with its cycle-type-version:

$\textbf{Definition}$($F(n)$, $F_{\text{ct}}(n)$)$\textbf{.}$ For every $n\in\omega$ let

$F(n):=\{(\pi_0,\pi_1)\in\mathfrak{S}_n\times\mathfrak{S}_n\mid \forall E\subseteq [n]^2\quad \pi_0\notin\text{Aut}(n,E) \vee \pi_1\in\text{Aut}(n,E) \}$,

let $P(n)$ denote set of integer-partitions of $n$, for every $\lambda\in P(n)$ let $\Pi(\lambda)$ denote the set of all $\pi\in\mathfrak{S}_n$ with $\text{cycletype}(\pi)=\lambda$, and let

$F_{\text{ct}}(n):=\{(\lambda_0,\lambda_1)\in P(n)\times P(n) \mid \forall E\subseteq [n]^2\forall(\pi_0,\pi_1)\in\Pi(\lambda_0)\times\Pi(\lambda_1)\quad \pi_0\notin\text{Aut}(n,E) \vee \pi_1\in\text{Aut}(n,E) \}$.

It follows from Lemma 1 that

$F(n) = \bigcup\limits_{(\lambda_0,\lambda_1)\in F_{\text{ct}}(n)}\Pi(\lambda_0)\times\Pi(\lambda_1)$

In that sense, all information about the relation 'forces', i.e., about the set $F(n)$, is contained in the relation $F_{\text{ct}}(n)$.

The set $F_{\text{ct}}(n)$ is obviously reflexive and transitive, and not symmetric for every $n\geq 3$. While we are at it, let me mention that I currently do not see an answer to the following:

Question. Is $F_{\text{ct}}(n)$ a poset for all $n$ except $n=2$? I.e., is it antisymmetric unless $n=2$?

The following Figures 1--5 give the binary relations $F_{\text{ct}}(n)$ for $n\in\{1,2,3,4,5\}$. In particular, the diagonal elements are represented by loops.

Figures 6 and 7 are self-explanatory proofs of Figures 1--5. (You'll probably have to zoom.) I ignore the identity permutations. Obviously, it is sufficient to only consider one representative of equivalence classes of the equivalence relation of 'being a complement of one another'. The relevant entry in the OEIS is https://oeis.org/A007869. Incidentally, I am a little surprised that there, the interpretation "isomorphism classes of edge-2-colored complete graphs w.r.t. the obvious notion of isomorphism(i.e. permutation of vertex-labels, and permutations of edge-colors)" is missing.

Figure 1. The poset $F_{\mathrm{ct}}(1)$. Its ground set is the 1-element set of integer partitions of the number $1$. A proof of the correctness of Figure 1 is not given; it is obvious.

Figure 2. The non-poset $F_{\mathrm{ct}}(2)$. Its ground set is the 2-element set of integer partitions of the number $2$. (I do not know whether $n=2$ is the only number for which the relation $F_{\mathrm{ct}}(n)$ is non-antisymmetric.) A proof of the correctness of Figure 2 is not given; it is obvious.

Figure 3. The poset $F_{\mathrm{ct}}(3)$. Its ground set is the 3-element set of integer partitions of the number $3$. A proof of the correctness of Figure 3 is not given; it is obvious.

Figure 4. The poset $F_{\mathrm{ct}}(4)$. Its ground set is the 5-element set of integer partitions of the number $4$. A proof of the correctness of Figure 3 is constituted by Figure 6.

Figure 5. The poset $F_{\mathrm{ct}}(5)$. Its ground set is the 7-element set of integer partitions of the number $5$. A proof of the correctness of Figure 5 is given by Figure 7.

Figure 6. The poset $F_{\mathrm{ct}}(6)$. Its ground set is the 11-element set of integer partitions of the number $6$. A proof of the correctness of Figure 6 is given by the relevant table in the pdf.

Hasse diagrams of the posets $F_{\mathrm{ct}}(3),\dotsc,F_{\mathrm{ct}}(6)$

Figure 7. Hasse diagram of the poset $F_{\mathrm{ct}}(3)$.

Figure 8. Hasse diagram of the poset $F_{\mathrm{ct}}(4)$.

Figure 9. Hasse diagram of the poset $F_{\mathrm{ct}}(5)$.

Figure 10. Hasse diagram of the poset $F_{\mathrm{ct}}(6)$.

Tables with conditional probabilities w.r.t. the uniform distribution

Figure 11. Conditional probabilities of a given cycle type of a permutation of $3$ forcing a permutation of another given cycle type.

Figure 12. Conditional probabilities of a given cycle type of a permutation of $4$ forcing a permutation of another given cycle type.

Figure 13. Conditional probabilities of a given cycle type of a permutation of $5$ forcing a permutation of another given cycle type.

Figure 14. Conditional probabilities of a given cycle type of a permutation of $6$ forcing a permutation of another given cycle type.

Animated tables proving Figures 8, 9, 12, 13.

Figure 6. Animated gif with which to determine which cycle types of automorphisms are forced by other cycle types of automorphisms, on $n=4$ vertices.

Figure 7. Animated gif with which to determine which cycle types of automorphisms are forced by other cycle types of automorphisms, on $n=5$ vertices. The frequency should be low enough to, if one wants to check the tables, easily take screenshots of the relevant table.

It seems useful to spell-out the implications encoded in the digraphs above as English sentences (I skip (0) the trivial cases $n\in\{1,2\}$, (1) the tautologies represented by the loops, and (2) the trivial conclusion that any automorphism forces the identity-automorphism):

$n=3$.

• For any graph on $3$, if it has an automorphism of cycle-type $3$, then it has an automorphism of cycle-type $2+1$.

$n=4$

• For any graph on $4$, if it has an automorphism of cycle-type $4$, then it has an automorphism of cycle-type $2+2$.

• For any graph on $4$, if it has an automorphism of cycle-type $3+1$, then it has an automorphism of cycle-type $2+1+1$.

$n=5$

• For any graph on $5$, if it has an automorphism of cycle-type $5$, then it has an automorphism of cycle-type $2+2+1$.

• For any graph on $5$, if it has an automorphism of cycle-type $4+1$, then it has an automorphism of cycle-type $2+2+1$.

• For any graph on $5$, if it has an automorphism of cycle-type $3+2$, then it has an automorphism of cycle-type $3+1+1$, and an automorphism of type $2+2+1$, and an automorphism of cycle-type $2+1+1+1$.

• For any graph on $5$, if it has an automorphism of cycle-type $3+1+1$, then it has an automorphism of cycle-type $2+1+1+1$.

In particular, automorphisms of cycle type $3+2$ are the smallest example of a symmetry which always forces more than one non-conjugate further symmetries (and there it happens to be three: $3+1+1$, $2+2+1$, $2+1+1+1$).

Sadly, I don't see a principle governing the data. I've little hope that there's a nice law to be discovered; e.g., the height of the posets $F_{\mathrm{ct}}(n)$ is not monotone in $n$: while $F_{\mathrm{ct}}(5)$ has height $4$, the poset $F_{\mathrm{ct}}(6)$ has height $3$ again.

Answer 2

Peter and YCor already gave a counterexample, so this answer is just some additional commentary. I'll ignore loops for simplicity. If $\varGamma$ is a permutation group on $\lbrace 1,\ldots, n \rbrace$, then the 2-closure $\varGamma_2$ of $\varGamma$ is the largest subgroup of $S_n$ such that the orbits of $\varGamma_2$ on the set of unordered pairs $\lbrace v,w\rbrace$ are the same as the orbits of $\varGamma$ on the set of unordered pairs. Clearly $\varGamma\le\varGamma_2$. (Google "2-closure" and "orbital" for tons of references and more information.)

Now, the key observation is that every automorphism group of a graph is 2-closed; i.e. it is equal to its own 2-closure. So to find counterexamples to your question just find any $\pi_0$ such that $\langle \pi_0\rangle$ is not 2-closed. YCor's example is a permutation with one cycle: for $n\ge 3$ and $\pi_0=(1\,2\,\ldots\,n)$, the 2-closure of $\langle \pi_0\rangle$ also contains an additional $n$ elements of order 2 (think of the reflections of a regular polygon about a line through the centre).

(Incidentally, many sources define "2-closed" using ordered pairs rather than unordered pairs. For undirected graphs we need unordered pairs.)

ADDED.

I'll start but not yet complete a full description of the set $F(n)$ defined by Peter. To recap: $F(n)$ is the set of all pairs $(\pi_0,\pi_1)$ of permutations in $S_n$ such that every $n$-vertex graph $G$ that has $\pi_0$ as an automorphism also has $\pi_1$ as an automorphism. Describing $F(n)$ is equivalent to describing the groups $\Gamma_{\pi_0}=\lbrace \pi_1 \mid (\pi_0,\pi_1)\in F(n)\rbrace$. ($\Gamma_{\pi_0}$ is a group because the intersection of groups is a group.)

The cases $n=1$ and $n=2$ are trivial and so is the case $n\ge 3, \pi_0=(1)$; I'll leave them for the reader. Assume that $n\ge 3 $ and that $\pi_0$ is not the identity.

Two obvious facts, the first by definition the second by symmetry:
(1) $\langle \pi_0\rangle\le \Gamma_{\pi_0}$.
(2) For any $\gamma\in S_n$, $\Gamma_{\pi_0^\gamma}=\Gamma_{\pi_0}^\gamma$, where exponentiation denotes conjugacy.
Fact (2) says that we only need be concerned with the cycle structure of $\pi_0$.

So take $\pi_0\in S_n$ and let the cycles $C_1,C_2,\ldots,C_k$ of $\pi_0$ have lengths $\ell_1\ge \ell_2\ge\cdots\ge\ell_k$.

For $1\le j\le k$, let $D_j$ be the unique dihedral group of degree $\ell_j$ that contains $C_j$. (Think of $C_j$ as the rotational symmetries of a regular $\ell_j$-gon and $D_j$ as the full symmetry group including reflections.) For small orbits with $\ell_j\le 2$, take $D_j=C_j$. Now define $\Gamma^*_{\pi_0}= D_1\oplus \cdots \oplus D_k$. By a $t$-gon we mean a single vertex if $t=1$, a single edge if $t=2$ and a (graph) cycle of length $t$ if $t\ge 3$. If we insert a $t$-gon into a $t$-cycle of $\pi_0$, we'll assume that the $t$-cycle is an automorphism of the $t$-gon.

Lemma 1. $~\Gamma_{\pi_0}\le \Gamma^*_{\pi_0}$.
Proof. For any $\ell_j\ge 2$, take a graph with an $\ell_j$-gon in $C_j$ and isolated vertices elsewhere. The automorphism group fixes $C_j$ setwise, so $\Gamma_{\pi_0}$ does too. If there are any 1-cycles, connect them into a path and connect one end of the path to some $t$-cycle ($t\ge 2$) into which insert a $t$-gon. No more edges. The automorphism group fixes each of the 1-cycles, so $\Gamma_{\pi_0}$ does too. Thus we have proved that $\Gamma_{\pi_0}$ fixes the cycle partition of $\pi_0$ cell-wise. Now take a graph in which $C_j$ contains an $\ell_j$-gon for every $j$ and no extra edges. The subgroup of its automorphism group that fixes the cycle partition of $\pi_0$ cell-wise is $\Gamma^*_{\pi_0}$. This completes the proof. $\square$

To complete the determination of $\Gamma_{\pi_0}$, we have to determine which elements of $\Gamma^*_{\pi_0}$ preserve all possible joins between different cycles. This is slightly complicated because it depends on arithmetic properties: the number of edges between $C_i$ and $C_j$ is divisible by the least common multiple of $\ell_i$ and $\ell_j$. On the bright side, the solution for two cycles should imply the solution for any number of cycles. I need to think of how to do it smoothly.