(REF )
\(X\)  has Wilson type (REF ) with parameters \(H = \langle 2\rangle = \lbrace 0,2,4,6\rbrace \) , \(R=\lbrace 4\rbrace \) , and \(d=4\) . (Then \(n/d = 2\)  is even, \(r/d = 1\)  for the unique element \(r\)  of \(R\) , and \(H = 2 \mathbb {Z}_8 \lnot \subset 4 \mathbb {Z}_8 = d\mathbb {Z}_8\) .) See val5Nontrivial for an explanation that \(X\)  is therefore nontrivially unstable.
(REF  and REF )
Let
\( X_0 = \operatorname{Cay}(\mathbb {Z}_8,\lbrace  \pm 1, \pm 3\rbrace ) \cong K_{4,4} . \) 
Since \(X_0\)  is bipartite, we know that \(BX_0\)  is isomorphic to the disjoint union of two copies of \(X_0\) . But \(BX\)  is connected, and the element \((\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}, 1)\)  of order 2 is the only element of its connection set that is not in the connection set of \(BX_0\) . It follows that

\( BX \ \cong \ X_0 \mathbin {\square }\) 
K2   K4,4 \(\square \)K2 .
\(So we see from {Aut(C4timesX)} that the set of \) 
nnnn\(-edges is invariant under all automorphisms of \) BX\(. On the other hand, \) K4,4\( is edge-transitive, so the other edges are all in a single orbit.\)
Lemma 5.6 
Let \(X = \operatorname{Cay}(\mathbb {Z}_n, S)\)  be a nontrivially unstable, circulant graph of valency 5.
If the set of \(n/2\) -edges is not invariant under \(\operatorname{Aut}BX\) , then:


\(X = \operatorname{Cay}(\mathbb {Z}_{12k},\lbrace  \pm s, \pm 2k, 6k \rbrace )\) , for some \(s,k \in \mathbb {Z}^+\) , with \(s\)  odd,
and


\(\operatorname{Aut}BX\)  has exactly two orbits on the set of edges of \(BX\) .


Write
\( X = \operatorname{Cay}(\mathbb {Z}_n, \lbrace \pm a, \pm b, \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\rbrace ) .\) 
By assumption, some automorphism of \(BX\)  maps an \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) -edge to an \(a\) -edge (perhaps after interchanging \(a\)  and \(b\) ).
Then order2orbit shows that every generator of \(\langle a \rangle \)  is in \(S \setminus \lbrace \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\rbrace \) . So the number of generators of \(\langle a \rangle \)  is \(\le 4\)  (and \(|a| > 2\) ), so \(|a| \in \lbrace 3, 4, 5, 6, 8, 12\rbrace \) .
Case 1. 
Assume \(|a| \in \lbrace 5, 8, 12\rbrace \) .
The four generators of \(\langle a \rangle \)  are in \(S\) , so they must coincide with \(\pm a\)  and \(\pm b\) . Therefore, \(\langle a, \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\rangle = \langle a, b, \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\rangle = \mathbb {Z}_n\) , so \(n \in \lbrace 10, 8, 12\rbrace \) . Therefore, \(X\)  is one of the following Cayley graphs:
\( \text{$\operatorname{Cay}(\mathbb {Z}_{10},\lbrace \pm 2, \pm 4, 5\rbrace )$,$\operatorname{Cay}(\mathbb {Z}_8,\lbrace \pm 1, \pm 3, 4 \rbrace )$,or$\operatorname{Cay}(\mathbb {Z}_{12},\lbrace \pm 1, \pm 5, 6 \rbrace )$.} \) 
Note that the first and third graphs appear in small under (REF ) and (REF ) respectively, and are therefore both stable. val5Z8(REF ) implies that the second graph is also not possible (since the statement of the val5nhNotInvt requires that the set of \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) -edges is not invariant under \(\operatorname{Aut}BX\) ).
So this val5nhNotInvtPf-a5812 cannot occur.
Case 2. 
Assume \(|a| \in \lbrace 3,4,6\rbrace \) .
Note that then \(\pm a\)  are the only generators of \(\langle a \rangle \) . Because all elements of \(S\)  are pairwise distinct, it follows that \(\langle a \rangle \ne \langle b \rangle \) . Therefore, \(|a|\ne |b|\) .
Subcase 2.1. Assume \(|b|\in \lbrace 3,4,6\rbrace \) .
We consider each of the three possibilities for \(\lbrace  |a|, |b| \rbrace \) :
Subsubcase 2.1.1. Assume \(\lbrace  |a|, |b| \rbrace  = \lbrace 3, 4\rbrace \) .
Then
\( X = \operatorname{Cay}(\mathbb {Z}_{12},\lbrace \pm 3, \pm 4, 6\rbrace ) . \) 
This graph is stable by small(REF ).
Subsubcase 2.1.2. Assume \(\lbrace  |a|, |b| \rbrace  = \lbrace 3, 6\rbrace \) .
Then
\( X = \operatorname{Cay}(\mathbb {Z}_6,\lbrace \pm 1, \pm 2,3\rbrace ) \cong K_6 . \) 
This graph is stable by KnStable.
Subsubcase 2.1.3. Assume \(\lbrace  |a|, |b| \rbrace  = \lbrace 4, 6\rbrace \) .
Then
\( X = \operatorname{Cay}(\mathbb {Z}_{12},\lbrace \pm 2, \pm 3, 6\rbrace ) . \) 
This graph appears in part (REF ) of the statement of the val5nhNotInvt with parameters \(s = 3\)  and \(k = 1\) .
Also note that
\( BX = \operatorname{Cay}( \mathbb {Z}_{12} \times \mathbb {Z}_2 , \lbrace  \pm (2,1), \pm (3,1), (6,1) \rbrace ) .\) 
Since \(\langle (3,1) \rangle \cap \langle (2,1) , (6,1) \rangle = \lbrace 0,0\rbrace \) , this implies

\( BX\cong C_4 \mathbin {\square }\) 
Cay( 2Z12 Z2 , { (2,1), (6,1) })
C4 \(\square \)M6
,
\(where \) 
6\( is the Möbius ladder with 6~vertices.Then {Aut(C4timesX)} implies that \) BX\( is not edge-transitive. Since \)nnnn\(-edges are in the same orbit as \) a\(-edges, this establishes part~\textup {(}\ref {val5nhNotInvt-orbits}\textup {)} of the statement of the {val5nhNotInvt} for this graph.\)
Subcase 2.2. 
Assume \(|b|\notin \lbrace 3,4,6\rbrace \) .
From here, we see from order2orbit that no automorphism of \(BX\)  can map an \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) -edge to a \(b\) -edge (because \(S\)  cannot contain more than 2 generators of \(\langle b \rangle \) , in addition to \(\pm a\) ). Hence, the set of \(b\) -edges is invariant under all automorphisms of \(BX\) . (Note that this establishes part (REF ) of the statement of the val5nhNotInvt for this val5nhNotInvtPf-a346-bNot346.) Now, we see that every automorphism of \(BX\)  is also an automorphism of the graphs
\(BX_1 &\operatorname{Cay}\bigl (\mathbb {Z}_n \times \mathbb {Z}_2,\lbrace (\pm a,1),(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}},1)\rbrace \bigr ) \\\multicolumn{2}{l}{\text{and}}\\BX_2 &\operatorname{Cay}\bigl (\mathbb {Z}_n \times \mathbb {Z}_2, \lbrace (\pm b,1)\rbrace ) ,\) 

which are the canonical double covers of
\( \text{$X_1\operatorname{Cay}\bigl (\mathbb {Z}_n, \lbrace \pm a, \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\rbrace )$\ and \ $X_2\operatorname{Cay}\bigl (\mathbb {Z}_n, \lbrace \pm b\rbrace )$,} \) 
respectively. Note that \(BX_1\)  is arc-transitive (because \(a\) -edges and \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) -edges are in the same orbit of \(\operatorname{Aut}BX\) ).
If \(|a|=3\) , then every connected component of \(BX_1\)  is isomorphic to a 6-prism, which is not arc-transitive.
If \(|a|=4\) , then every connected component of \(X_1\)  is isomorphic to \(K_4\) , which is a stable graph by KnStable, so it follows from StableSubgraph that \(X\)  is stable, a contradiction.
Therefore, we must have \(|a|=6\) .
The connected components of \(X_2\)  are \(|b|\) -cycles. If \(|b|\)  is odd, then these are stable (by OddCirculant, for example). By another application of StableSubgraph, it follows that \(X\)  is stable, a contradiction.
So we can now assume that \(|a| = 6\)  and \(|b|\)  is even. Write \(n=6\ell \) . From here \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}= 3\ell \)  and \(\lbrace \pm a\rbrace  = \lbrace \ell ,5\ell \rbrace \) .
Note that if \(\ell \)  is odd, then \(a\)  and \(b\)  must both be odd (since \(|a|\)  and \(|b|\)  are even). Since \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}= 3\ell \)  is also odd, this means that all elements of \(S\)  are odd, so \(X\)  is bipartite, a contradiction.
Therefore, we know that \(\ell \)  is even, so we may write \(\ell = 2k\) . Then \(n = 12k\) , \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}= 6k\)  and \(\lbrace \pm a\rbrace  = \lbrace \pm 2k\rbrace \) . In particular, \(\pm a\)  and \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\)  are all even. So \(c\)  must be odd (since \(X\)  is connected). This means that \(X\)  appears in part (REF ) of the statement of the val5nhNotInvt with parameter \(s = c\) .
\((\Leftarrow )\)  It suffices to show that each of the graphs in (REF ) and (REF ) has the specified Wilson type.
For any member of (REF ), it holds that \(S_e = \lbrace 2k,6k,10k\rbrace \) ; therefore \(4k+S_e = S_e\) , so the graph has Wilson type (REF ).
For the graph in (REF ), see val5Z8(REF ).
\((\Rightarrow )\)  Assume \(X = \operatorname{Cay}(\mathbb {Z}_n, S)\)  has valency 5, and is nontrivially unstable. Then either val5nhInvt or val5nhNotInvt must apply (depending on whether the set of \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) -edges is invariant or not). So \(X\)  is one of the graphs listed in these two val5nhInvts, and is therefore listed in the statement of the val5.
Combining val5nhInvt,val5Z8,val5nhNotInvt also yields the following observation that will be used in val7Sect:
Corollary 5.7 
If \(X\)  is a nontrivially unstable, 5-valent, circulant graph, then \(\operatorname{Aut}BX\)  has exactly two orbits on the edges of \(BX\) .

Unstable circulants of valency 6
See explicit6 for a more explicit formulation of the following val6.
Theorem 6.1 
Every nontrivially unstable, circulant graph of valency 6 has Wilson type (REF ), (REF ), (REF ), or (REF ).

Let \(X = \operatorname{Cay}(\mathbb {Z}_n, S)\)  be a nontrivially unstable, circulant graph of valency 6, and write \(S = \lbrace \pm a, \pm b, \pm c\rbrace \) . The proof is by contradiction, so assume that \(X\)  does not have any of the four listed Wilson types.
As usual, we let \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}= n/2\) , for convenience.
The proof considers several val6pf-2a=2bs.
Case 1. 
Assume \(2a = 2b\) .
This means \(b = a + \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\)  (and \(-b = -a + \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) ). Since \(X\)  does not have Wilson type (REF ), we also know that
\( (S \cap 2\mathbb {Z}_n) \ne \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}+ (S \cap 2\mathbb {Z}_n) . \) 
Therefore, we must have \(S \cap 2\mathbb {Z}_n \ne \lbrace \pm a, \pm b\rbrace \) . Since \(S \lnot \subseteq 2 \mathbb {Z}_n\) , this implies
\( \lbrace a,b\rbrace  \lnot \subseteq 2\mathbb {Z}_n. \) 
We claim that \(|c|\)  is not divisible by 4. To see this, note that otherwise \(n/{\gcd (c,n)} = |c|\)  is even, so \(c/{\gcd (c,n)}\)  is odd, and we also know that \(|2c|\)  is even, so \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\in \langle 2c \rangle \) . This contradicts the fact that \(X\)  does not have Wilson type (REF ) (with \(H = \langle \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\rangle \) , \(R = \lbrace \pm c\rbrace \) , and \(d = \gcd (c, n)\) ). This completes the proof of the claim.
Also note that \(2c \notin \lbrace \pm 2a, \pm 2b\rbrace \) . (For example, if \(2c = 2a\) , then, since \(c \ne a\) , we must have \(c = a + \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}= b\) , which contradicts the fact that \(a\) , \(b\) , and \(c\)  must be distinct, because \(|S| = 6\) .) Furthermore, since \(|c|\)  is not divisible by 4, we also know that \(|c| \ne 4\) , so \(2c \ne -2c\) . Thus, we have
\( 2c \notin \lbrace \pm 2a, \pm 2b, -2c \rbrace . \) 

Therefore, we see from 2S'-BX (with \(S^{\prime } = \lbrace \pm c\rbrace \) ) that
\( \begin{matrix}\text{every automorphism of $BX$ is also an} \\\text{automorphism of $\operatorname{Cay}(\mathbb {Z}_n \times \mathbb {Z}_2 , \lbrace (\pm 2c, 0)\rbrace  \bigr )$.}\end{matrix}\) 
We now consider two val6pf-onlys.
Subcase 1.1. 
Assume \((c,1)\)  is the only common neighbor of \((0,0)\)  and \((2c,0)\)  in \(BX\) .
Let \(\alpha \)  be an automorphism of \(BX\)  that fixes \((0,0)\) , but does not fix \((0,1)\) .
Combining (REF ) with the assumption of this val6pf-only implies that \(\alpha \)  must preserve the set of \(c\) -edges.
If \(|c|\)  is odd, then letting \(S_0 = \lbrace \pm c\rbrace \)  in StableSubgraph implies that \(X\)  is stable (because cycles of odd length are stable), which is a contradiction.
Therefore, since \(|c|\)  is not divisible by 4, we must have \(|c| \equiv 2 \ (\mathrm {mod}~4)\) , so \((|c|/2) \cdot (c,1) = (\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}},1)\) , so this implies that
\( \text{$\alpha \bigl ( v + (\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}},1) \bigr ) = \alpha (v) + (\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}},1)$ for every vertex $v$ of~$BX$.} \) 
Also note that, since \(\alpha \)  preserves the set of \(c\) -edges in \(BX\) , it must also preserve the complement, which consists of the \(a\) -edges and \(b\) -edges. Hence, \(\alpha \)  is an automorphism of the canonical double cover of the 5-valent circulant graph \(X^{\prime } = \operatorname{Cay}(\mathbb {Z}_n, S^{\prime })\) , where \(S^{\prime } = \lbrace \pm a, \pm b, \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\rbrace \) .
Let \(X^{\prime }_0\)  be the connected component of \(X^{\prime }\)  that contains 0.
Note that \(X^{\prime }_0\)  is not stable (since \(\alpha \)  does not fix \((0,1)\) ). Also note that \(X^{\prime }_0\)  is connected, by definition. Furthermore, it is not bipartite, because \(X\)  is not bipartite and \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}= kc\)  where \(k\)  is odd. We therefore see from nottwinfree that it is also twin-free. So \(X^{\prime }_0\)  is nontrivially unstable, and must therefore be one of the graphs listed in val5 (after identifying the cyclic group \(V(X_0^{\prime })\)  with some \(\mathbb {Z}_m\)  by a group isomorphism). Since \(2a = 2b\) , it follows that \(X^{\prime }_0\)  is the graph in part (REF ) of the val5, so
\( X^{\prime } = \operatorname{Cay}(\mathbb {Z}_n,\lbrace \pm n/8, \pm 3n/8, \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\rbrace ) . \) 
Therefore, if we write \(|c| = 2k\) , where \(k\)  is odd, then
\( X = \operatorname{Cay}(\mathbb {Z}_{8k}, \lbrace  \pm k, \pm 3k, \pm c \rbrace  ) . \) 
So \(X\)  has Wilson type (REF ), with \(H = \langle 2k \rangle \) , \(R = \lbrace \pm c\rbrace \) ,
\( d = \gcd (c, 8k) = \frac{8k}{|c|} = \frac{8k}{2k} = 4 , \) 
and \(H \nsubseteq d \mathbb {Z}_{8k}\) .
Subcase 1.2. 
Assume \((c,1)\)  is not the only common neighbor of \((0,0)\)  and \((2c,0)\)  in \(BX\) .
This implies that
\( \text{$2c$ is equal to either $-2c$ or $a - c$ or $2a$ or $a + b$ or $a-b$} \) 
(perhaps after interchanging \(a\)  with \(b\)  and/or replacing both of them with their negatives).
However, we know from (REF ) that \(2c \ne -2c\)  and \(2c \ne 2a\) . Also, if \(2c=a-b=\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) , then \(|c| = 4\) , which contradicts the fact that \(|c|\)  is not divisible by 4. Thus, only two possibilities need to be considered.
Subsubcase 1.2.1. 
Assume \(2c = a + b = 2a + \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) .
Since \(2a\)  and \(2c\)  are even, this implies \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\)  is even, which means \(n \equiv 0 \ (\mathrm {mod}~4)\) . It also implies that \(a\)  and \(b\)  have the same parity, so we conclude from (REF ) that \(a\)  and \(b\)  are odd. Since \(X\)  is not bipartite, then \(c\)  must be even. Therefore,
\( 0 \equiv 2c = 2a + \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\equiv 2 + \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\ (\mathrm {mod}~4), \) 
so \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\equiv 2 \ (\mathrm {mod}~4)\) , which means \(n/4\)  is odd. Also note that \(4c = 4a = 4b\) . Therefore, setting \(k n/4\) , we get that
\( X = \operatorname{Cay}(\mathbb {Z}_{4k},\lbrace \pm c, \pm (c + k), \pm (c - k) \rbrace ) . \) 
If \(c \equiv 0 \ (\mathrm {mod}~4)\) , this graph has Wilson type (REF ) (with \(h = k\) ).
So we may assume \(c \equiv 2 \ (\mathrm {mod}~4)\) .
We will show that this implies \(X\)  is stable (which is a contradiction).
Any two vertices of \(BX\)  that are in the same coset of the subgroup \(\langle (k, 0) \rangle \)  have 4 common neighbors, 
\(\begin{pmatrix} \text{see} \\[-3pt] \text{note} \\[-3pt] \text{\ref {val6pf-same-coset}} \end{pmatrix}\) but no two vertices of \(BX\)  that are in different cosets of \(\langle (k, 0) \rangle \)  have more than 3 common neighbors. 
\(\begin{pmatrix} \text{see} \\[-3pt] \text{note} \\[-3pt] \text{\ref {val6pf-diff-cosets}} \end{pmatrix}\) Therefore, each coset of \(\langle (k, 0) \rangle \)  is a block for \(\operatorname{Aut}BX\) .
Also note that \((c + 2k,1)\)  is the only element of the coset \((c,1) + \langle (k, 0) \rangle \)  that is not adjacent to \((0,0)\) . So every automorphism of \(BX\)  must preserve the set of \((c + 2k)\) -edges.
Since \(c + 2k\)  is an element of odd order (because \(c + 2k \equiv 2 + 2 \equiv 0 \ (\mathrm {mod}~4)\)  and \(n = 4k\)  is not divisible by 8), we conclude from StableSubgraph that \(X\)  is stable.
Subsubcase 1.2.2. Assume \(2c = a - c\) .
This implies \(a = 3c\) , so
\( \mathbb {Z}_n = \langle a, b, c \rangle = \langle 3c, 3c + \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}, c \rangle = \langle c, \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\rangle . \) 
If \(|c|\)  is even, we know that \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\in \langle c \rangle \) , so \(\langle c \rangle = \mathbb {Z}_n\) .
This implies that \(c\)  is odd, so \(\lbrace a,b\rbrace  \cap 2\mathbb {Z}_n \ne \emptyset \)  (because \(X\)  is not bipartite). Since \(\lbrace a,b\rbrace  \lnot \subseteq 2\mathbb {Z}_n\) , this implies \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\)  is odd (i.e., \(n \equiv 2 \ (\mathrm {mod}~4)\) ). And 2S'-BX (together with (REF )) implies that \(\langle 2(c,1) \rangle = 2 \mathbb {Z}_n \times \lbrace 0\rbrace \)  is a block for the action of \(\operatorname{Aut}BX\) . Then, since \(|S \cap 2\mathbb {Z}_n| = 2 \le 5\) , we see from InterchangeCI-valency that \(X\)  has Wilson type (REF ) or (REF ).
We may now assume that \(|c|\)  is odd.
Since \(2a=2b\)  and we may assume that val6pf-notonly-a+b does not apply, it is easy to see that \(X\)  is stable by 2aneqs+t, which is a contradiction.
Case 2. 
Assume \(|a| = 4\) , and the previous val6pf-2a=2b does not apply.
Subcase 2.1. Assume some automorphism of \(BX\)  maps an \(a\) -edge to a \(b\) -edge.
Then order2orbit tells us that \(S\)  contains every generator of \(\langle b \rangle \) . Since \(|S| = 6\)  (and the only generators of \(\langle a \rangle \)  are \(\pm a\) ), it follows that \(\phi (|b|) \le 4\) . We also know \(|b|\ge 3\) , so we conclude that
\( |b|\in \lbrace 3,4,5,6,8,10,12\rbrace  . \) 
Also note that if \(\phi (|b|) = 4\) , then \(\lbrace \pm b, \pm c\rbrace \)  consists of the 4 generators of \(\langle b \rangle \) , so \(n = \operatorname{lcm}\bigl ( |a|, |b| \bigr ) = \operatorname{lcm}\bigl ( 4, |b| \bigr )\) .
\(\bullet \)  If \(|b|=4\) , then \(a\)  and \(b\)  are generators of the same cyclic subgroup of order 4, but then \(\lbrace \pm a\rbrace  = \lbrace \pm b\rbrace \) , a contradiction.
\(\bullet \)  If \(|b| \in \lbrace 5,10\rbrace \) , then \(\phi (|b|) = 4\) , so \(\lbrace \pm b, \pm c\rbrace \)  consists of the 4 generators of \(\langle b \rangle \) , and we have \(n = \gcd \bigl ( 4, |b| \bigr ) = 20\) . If \(|b| = 5\) , then \(X\)  is isomorphic to
\( \operatorname{Cay}(\mathbb {Z}_{20},\lbrace  \pm 4, \pm 5, \pm 8 \rbrace ) \) ;
if \(|b|=10\) , then \(X\)  is isomorphic to
\(\operatorname{Cay}(\mathbb {Z}_{20},\lbrace  \pm 2, \pm 5, \pm 6 \rbrace ) \) .
Both of these graphs are stable by small(REF ).
\(\bullet \)  If \(|b| \in \lbrace 8,12\rbrace \) , then \(\lbrace \pm a \rbrace  \subseteq \langle b \rangle \) , and \(a\)  is not a generator of this subgroup. So the other two generators of \(\langle b \rangle \)  must be \(\pm c\) . This implies that \(b\)  and \(c\)  each generate the whole group \(\mathbb {Z}_n\) . If \(|b| = 8\) , then \(X\)  is isomorphic to
\(\operatorname{Cay}(\mathbb {Z}_8,\lbrace  \pm 1, \pm 2, \pm 3 \rbrace )\) ,
which is not twin-free since \(4 + S = S\) . If \(|b| = 12\) , then \(X\)  is isomorphic to
\(\operatorname{Cay}(\mathbb {Z}_{12},\lbrace  \pm 1, \pm 3, \pm 5 \rbrace )\) ,
which is bipartite.
\(\bullet \)  We may now assume \(|b| \in \lbrace 3,6\rbrace \) .
We consider two val6pf-a=4-atob-36s.
Subsubcase 2.1.1. 
Assume \(|b| \in \lbrace 3,6\rbrace \)  and \(|c| \in \lbrace 3,6\rbrace \) .
If \(|c|=|b|\) , then \(b\)  and \(c\)  generate the same cyclic subgroup, which has only two generators, which contradicts the fact that \(\lbrace \pm b\rbrace  \ne \lbrace \pm c\rbrace \) . So we may assume \(|b|=3\)  and \(|c|=6\) . Then \(X\)  is isomorphic to
\(\operatorname{Cay}(\mathbb {Z}_{12},\lbrace  \pm 2, \pm 3, \pm 4 \rbrace )\) ,
which is not twin-free since \(6 + S = S\) .
Subsubcase 2.1.2. Assume \(|b| \in \lbrace 3,6\rbrace \)  and \(|c| \notin \lbrace 3,6\rbrace \) .
Then we can assume that no isomorphism of \(BX\)  maps an \(a\) -edge to a \(c\) -edge (for otherwise an earlier argument would apply after interchanging \(b\)  and \(c\) ). Since \(a\) -edges can be mapped to \(b\) -edges, this implies that no \(b\) -edge can be mapped to a \(c\) -edge. Therefore, every automorphism of \(BX\)  is an automorphism of \(BX_0\) , where \(X_0 = \operatorname{Cay}(\mathbb {Z}_n,\lbrace \pm a, \pm b\rbrace )\) . Let \(X_0^{\prime }\)  be the connected component of \(X_0\)  that contains 0. Recalling that \(|a|=4\) , we see that if \(|b|=3\)  then
\( X_0^{\prime }\)  is isomorphic to \(\operatorname{Cay}(\mathbb {Z}_{12},\lbrace  \pm 3, \pm 4 \rbrace ) \) ,
and if \(|b|=6\) , then
\( X_0^{\prime }\)  is isomorphic to \(\operatorname{Cay}(\mathbb {Z}_{12},\lbrace  \pm 2, \pm 3 \rbrace )\) .
Both of these graphs are stable (by small(REF ) or val4). So StableSubgraph tells us that \(X\)  is stable as well, a contradiction.
Subcase 2.2. Assume every automorphism of \(BX\)  maps \(a\) -edges to \(a\) -edges.
Then every automorphism of \(BX\)  is also an automorphism of \(BX_0\) , where \(X_0 = \operatorname{Cay}(\mathbb {Z}_n, \lbrace \pm b, \pm c\rbrace )\) . As usual, let \(X_0^{\prime }\)  be the connected component of \(X_0\)  that contains 0.
Subsubcase 2.2.1. Assume \(X_0\)  is not twin-free.
Then \(b = c + \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\)  (perhaps after replacing \(c\)  with \(-c\) ). Since \(a + \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}= -a\) , this implies \(S + \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}= S\) , which contradicts the fact that \(X\)  is twin-free.
Subsubcase 2.2.2. Assume \(X_0\)  is not connected (but is twin-free).
We know that \(X_0^{\prime }\)  is not stable (for otherwise StableSubgraph contradicts the fact that \(X\)  is not stable). Since \(X_0^{\prime }\)  is connected (by definition) and twin-free (by assumption), this implies that it has even order (see OddCirculant). Since \(\langle a, b, c \rangle = \mathbb {Z}_n\)  and \(|a| = 4\) , we conclude that \(\langle b, c \rangle = 2 \mathbb {Z}_n\)  and \(n \equiv 4 \ (\mathrm {mod}~8)\) .
\(\bullet \)  If \(X_0^{\prime }\)  is bipartite, then \(BX_0\)  is isomorphic to the union of four disjoint copies of \(X_0^{\prime }\) . Since \(|a| = 4\)  and \(BX\)  is connected, this implies that \(BX \cong C_4 \mathbin {\square }\) X0'\(.Since \) X0'\( has even valency, and \) |V(X0')|/2\( is odd, it it is easy to see that \) X0'\( does not have \) K2\( as a Cartesian factor. (If \) X0' K2 \(\square \)Y\(, then \) Y\( is a regular graph of odd valency and odd order, which is impossible.) This implies (by {Aut(C4timesX)}) that\)\( |{\operatorname{Aut}BX}| = |{\operatorname{Aut}(C_4 \mathbin {\square }}X_0^{\prime })\) |= |AutC4| |AutX0' | = 8   |AutX0' | .
\(Also note that, since \) 
0'\( is a bipartite circulant graph whose order is congruent to~\) 2\( modulo~\) 4\(, it is (isomorphic to) the canonical double cover of a circulant graph of odd order. Since connected, twin-free, circulant graphs of odd order are stable (see {OddCirculant}) and \) 2a\( is the element of order~\) 2\( in~\) Zn\(, we conclude that if \)\( is any automorphism of~\) X0'\(, then \) (v + 2a) = (v) + 2a\( for every \) v V(X0')\(. This implies that we can extend~\)\( to an automorphism~\) '\( of~\) X\( by defining \) '(a + v) = a + (v)\( for \) v V(X0')\(; so \) AutX\( contains a copy of \) AutX0'\(. Since \) AutX\( also contains the translation \) v v + a\( and the negation automorphism \) v -v\(, we conclude that\) |AutX| 4   |AutX0' |\(.Combining this with the above calculation of \) |AutBX|\( contradicts the fact that \) X\( is not stable.\)
\(\bullet \)  If \(X_0^{\prime }\)  is not bipartite, then \(X_0^{\prime }\)  is nontrivially unstable, and therefore must be described by val4. Since \(|2\mathbb {Z}_n| \equiv 2 \ (\mathrm {mod}~4)\) , we must be in the situation of REF (REF ): \(\langle c \rangle = 2 \mathbb {Z}_n\) , and \(b = mc + \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) , for some \(m \in \mathbb {Z}_n^\times \) , such that \(m^2 \equiv \pm 1 \ (\mathrm {mod}~n)\) . (Technically, val4 only tells us that \(m^2 \equiv 1 \ (\mathrm {mod}~n/2)\) . However, we know that \(m\)  is odd, so \(m^2 \equiv 1 \ (\mathrm {mod}~4)\) . Therefore \(m^2 \equiv 1 \ (\mathrm {mod}~n)\) .) We also have \(ma + \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}= \pm a\)  (since \(|a| = 4\) ). Therefore \(m S + \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}= S\) , which means that \(X\)  has Wilson type (REF ).
Subsubcase 2.2.3. Assume \(X_0\)  is connected and bipartite.
This means that \(b\)  and \(c\)  are odd, so \(S \cap 2\mathbb {Z}_n = \lbrace \pm a\rbrace \) . Since \(|a| = 4\) , we conclude that \((S \cap 2\mathbb {Z}_n) + \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}= (S \cap 2\mathbb {Z}_n)\) , so \(X\)  has Wilson type (REF ).
Subsubcase 2.2.4. Assume \(X_0\)  is nontrivially unstable.
Then val4 tells us that \(X_0\)  has Wilson type (REF ). Then \(X\)  also has Wilson type (REF ), with the same value of \(m\) .
Case 3. 
Assume neither of the previous val6pf-2a=2bs apply (even after permuting and/or negating some of the generators).
Let \(\alpha \)  be an automorphism of \(BX\)  that fixes \((0,0)\) .
The assumption of this val6pf-neither implies that \(2s \ne 2t\)  for all \(s,t \in S\) , such that \(s \ne t\) . Therefore, 2S'-BX implies that the cosets of \(2\mathbb {Z}_n \times \lbrace 0\rbrace \)  are blocks for the action of \(\operatorname{Aut}BX\) . So \(\alpha \)  must fix the two cosets that are in \(\mathbb {Z}_n \times \lbrace 0\rbrace \) , and either fixes or interchanges the other two. However, also note that \(S\)  is the disjoint union of
\( \text{$S_e S \cap 2\mathbb {Z}_n$ and $S_o S \cap (1 + 2 \mathbb {Z}_n)$.} \) 
Each of these two sets has even cardinality (since it is closed under inverses), and \(|S_e| + |S_o| = 6\) , so it is easy to see that \(|S_e| \ne |S_o|\) . Therefore, \(\alpha \)  cannot interchange \(S_e\)  and \(S_o\) , which means that \(\alpha \)  must fix all four cosets of \(2\mathbb {Z}_n \times \lbrace 0\rbrace \) . So
\( \text{$\alpha $ maps $S_e$-edges to $S_e$-edges, and maps $S_o$-edges to $S_o$-edges.}\) 

Hence, by StableSubgraph, we know that
\( \text{the connected components of $\operatorname{Cay}(\mathbb {Z}_n, S_e)$ are unstable.} \) 
(The connected components of \(\operatorname{Cay}(\mathbb {Z}_n, S_o)\)  are always unstable, since they are bipartite.) We also know that \(\operatorname{Cay}(\mathbb {Z}_n, S_e)\)  is twin-free (since \(X\)  does not have Wilson type (REF )). Therefore, we see from OddCirculant that \(|\langle S_e \rangle |\)  is even, so
\( n \equiv 0 \ (\mathrm {mod}~4) . \) 
From NormalCover, we see that \(BX\)  is not normal. So applying 4cyclenormal to \(BX\)  implies that
either  \(|a| = 4\)   or  \(3a = b\)   or  \(2a = 2b\)   or  \(2a = b + c\) 
(perhaps after permuting and/or negating some of the generators).
Since neither of the previous cases apply, this implies that
\( \text{either $3a = b$ or $2a = b + c$.} \) 
We will consider each of these two possibilities as a separate val6pf-neither-3a=3b.
Recall that CayleyDefn(REF ) introduced \(\tilde{s}\)  as an abbreviation for \((s,1)\)  with \(s\in S\) .
Subcase 3.1. 
Assume \(3a = b\) .
Then also \(3\tilde{a} = \tilde{b}\) .
We claim that \(|\tilde{a}| \ge 10\) . First of all, we have \(|\tilde{a}| \ne 2\) , because \(|a| \notin \lbrace 1,2\rbrace \) .
We also have \(|\tilde{a}| \ne 4\) , because \(|a| \ne 4\)  (since val6pf-a=4 does not apply).
Now, note that if \(|\tilde{a}|=6\) , then \(|a| = 3\)  or \(|a| = 6\) ; however, the fact that \(b = 3a\)  would then imply that \(|a| = 3|b|\) , so \(|b| \in \lbrace 1,2\rbrace \) , which is a contradiction.
Finally, note that if \(|a|=8\) , then \(2(-a) = -2a = 6a = 2(3a) = 2b\) , which contradicts the assumption that val6pf-2a=2b does not apply.
This completes the proof of the claim.
Subsubcase 3.1.1. Assume \(|\tilde{a}|=10\) .
Then \(|a|=5\)  or \(|a|=10\) . However, if \(|a|=5\) , then \(|b|=5\)  as well and they generate the same cyclic subgroup of \(\mathbb {Z}_n\) . In particular, the connected components of \(\operatorname{Cay}(\mathbb {Z}_n,\lbrace \pm a, \pm b\rbrace )\)  are isomorphic to \(K_5\) , which is stable, so by StableSubgraph, we get that \(X\)  is stable, a contradiction.
Therefore, we must have \(|a|=10\) . (Then \(|b|=10\)  and they generate the same cyclic subgroup.)
Since \(n \equiv 0 \ (\mathrm {mod}~4)\) , we may write
\( \text{$n = 20k$ for some $k \in \mathbb {Z}$.} \) 
Since \(|a| = |b| = 10 \lnot \equiv 0 \ (\mathrm {mod}~4)\)  and \(n \equiv 0 \ (\mathrm {mod}~4)\) , it is clear that \(|c|\)  is even (in fact, it is divisible by 4). It follows that \(|c|\)  is either \(n\)  (if \(|c|\)  is divisible by 5) or \(n/5\)  (otherwise). So we see that (up to isomorphism) \(X\)  is
\( \text{$\operatorname{Cay}(\mathbb {Z}_{20k},\lbrace \pm c,2k,6k,14k,18k\rbrace )$ \ with $c = 1$ or $c = 5$.} \) 
From (REF ), we know that \(\alpha \)  is also an automorphism of the graphs
\( Y_1 = \operatorname{Cay}(\mathbb {Z}_{20k}\times \mathbb {Z}_2,\lbrace (\pm c, 1)\rbrace ) \) 
and
\( Y_2 = \operatorname{Cay}(\mathbb {Z}_{20k}\times \mathbb {Z}_2,\lbrace (2k,1),(6k,1),(14k,1),(18k,1)\rbrace ) . \) 
Note that \((0,0)\)  and \((10k,1)\)  lie in the same connected component of \(Y_2\) , which is isomorphic to \(K_{5,5}-5K_2\) . In this component, \((10k,1)\)  is the unique vertex at distance 3 from \((0,0)\) , so \(\alpha \)  fixes \((10k,1)\) .
Also note that the vertices \((0,1)\)  and \((10k,1)\)  lie in the same connected component of \(Y_1\) , which is a cycle (of length \(20k\)  or \(4k\) ), and that these two vertices are diametrically opposite on this cycle. Since we already know that \(\alpha \)  fixes \((10k,1)\) , it must also fix \((0,1)\) . We conclude that \(X\)  is stable, a contradiction.
Subsubcase 3.1.2. Assume \(|\tilde{a}|=12\) .
Then \(|a|=12\) . Since \(b = 3a\) , we have \(|b|=|3a|=4\) , which contradicts the fact that val6pf-a=4 does not apply.
Subsubcase 3.1.3. 
Assume \(|\tilde{a}| \ge 14\) .
Let \(\mathsf {B}_2\)  be the subgraph induced by the ball of radius 2 centered at 0 in \(\operatorname{Cay}(\mathbb {Z}_n\times \mathbb {Z}_2, \lbrace \pm \tilde{a}, \pm \tilde{b}\rbrace )\) .
This graph is drawn in B2, under the assumption of this val6pf-neither-3a=3b-a>14 that \(|\tilde{a}| \ge 14\) . From this drawing, it can be seen that \(\pm \tilde{b}\)  are the only vertices in \(\mathsf {B}_2\)  that have a pendant edge. (These edges are colored white in the figure.) So \(\lbrace \pm \tilde{b}\rbrace \)  is \(\alpha \) -invariant. This means that \(\alpha \)  maps \(b\) -edges to \(b\) -edges. Since we already know that \(\alpha \)  maps \(c\) -edges to \(c\) -edges, it must also map \(a\) -edges to \(a\) -edges.
<FIGURE>In the terminology of [1]}, this means that \(\alpha \)  is a color-preserving graph automorphism. We will now use a simple argument from [1]} to establish that \(\alpha \)  is a group automorphism (so \(BX\)  is normal, and then it follows from NormalCover that \(X\)  has Wilson type (REF )).
We provide only a sketch of the proof.
By composing with negation, if necessary, we may assume that \(\alpha (\tilde{a}) = \tilde{a}\) . This implies \(\alpha (k \tilde{a}) = k \tilde{a}\)  for all \(k \in \mathbb {Z}\) . Let \(m \in \mathbb {Z}^+\) , such that \(m \tilde{c} \in \langle \tilde{a} \rangle \) . Then \(\alpha (k m \tilde{c}) = k m \tilde{c}\)  for all \(k \in \mathbb {Z}\) . If \(2 m \tilde{c} \ne 0\) , this implies that \(\alpha (\ell \tilde{c}) = \ell \tilde{c}\)  for all \(\ell \in \mathbb {Z}\) ; in fact, \(\alpha (k \tilde{a} + \ell \tilde{c}) = k \tilde{a} + \ell \tilde{c}\) , for all \(k,\ell \in \mathbb {Z}\) , which means that \(\alpha \)  is the identity map, contradicting the fact that \(\alpha \notin \operatorname{Aut}X \times \mathbb {Z}_2\) .
Therefore, we may assume \(2 m \tilde{c} = 0\) , for all \(m \in \mathbb {Z}\) , such that \(m \tilde{c} \in \langle \tilde{a} \rangle \) . This means that \(|\langle \tilde{c} \rangle \cap \langle \tilde{a} \rangle | \le 2\) , so there is a group automorphism of \(\mathbb {Z}_n\)  that fixes \(\tilde{a}\)  and negates \(\tilde{c}\) . So we may assume that \(\alpha (\tilde{c}) = \tilde{c}\) . Since \(\tilde{a} + \tilde{c}\)  is the only common neighbor of \(\tilde{a}\)  and \(\tilde{c}\) , we must have \(\alpha (\tilde{a} + \tilde{c}) = \tilde{a} + \tilde{c}\) . Similarly, we must have \(\alpha (2 \tilde{a} + \tilde{c}) = 2\tilde{a} + \tilde{c}\)  and \(\alpha (\tilde{a} + 2\tilde{c}) = \tilde{a} + 2\tilde{c}\) . Repeating the argument shows that \(\alpha (k \tilde{a} + \ell \tilde{c}) = k \tilde{a} + \ell \tilde{c}\) , for all \(k,\ell \in \mathbb {Z}\) , so, once again, \(\alpha \)  is the identity map.
Subcase 3.2. 
Assume \(2a = b + c\) .
(Note that this implies \(2\tilde{a} = \tilde{b} + \tilde{c}\) .)
We will show that \(\alpha (k \tilde{b} + \ell \tilde{a}) = k \alpha (\tilde{b}) + \ell \alpha (\tilde{a})\) , for all \(k, \ell \in \mathbb {Z}^{\ge 0}\) . (This implies that \(\alpha \)  is a group automorphism of \(\mathbb {Z}_n\) , so \(BX\)  is normal, so NormalCover implies that \(X\)  has Wilson type (REF ).)
Since \(b\)  and \(c\)  have the same parity, we see from (REF ) that \(\alpha \)  maps \(\lbrace b,c\rbrace \) -edges to \(\lbrace b,c\rbrace \) -edges, and maps \(a\) -edges to \(a\) -edges. In particular, we may assume (by composing with negation if necessary) that
\( \text{$\alpha $ fixes every element of~$\langle \tilde{a} \rangle $.}\) 
Since \(\alpha \)  maps \(\lbrace b,c\rbrace \) -edges to \(\lbrace b,c\rbrace \) -edges, \(\alpha \)  is an automorphism of the graph \(\operatorname{Cay}(\mathbb {Z}_n\times \mathbb {Z}_2,\lbrace \pm \tilde{b},\pm \tilde{c}\rbrace )\) , which has at most two connected components. Let \(X_0^{\prime }\)  be its connected component containing \((0,0)\)  with the vertex set \(\langle \tilde{b},\tilde{c}\rangle \) . Since \(\alpha \)  fixes \((0,0)\) , it restricts to an automorphism of \(X_0^{\prime }\) . Because we are assuming val6pf-2a=2b and val6pf-a=4 do not hold and we can additionally assume val6pf-neither-3a=3b does not hold either, 4cyclenormal applies to \(X_0^{\prime }\) . It follows that the restriction of \(\alpha \)  to \(V(X_0^{\prime })\)  is a group automorphism of \(\langle \tilde{b}, \tilde{c} \rangle \) . We let \(b^{\prime }, c^{\prime } \in \lbrace  \pm b, \pm c \rbrace \) , such that \(\alpha (\tilde{b}) = \tilde{b^{\prime }}\)  and \(\alpha (\tilde{c}) = \tilde{c^{\prime }}\) . It follows that:
\(\alpha (k\tilde{b} + \ell \tilde{c}) = k\tilde{b^{\prime }}+\ell \tilde{c^{\prime }} \qquad \forall k,\ell \in \mathbb {Z}\) 
Notice that:
\(\tilde{b} + \tilde{c} &= 2\tilde{a}&& (\text{assumption of {val6pf-neither-2a=b+c}})\\&= \alpha (2\tilde{a})&& \textup {(}\ref {val6pf-neither-2a=b+c-fixa}\textup {)}\\&= \alpha (\tilde{b}+ \tilde{c})&& \text{($2\tilde{a} = \tilde{b}+ \tilde{c}$)}\\&= \tilde{b}^{\prime } + \tilde{c}^{\prime }&& \textup {(}\ref {val6pf-2a=b+c-normal}\textup {)}. \) 
As we have already established that the hypothesis of 4cyclenormal holds, we obtain that \(\lbrace b^{\prime }, c^{\prime }\rbrace  = \lbrace b,c\rbrace \) .
To complete the proof of this val6pf-neither-2a=b+c, we now prove by induction on \(k\)  that, for all \(k,\ell \in \mathbb {Z}^{\ge 0}\) , we have
\( \alpha (k \tilde{b} + \ell \tilde{a}) = k \tilde{b}^{\prime } + \ell \tilde{a}. \) 
The base case is provided by (REF ), so assume \(k > 0\) .
Since \(\alpha \)  maps \(a\) -edges to \(a\) -edges, there exists \(\epsilon \in \lbrace \pm 1\rbrace \) , such that \(\alpha (k \tilde{b} + \ell \tilde{a}) = k \tilde{b}^{\prime } + \epsilon \ell \tilde{a}\)  for all \(\ell \in \mathbb {Z}\) . We wish to show \(\epsilon = 1\) , so suppose \(\epsilon = -1\) . (This will lead to a contradiction.) Letting \(\ell = -2\)  tells us
\((k -1) \tilde{b}^{\prime } - \tilde{c}^{\prime }&= \alpha \bigl ( (k -1) \tilde{b} - \tilde{c} \bigr )&& \text{\textup {(}\ref {val6pf-2a=b+c-normal}\textup {)}}\\&= \alpha (k \tilde{b} - 2\tilde{a})&& \text{($2 \tilde{a} = \tilde{b} + \tilde{c}$)}\\&= k \tilde{b}^{\prime } + 2 \tilde{a}&& (\epsilon = -1)\\&= k \tilde{b}^{\prime } + (\tilde{b} + \tilde{c})&& \text{($2 \tilde{a} = \tilde{b} + \tilde{c}$)}\\&= k \tilde{b}^{\prime } + (\tilde{b}^{\prime } + \tilde{c}^{\prime })&& (\lbrace b, c\rbrace  = \lbrace b^{\prime }, c^{\prime }\rbrace ). \) 

This implies \(-2\tilde{b}^{\prime } = 2 \tilde{c}^{\prime }\) , which contradicts the fact that val6pf-2a=2b does not apply.
The following result provides a more explicit version of val6. val6nontrivial explains which of these graphs are nontrivially unstable.
Corollary 6.8 
A circulant graph \(X = \operatorname{Cay}(\mathbb {Z}_n, \lbrace \pm a, \pm b, \pm c \rbrace )\)  of valency 6 is unstable if and only if either it is trivially unstable, or it is one of the following:



\(\operatorname{Cay}(\mathbb {Z}_{8k},\lbrace \pm a, \pm b, \pm 2k\rbrace )\) , where \(a\)  and \(b\)  are odd, which is of Wilson type (REF ).


\(\operatorname{Cay}(\mathbb {Z}_{4k},\lbrace \pm a, \pm b, \pm b + 2k\rbrace )\) , where \(a\)  is odd and \(b\)  is even, which is of Wilson type (REF ).


\(\operatorname{Cay}\bigl ( \mathbb {Z}_{4k}, \bigl \lbrace  \pm a, \pm (a + k), \pm (a - k) \bigr \rbrace  \bigr )\) , where \(a \equiv 0 \ (\mathrm {mod}~4)\)  and \(k\)  is odd, which is of Wilson type (REF ).


\(\operatorname{Cay}(\mathbb {Z}_{8k},\lbrace \pm a, \pm b, \pm b + 4k\rbrace )\) , where \(a\)  is even and \(|a|\)  is divisible by 4, which is of Wilson type (REF ).


\(\operatorname{Cay}(\mathbb {Z}_{8k},\lbrace \pm a, \pm k, \pm 3k\rbrace )\) , where \(a \equiv 0 \ (\mathrm {mod}~4)\)  and \(k\)  is odd, which is of Wilson type (REF ).


\(\operatorname{Cay}(\mathbb {Z}_{4k},\lbrace \pm a, \pm b, \pm m b + 2k \rbrace )\) , where
\( \text{$\gcd (m, 4k) = 1$, \quad $(m-1)a \equiv 2k \ (\mathrm {mod}~4k)$, \quad and} \) 
\( \text{either \ $m^2 \equiv 1 \ (\mathrm {mod}~4k)$\ or \ $(m^2 + 1) b \equiv 0 \ (\mathrm {mod}~4k)$,} \) 
which is of Wilson type (REF ).


\(\operatorname{Cay}(\mathbb {Z}_{8k},\lbrace \pm a, \pm b, \pm c \rbrace )\) , where there exists \(m \in \mathbb {Z}\) , such that
\( \text{$\gcd (m, 8k) = 1$, \quad $m^2 \equiv 1 \ (\mathrm {mod}~8k)$, \quad and} \) 
\( (m-1)a \equiv (m + 1)b \equiv (m + 1)c \equiv 4k \ (\mathrm {mod}~8k) , \) 
which is of Wilson type (REF ).


(\(\Leftarrow \) ) It is easy to see that each graph has the specified Wilson type, and is therefore unstable.
(The arguments in the other direction of the proof can provide some hints, if required.)
(\(\Rightarrow \) ) If \(X\)  is unstable, then we know from val6 that \(X\)  has Wilson type (REF ), (REF ), (REF ), or (REF ). We treat each of these possibilities as a separate case.
Case 1. Assume \(X\)  has Wilson type ( REF).
Subcase 1.1. Assume \(|S_e| = 2\) .
Then we may assume \(S_e = \lbrace \pm c \rbrace \) . Since \(X\)  has Wilson type (REF ), we must have \(-c = c + \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) , so \(|c| = 4\) . (Since \(c \in S_e\) , this implies that \(n\)  is divisible by 8.) Therefore \(X\)  is as described in part (REF ) of the explicit6.
Subcase 1.2. Assume \(|S_e| = 4\) .
Then we may assume \(S_e = \lbrace \pm b, \pm c\rbrace \) . Since \(X\)  has Wilson type (REF ) (and \(|S_e|\)  is a power of 2), we must have \(S_e + \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}= S_e\) . Therefore, we may assume \(c = b + \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\)  (because we cannot have \(b + \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}= -b\)  and \(c + \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}= -c\) ). Since \(b\)  and \(c\)  are even, this implies \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\)  is even, so \(n\)  is divisible by 4. Hence, \(X\)  is as described in part (REF ) of the explicit6.
Case 2. Assume \(X\)  has Wilson type ( REF).
Let \(h \in 1 + 2 \mathbb {Z}_n\) , such that (REF ) and (REF ) of condition (REF ) hold.
Subcase 2.1. Assume \(|S_o| = 2\) .
Then we may assume \(S_o = \lbrace \pm c\rbrace \) , so part (REF ) of (REF ) tells us \(-c = c + 2h\)  and \(c = -c + 2h\) . This implies that \(|c| = 4\)  and \(|h| = 4\) . So we may assume \(c = h = n/4\) . Then it is obvious that \(-c \equiv -h \ (\mathrm {mod}~4)\) , so part (REF ) of (REF ) implies that \(0 = -c + h \in S\) . This contradicts the fact that graphs in this paper do not have loops (see GraphsAreSimple).
Subcase 2.2. Assume \(|S_o| = 4\) .
Then we may assume \(S_o = \lbrace \pm b, \pm c\rbrace \) , so part (REF ) of (REF ) implies that we may assume \(c = b + 2h\)  (by replacing \(b\)  with \(-b\)  if necessary), and we must have \(|2h| \in \lbrace 2,4\rbrace \) .
Subsubcase 2.2.1. Assume \(|2h| = 2\) .
Then we have \(c = b + \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) . We may assume \(b \equiv -h \ (\mathrm {mod}~4)\)  (by interchanging \(b\)  and \(c\)  if necessary). So part (REF ) of condition (REF ) implies \(b + h \in S\) , which means \(a = b + h\)  (perhaps after replacing \(a\)  with \(-a\) ). In other words, we have \(b = a - h\) ; then \(c = b + 2h = a + h\) . Therefore, since \(|h| = 4\) , we have
\( S = \bigl \lbrace  \pm a, \pm \bigl ( a + (n/4) \bigr ), \pm \bigl ( a - (n/4) \bigr ) \bigr \rbrace  . \) 
We see from part (REF ) of condition (REF ) that \(S\)  contains an element that is divisible by 4, so we must have \(a \equiv 0 \ (\mathrm {mod}~4)\) .
Also, since \(a + (n/4) = b\)  is odd, we know that \(n/4\)  is odd.
Hence, \(X\)  is as described in part (REF ) of the explicit6.
Subsubcase 2.2.2. 
Assume \(|2h| = 4\) .
Then
\( \lbrace \pm b, \pm c\rbrace  = \lbrace b , b + 2h, b + 4h, b + 6h \rbrace , \) 
so \(-c = b + 4h\)  (and \(-b = b + 6h\) ). Since \(c = b + 2h\) , this implies \(2c2= 6h\)  has order 4, so \(|b| = 8\) . So \(S_o = \lbrace \pm n/8, \pm 3n/8 \rbrace \)  consists of all of the elements of order 8. Since \(-h\)  has order 8, we conclude that \(-h \in S_o\) , so part (REF ) of condition (REF ) implies \(0 \in S\) , which (again) contradicts the fact that graphs in this paper do not have loops.
Case 3. Assume \(X\)  has Wilson type ( REF).
Let \(H\) , \(R\) , and \(d\)  be as in the definition of Wilson type (REF ). We may assume that \(X\)  does not have Wilson type (REF ), so \(R\)  contains at least one element of \(S_e\) ; for definiteness, let us say that \(a\)  is in \(R \cap S_e\) . Since \(r/d\)  is odd for every \(r \in R\) , we know that all elements of \(R\)  have the same parity, so this implies \(R \subseteq S_e\) .
Subcase 3.1. Assume \(|R| = 2\) .
This means \(R = \lbrace \pm a\rbrace \) , \(d = \gcd (n,a)\) , and \(\lbrace \pm b, \pm c\rbrace  + H = \lbrace \pm b, \pm c\rbrace \) .
Let \(h\)  be a generator of \(H\) , so \(b + h = c\)  (perhaps after replacing \(c\)  with \(-c\) ).
Subsubcase 3.1.1. Assume \(|h| = 2\)  (so \(h = \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\)).
Since \(n/d\)  is even, we know that \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\in d \mathbb {Z}_n\) . Therefore, the last condition in (REF ) implies that \(|a|\)  is divisible by 4.
(Since \(a\)  is even, this implies that \(n\)  is divisible by 8.)
Hence, \(X\)  is as described in part (REF ) of the explicit6.
Subsubcase 3.1.2. Assume \(|h| = 4\) .
The argument of explicit6pf-C2-4-4 shows \(\lbrace \pm b, \pm c\rbrace  = \lbrace \pm n/8, \pm 3n/8\rbrace \) . Since the elements of \(S\)  cannot all be even, we know that \(n/8\)  is odd. Then, since \(a\)  is even, we know that \(2a \mathbb {Z}_n\)  does not contain an element of order 4, so we conclude from the last sentence of condition (REF ) that \(a \mathbb {Z}_n\)  does not contain \(H\) . This means that \(a\)  is divisible by 4.
Hence, \(X\)  is as described in part (REF ) of the explicit6.
Subcase 3.2. Assume \(|R| = 4\) .
This means we may assume \(R = \lbrace \pm a, \pm b\rbrace \) , \(H = \langle \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\rangle \) , and \(|c| = 4\) .
Since \(n/d\)  is even, we know that the elements of \(R\)  have even order, so \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\in \langle R \rangle = d \mathbb {Z}_n\) . Therefore, the last sentence of condition (REF ) implies \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\in 2 d \mathbb {Z}_n\) , which means \(n/d\)  is divisible by 4. Since \(r/d\)  is odd for every \(r \in R\) , this implies \(|a| \equiv |b| \equiv 0 \ (\mathrm {mod}~4)\) . Since \(a \in R \subseteq S_e\) , we conclude that \(n\)  is divisible by 8. So \(c = \pm n/4\)  is even. This contradicts the fact that at least one element of \(S\)  must be odd (since \(S\)  generates \(\mathbb {Z}_n\) ).
Case 4. Assume \(X\)  has Wilson type ( REF).
This means there exists \(m \in \mathbb {Z}\)  such that \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}+ m S = S\)  and \(\gcd (m, n) = 1\) . Let \(\alpha (x) \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}+ m x\) , so \(\alpha (S) = S\) .
Since \(|S_e| \ne |S_o|\) , we know that \(\alpha (S_e) \ne S_o\) . Therefore, we must have \(\alpha (S_e) = S_e\)  and \(\alpha (S_o) = S_o\) . This means that \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\)  is even (so \(n\)  is divisible by 4).
Assume, without loss of generality, that \(b\)  and \(c\)  have the same parity (and \(a\)  has the opposite parity).
We must have \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}+ m a \in \lbrace \pm a\rbrace \) . So we may assume \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}+ m a = a\)  (by replacing \(m \)  with \(-m \)  if necessary), so \((m -1)a = \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) .
We also have \(\alpha (\lbrace  \pm b, \pm c \rbrace ) = \lbrace  \pm b, \pm c \rbrace \) .
Therefore, either \(\alpha \)  fixes \(\lbrace \pm b \rbrace \)  and \(\lbrace \pm c\rbrace \) ,
or \(\alpha \)  interchanges these two sets.
Subcase 4.1. Assume \(\alpha (b) \in \lbrace  \pm b \rbrace \)  and \(\alpha (c) \in \lbrace  \pm c \rbrace \) .
This means \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}+ m b = \pm b\)  and \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}+ m c = \pm c\) , so
\((m \pm 1) b = \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\)  and \((m \pm 1) c = \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) . Since
\((m - 1) a = \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) , and \(a\)  has the opposite parity from \(b\) 
and \(c\) , we cannot have \((m - 1) b = \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\)  or \((m - 1)c = \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) .
Therefore, we must have \((m + 1) b = \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\)  and \((m + 1) c = \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) .
We know that \(m\)  is odd, so either \(m - 1\)  or \(m + 1\)  is divisible by 4. Since
\((m - 1)a = \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\)  and \((m + 1)b = \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) , this implies that \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\)  is divisible by 4.
So \(n\)  is divisible by 8
Note that, since \(m + 1\)  is even, we have
\( (m^2 - 1)a = (m + 1)(m - 1)a = (m + 1) \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}= 0 . \) 
Similarly, we also have \((m^2 - 1)b = 0\)  and \((m^2 - 1)c = 0\) .
Since \(\langle a, b, c \rangle = \mathbb {Z}_n\) , this implies that
\(m^2 \equiv 1 \ (\mathrm {mod}~n)\) . Hence, \(X\)  is as described in
part (REF ) of the explicit6.
Subcase 4.2. Assume \(\alpha (b) \in \lbrace  \pm c \rbrace \)  and \(\alpha (c) \in \lbrace  \pm b \rbrace \) .
We have \(\alpha ^2(b) \in \lbrace \pm b\rbrace \) , which means
\(\pm b = \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}+ m (\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}+ m b) = m ^2 b\) ,
so there exists \(\epsilon \in \lbrace \pm 1\rbrace \) , such that \((m ^2 + \epsilon ) b = 0\) .
Subsubcase 4.2.1. Assume \(\epsilon = -1\) .
This means \((m ^2 - 1) b = 0\) . Since \(m \)  must be odd, we also have
\((m ^2 - 1)a = (m + 1) \cdot (m -1) a = (m + 1) \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}= 0 \) 
and \((m ^2 - 1) \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}= 0\) . Since
\( \mathbb {Z}_n = \langle a, b, c \rangle = \langle a, b, \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}+ m b \rangle = \langle a, b, \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\rangle ,\) 
we conclude that \((m ^2 - 1) \mathbb {Z}_n = \lbrace 0\rbrace \) , so \(m ^2 \equiv 1 \ (\mathrm {mod}~n)\) .
Hence, \(X\)  is as described in part (REF ) of the explicit6 (with \(m^2 \equiv 1 \ (\mathrm {mod}~n)\) ).
Subsubcase 4.2.2. Assume \(\epsilon = 1\) .
This means \((m ^2 + 1) b = 0\) .
Hence, \(X\)  is as described in part (REF ) of the explicit6 (with \((m^2 + 1) b = 0\) ).
Remark 6.9 
It is easy to determine whether a graph in explicit6 is nontrivially unstable. Indeed, here are quite simple necessary and sufficient conditions for each of the lists in the statement of the explicit6:

\(\gcd (a, b, k) = 1\)  and \(b \notin \lbrace \pm a + 4k\rbrace \) .

\(\gcd (a, b, k) = 1\)  and \(a \notin \lbrace \pm k\rbrace \) .

\(\gcd (a, k) = 1\) .

\(\gcd (a, b, 4k) = 1\)  and \(a \notin \lbrace \pm 2k\rbrace \) .

\(\gcd (a, k) = 1\) .

\(\gcd (a, b, 2k) = 1\) , either \(a\)  or \(b\)  is even,
and either \(a \notin \lbrace \pm k\rbrace \)  or \(mb \notin \lbrace \pm b\rbrace \) .

\(\gcd (a, b, c, 4k) = 1\) , either \(a\)  or \(b\)  is even,
and either \(a \notin \lbrace \pm 2k\rbrace \)  or \(c \notin \lbrace \pm b + 4k\rbrace \) .


For convenience, let \(S = \lbrace \pm a, \pm b, \pm c\rbrace \) .
It is clear that \(X\)  is connected if and only if \(\gcd (S \cup \lbrace n\rbrace ) = 1\) . Therefore, the first condition in each part of the val6nontrivial is precisely the condition for \(X\)  to be connected.
Knowing that \(\gcd (S \cup \lbrace n\rbrace ) = 1\)  implies that at least one element of \(S\)  is odd (since \(n\)  is even). Therefore, \(X\)  is nonbipartite if and only if at least one element of \(S\)  is even. It is obvious that \(S\)  has an even element in all parts of explicit6 other than (REF ) and (REF ), so the statement of the val6nontrivial only adds this as an explicit condition for parts (REF ) and (REF ). (In part (REF ), the fact that \((m + 1)b \equiv (m + 1)c \equiv 4k \ (\mathrm {mod}~8k)\)  implies that \(b\)  and \(c\)  have the same parity, so there is no need to mention the possibility that \(c\)  is even.)
Now, let us suppose that \(X\)  is not twin-free (but is connected and nonbipartite). Then by nottwinfree(REF ), it follows that \(X\cong Y\wr \overline{K_m}\)  with \(Y\)  being a connected circulant of valency \(\delta \)  and \(m\ge 2\)  an integer. Clearly, \(6=\delta m\) , so \(m\in \lbrace 2,3,6\rbrace \) .

If \(m=6\) , then \(\delta =1\)  and \(Y\cong K_2\) . Consequently, \(X\cong K_2\wr \overline{K_6}\cong K_{6,6}\) , which contradicts the fact that \(X\)  is not bipartite.

If \(m=3\) , then \(\delta =2\)  and \(Y\)  is a cycle of even length, which again contradicts the fact that \(X\)  is not bipartite.

If \(m=2\) , then from the proof of nottwinfree(REF ), it can be concluded that the unique twin of 0 is \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) . Therefore, it must hold that \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}+ S = S\) .

Thus, we see that \(X\)  is twin-free if and only if \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}+ S \ne S\) .
In parts (REF ) and (REF ), it is clear that if \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}+ S = S\) , then \(a + \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}= -a\) , which means \(a = \pm n/4\) . Since \(a \equiv 0 \ (\mathrm {mod}~4)\) , this implies \(n\)  is divisible by 16, which contradicts the fact that \(k\)  is odd. So all of the graphs of these two types are twin-free. All other parts of the val6nontrivial add a final condition that specifically rules out the possibility that \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}+ S = S\) .

Unstable circulants of valency 7
Theorem 7.1 
A circulant graph \(\operatorname{Cay}(\mathbb {Z}_n, S)\)  of valency 7 is unstable if and only if either it is trivially unstable, or it is one of the following:



\(\operatorname{Cay}(\mathbb {Z}_{6k},\lbrace \pm 2t, \pm 2(k - t), \pm 2(k + t), 3k\rbrace )\) , with \(k\)  odd, which has Wilson type (REF ).


\(\operatorname{Cay}(\mathbb {Z}_{12k},\lbrace \pm 2k,\pm b,\pm c, 6k\rbrace )\) , with \(b\)  and \(c\)  odd, which has Wilson type (REF ).


\(\operatorname{Cay}(\mathbb {Z}_{20k},\lbrace \pm t,\pm 2k,\pm 6k,10k\rbrace )\) , with \(t\)  odd, which has Wilson type (REF ).


\(\operatorname{Cay}(\mathbb {Z}_{4k},\lbrace \pm t, \pm (k - t), 2k\pm t, 2k\rbrace )\) , with \(k\)  odd and \(t \equiv k \ (\mathrm {mod}~4)\) , which has Wilson type (REF ).


\(\operatorname{Cay}(\mathbb {Z}_{8k},\lbrace \pm 4t,\pm k,\pm 3k, 4k\rbrace )\) , with \(k\)  and \(t\)  odd, which has Wilson type (REF ).


\(\operatorname{Cay}(\mathbb {Z}_{12k},\lbrace \pm t, \pm (4k - t), \pm (4k + t), 6k\rbrace )\) , with \(t\)  odd, which has Wilson type (REF ).


Remark 7.2 It is easy to see that each connection set listed in val7 contains both even elements and odd elements, so none of the graphs are bipartite. Then it follows from nottwinfree(REF ) that the graphs are also twin-free. Therefore, a graph in the list is nontrivially unstable if and only if it is connected. And this is easy to check: a graph listed in val7 is connected if and only if \(\gcd (t,k) = 1\)  (except that the condition for part (REF ) is \(\gcd (b, c, k) = 1\) ).

Remark 7.3 In the statement of val7, it is implicitly assumed that \(k,t \in \mathbb {Z}^+\) . In order for the graphs to have valency 7, the parameters \(k\)  and \(t\)  (or \(k\) , \(b\) , and \(c\) ) must be chosen so that all of the listed elements of the connection set are distinct in the cyclic group. (Note that this implies \(k > 1\)  in parts (REF ), (REF ), and (REF ).)

\((\Leftarrow )\) 
This is the easy direction.
For each family of graphs in the statement of the val7, we briefly justify the specified Wilson type (which implies that the graphs are unstable):

Type (REF ) with \(S_e=\lbrace \pm 2t, \pm 2(k - t), \pm 2(k + t)\rbrace \)  and \(2k + S_e = S_e\) .

Type (REF ) with \(S_e=\lbrace \pm 2k,6k\rbrace \)  and \(4k+S_e=S_e\) .

Type (REF ) with \(S_e=\lbrace \pm 2k,\pm 6k,\pm 10k\rbrace \)  and \(4k+S_e=S_e\) .

Type (REF ) with \(h = k\)  and \(S_o = \lbrace \pm t, 2k \pm t\rbrace \) . Note that \(s \equiv 0\)  or \(-k \ (\mathrm {mod}~4)\)  if and only if
\( s \in \lbrace  -t, k - t, -(k - t), 2k + t \rbrace , \) 
in which case
\(s + k &\in \lbrace  k - t, 2k - t, t, -k + t\rbrace . \) 

(Note that \(-k + t = -(k - t)\)  is in the connection set.)

Type (REF ) with \(H = \langle 2k\rangle \) , \(R=\lbrace \pm 4t, 4k\rbrace \) , \(d = 4\) , \(n/d = 2k\) , \(\lbrace r/d\rbrace  = \lbrace t, k\rbrace \) , and \(H \lnot \subseteq d\mathbb {Z}_{8k}\) .

Type (REF ) with \(H=\langle 4k\rangle \) , \(R=\lbrace 6k\rbrace \) , \(d = 6k\) , \(n/d = 2\) , \(\lbrace r/d\rbrace  = \lbrace 1\rbrace \) , and \(H \lnot \subseteq d\mathbb {Z}_{12k}\) .

(\(\Rightarrow \) ) Let \(X = \operatorname{Cay}(\mathbb {Z}_n, S)\)  be a nontrivially unstable circulant graph of valency 7. Since the graph has odd valency (or by OddCirculant), \(n\)  must be even. We will write \(S=\lbrace \pm a, \pm b, \pm c, \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\rbrace \)  for its connection set.
Case 1. 
Assume there exists an automorphism of \(BX\)  that maps an \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) -edge to an \(a\) -edge.
By order2orbit, \(S\)  must contain every generator of \(\langle a \rangle \) . It follows that \(\phi (|a|) \le 6\)  (and we also know \(|a| \ne 2\) ). In particular, we obtain that
\( \text{$|a|$ is an element of the set $\lbrace 3,4,5,6,7,8,9,10,12,14,18\rbrace $.} \) 
We consider the following cases.
Subcase 1.1. Assume \(|a| \in \lbrace 7,9\rbrace \) .
Then \(S\)  must contain the 6 generators of \(\langle a \rangle \) . Since \(|a|\)  is odd, we know \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\notin \langle a \rangle \) , so we conclude that \(\mathbb {Z}_n = \langle a \rangle \times \langle \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\rangle \) . In particular, \(X\)  is one of the following:
\( \text{$\operatorname{Cay}(\mathbb {Z}_{14},\lbrace \pm 2, \pm 4, \pm 6, 7\rbrace )$ or $\operatorname{Cay}(\mathbb {Z}_{18},\lbrace \pm 2, \pm 4, \pm 8, 9\rbrace )$.} \) 
Note that the first graph appears in small(REF ), which contradicts the assumption that \(X\)  is (nontrivially) unstable. The second graph is listed in part (REF ) of the statement of the val7 (with parameters \(k=3\)  and \(t = 1\) ).
Subcase 1.2. Assume \(|a| \in \lbrace 14,18\rbrace \) .
Then \(S\)  again contains the 6 generators of \(\langle a \rangle \) . Additionally, since \(|a|\)  is even, we have \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\in \langle a \rangle \) . We conclude that \(a\)  generates \(\mathbb {Z}_n\)  and it follows that \(X\)  is one of the following:
\( \text{$\operatorname{Cay}(\mathbb {Z}_{14},\lbrace \pm 1, \pm 3, \pm 5, 7\rbrace )$ or $\operatorname{Cay}(\mathbb {Z}_{18},\lbrace \pm 1, \pm 5, \pm 7, 9\rbrace )$.} \) 
It is clear that both of these graphs are bipartite, which contradicts the assumption that \(X\)  is nontrivially unstable.
Subcase 1.3. 
Assume \(|a| = 5\) .
Then \(S\)  contains the 4 generators of \(\langle a \rangle \) . We may suppose without loss of generality that besides \(\pm a\) , the remaining two generators of \(\langle a \rangle \)  are \(\pm b\) .
Subsubcase 1.3.1. Assume \(|c| \in \lbrace 3,4,6\rbrace \) .
Then \(X\)  is one of the following graphs, all of which are stable by small.

\(|c| = 3 \Rightarrow X = \operatorname{Cay}(\mathbb {Z}_{30},\lbrace \pm 6,\pm 10,\pm 12, 15\rbrace )\) . See small(REF ).

\(|c| = 4 \Rightarrow X = \operatorname{Cay}(\mathbb {Z}_{20},\lbrace \pm 4,\pm 5,\pm 8,10\rbrace )\) . See small(REF ).

\(|c| = 6 \Rightarrow X = \operatorname{Cay}(\mathbb {Z}_{30},\lbrace \pm 5,\pm 6,\pm 12,15\rbrace )\) . See small(REF ).

Subsubcase 1.3.2. 
Assume \(|c| \notin \lbrace 3,4,6\rbrace \) .
From here, \(\langle c \rangle \)  has more than two generators, while \(\langle a\rangle = \langle b\rangle \)  has no generators besides \(\pm a,\pm b\) . Hence, there cannot exists an automorphism of \(BX\)  mapping an \(s\) -edge, with \(s \in S\setminus \lbrace \pm c\rbrace \) , onto a \(c\) -edge, since order2orbit would then imply that \(S\)  contains all generators of \(\langle c \rangle \) .
It follows the set of \(c\) -edges is invariant under \(\operatorname{Aut}BX\) . Hence, every automorphism of \(BX\)  maps \(S_0\) -edges to \(S_0\) -edges, where we define \(S_0\lbrace \pm a, \pm b, \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\rbrace \) . The connected components of \(\operatorname{Cay}(\mathbb {Z}_n,S_0)\)  are isomorphic to
\( \operatorname{Cay}(\mathbb {Z}_{10},\lbrace 2,4,5,6,8\rbrace ) . \) 
By small(REF ), this graph is stable. It then follows from StableSubgraph that \(X\)  is stable as well, a contradiction.
Subcase 1.4. Assume \(|a| = 8\) .
We may assume (as in val7Pf-NotInvt-a=5) that \(\pm a\)  and \(\pm b\)  are the four generators of \(\langle a \rangle \)  (which contains \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) , because \(|a|\)  is even).
Subsubcase 1.4.1. Assume \(|c|\in \lbrace 3,4,6\rbrace \) .
Then \(X\)  is one of the following graphs

\(|c| = 3\)  \(\Rightarrow \)  \(X = \operatorname{Cay}(\mathbb {Z}_{24},\lbrace \pm 3,\pm 8,\pm 9,12\rbrace )\) . This is stable, by small(REF ).

\(|c| = 4\)  \(\Rightarrow \)  \(X = \operatorname{Cay}(\mathbb {Z}_{8},\lbrace \pm 1,\pm 2,\pm 3,4\rbrace )\cong K_8\) . This is stable, by KnStable.

\(|c| = 6\)  \(\Rightarrow \)  \(X = \operatorname{Cay}(\mathbb {Z}_{24},\lbrace \pm 3,\pm 4,\pm 9,12\rbrace )\) . This graph appears in part (REF ) of the statement of the val7 (with parameters \(k=3\)  and \(t = 1\) ).

Subsubcase 1.4.2. Assume \(|c|\notin \lbrace 3,4,6\rbrace \) .
By the assumption of val7pf-NotInvt, there is an automorphism \(\alpha \)  of \(X\)  that maps an \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) -edge to an \(a\) -edge. By composing with translations on the left and right, we may assume that \(\alpha \)  fixes the vertex \((0,0)\) , and maps an \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) -edge that is adjacent to \((0,0)\)  to an \(a\) -edge that is adjacent to \((0,0)\) .
We see from order2orbit (by the same argument as in cinv) that the set of \(c\) -edges is invariant under all automorphisms of \(BX\) . So \(\alpha \)  restricts to an automorphism of \(BX_0^{\prime }\) , where \(X_0^{\prime }\)  is the connected component of \(\operatorname{Cay}(\mathbb {Z}_n,\lbrace \pm a, \pm b, \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\rbrace )\)  that contains 0. However, since \(X_0^{\prime } \cong \operatorname{Cay}(\mathbb {Z}_8,\lbrace \pm 1,\pm 3,4\rbrace )\) , we know from val5Z8(REF ) that the set of \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) -edges is invariant under all automorphisms of \(BX_0^{\prime }\) . This contradicts the choice of \(\alpha \) .
Subcase 1.5. Assume \(|a| = 10\) .
Once again, we may assume that \(\pm a\)  and \(\pm b\)  are the four generators of \(\langle a \rangle \)  (which contains \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) , because \(|a|\)  is even).
Subsubcase 1.5.1. Assume \(|c|\in \lbrace 3,4,6\rbrace \) .
Then \(X\)  is one of the following graphs:

\(|c| = 3\)  \(\Rightarrow \)  \(X = \operatorname{Cay}(\mathbb {Z}_{30},\lbrace \pm 3,\pm 9,\pm 10,15\rbrace )\) . By small(REF ), this graph is stable.

\(|c| = 4\)  \(\Rightarrow \)  \(X = \operatorname{Cay}(\mathbb {Z}_{20},\lbrace \pm 2,\pm 5,\pm 6,10\rbrace )\) . This graph appears in part (REF ) of the statement of the val7 (with parameters \(k=1\)  and \(t = 5\) ).

\(|c| = 6\)  \(\Rightarrow \)  \(X = \operatorname{Cay}(\mathbb {Z}_{30},\lbrace \pm 3,\pm 5,\pm 9,15\rbrace )\) . This is a bipartite graph, so trivially unstable.

Subsubcase 1.5.2. Assume \(|c|\notin \lbrace 3,4,6\rbrace \) .
Since \(|a| = 10\) , we may write \(n = 10m\) .
As before, we see from order2orbit that the set of \(c\) -edges is invariant under all automorphisms of \(BX\) . Then StableSubgraph implies that \(|c|\)  is even (since cycles of odd length are stable).
If \(m\)  is odd, then \(c\)  must also be odd (since \(|c|\)  is odd and \(n = 10m\)  is not divisible by 4), so all elements of \(S\)  are odd. Then \(X\)  is bipartite, which contradicts the assumption that \(X\)  is nontrivially unstable.
So \(m\)  must be even, which means we may write \(m = 2k\) . In this notation, we have \(X = \operatorname{Cay}(\mathbb {Z}_{20k},\lbrace \pm c, \pm 2k, \pm 6k,10k\rbrace )\) . Note that \(c\)  must be odd, since \(X\)  is not bipartite, so this is listed in part (REF ) of the val7 (with parameter \(t = c\) ).
Subcase 1.6. Assume \(|a| = 12\) .
Then \(S\)  contains the 4 generators of \(\langle a \rangle \) , which are without loss of generality \(\pm a\)  and \(\pm b\) .
Subsubcase 1.6.1. Assume \(|c| \in \lbrace 3,4,6\rbrace \) .
Then \(X\)  is one of the following graphs:

\(|c| = 3\)  \(\Rightarrow \)  \(X = \operatorname{Cay}(\mathbb {Z}_{12},\lbrace \pm 1,\pm 4,\pm 5,6\rbrace )\) . This is listed in part (REF ) of the val7 (with parameters \(k=3\)  and \(t = -1\) ).

\(|c| = 4\)  \(\Rightarrow \)  \(X = \operatorname{Cay}(\mathbb {Z}_{12},\lbrace \pm 1,\pm 3,\pm 5,6\rbrace )\) . This is listed in part (REF ) of the val7 (with parameters \(k = t = 1\) ).

\(|c| = 6\)  \(\Rightarrow \)  \(X = \operatorname{Cay}(\mathbb {Z}_{12},\lbrace \pm 1, \pm 2, \pm 5, 6\rbrace )\) . This is listed in part (REF ) of the val7 (with parameters \(k = 1\) , \(b = 1\) , and \(c = 5\) ).

Subsubcase 1.6.2. Assume \(|c| \notin \lbrace 3,4,6\rbrace \) .
As usual, we see from order2orbit (by the same argument as in cinv) that the set of \(c\) -edges is invariant under all automorphisms of \(BX\) . Therefore, if we let \(S_0\lbrace \pm a, \pm b, \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\rbrace \) , then the set of \(S_0\) -edges is also invariant under every automorphism of \(BX\) . Since the connected components of \(\operatorname{Cay}(\mathbb {Z}_n,S_0)\)  are isomorphic to \(\operatorname{Cay}(\mathbb {Z}_{12},\lbrace \pm 1,\pm 5,6\rbrace )\) , we see from small(REF ) that these connected components are stable. It therefore follows from StableSubgraph that \(X\)  is stable.
Subcase 1.7. Assume \(|a|\in \lbrace 3,4,6\rbrace \) .
Subsubcase 1.7.1. 
Assume \(|b|\in \lbrace 3,4,6\rbrace \) .
Note that no two of \(a\) , \(b\) , and \(c\)  can have the same order, as they cannot generate the same subgroup, since a cyclic group of order 3, 4, or 6 has only 2 generators.
If \(|c| \in \lbrace 3,4,6\rbrace \) , then \(\lbrace |a|, |b|, |c|\rbrace  = \lbrace 3,4,6\rbrace \) , so
\( X = \operatorname{Cay}(\mathbb {Z}_{12},\lbrace \pm 2,\pm 3,\pm 4,6\rbrace ). \) 
By small(REF ), this graph is stable.
So we must have \(|c|\notin \lbrace 3,4,6\rbrace \) . Then, yet again, order2orbit implies that the set of \(c\) -edges is invariant under every automorphism of \(BX\) . Therefore, if we let \(S_0 \lbrace \pm a, \pm b, \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\rbrace \) , then the set of \(S_0\) -edges is also invariant.

If \(\lbrace |a|,|b|\rbrace  = \lbrace 3,4\rbrace \) , then the connected components of \(\operatorname{Cay}(\mathbb {Z}_n,S_0)\)  are isomorphic to \(\operatorname{Cay}(\mathbb {Z}_{12},\lbrace \pm 3,\pm 4,6\rbrace )\) . By small(REF ), this graph is stable and consequently, by StableSubgraph, so is \(X\) .

If \(\lbrace |a|,|b|\rbrace  = \lbrace 3,6\rbrace \) , then the connected components of \(\operatorname{Cay}(\mathbb {Z}_n,S_0)\)  are isomorphic to \(\operatorname{Cay}(\mathbb {Z}_6,\lbrace \pm 1,\pm 2,3\rbrace )\) , which, in turn, is isomorphic to \(K_6\) . By KnStable, this is stable. Then, by StableSubgraph, so is \(X\) .

Therefore, we must have \(\lbrace |a|,|b|\rbrace  = \lbrace 4,6\rbrace \) .
In this situation, a connected component \(X_0^{\prime }\)  of \(\operatorname{Cay}(\mathbb {Z}_n, S_0)\)  is isomorphic to \(\operatorname{Cay}(\mathbb {Z}_{12},\lbrace \pm 2,\pm 3,6\rbrace )\) . This graph is nontrivially unstable, as it is listed in val5(REF ) with parameters \(k=1\)  and \(s=3\)  (and val5Nontrivial tells us that it is nontrivially unstable, not merely unstable).
So val5orbits tells us that the group \(\operatorname{Aut}BX_0^{\prime }\)  has precisely two orbits on the edges of \(BX_0^{\prime }\) . We know from the assumption of val7pf-NotInvt that there exists an automorphism of \(BX\)  that maps an \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) -edge to an \(a\) -edge. Since the set of \(S_0\) -edges is invariant, this implies there is an automorphism of \(BX_0^{\prime }\)  that maps an \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) -edge to an \(a\) -edge. (So the \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) -edges are in the same orbit as the \(a\) -edges.) It follows that the set of \(b\) -edges is invariant.
If \(|a|=4\) , then the invariant subgraph \(\operatorname{Cay}(\mathbb {Z}_n,\lbrace \pm a,\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\rbrace )\)  of \(X\)  has connected components isomorphic to \(K_4\) , which is stable by KnStable. It then follows from StableSubgraph that \(X\)  is stable.
So we must have \(|a|=6\) . Then \(|b|=4\) . Write \(n=12k\) . Then, since \(|a|\)  is not divisible by 4, we see that \(a\)  must be even.
If \(b\)  and \(c\)  are of opposite parity, then the connected components of \(\operatorname{Cay}(\mathbb {Z}_n,\lbrace \pm b,\pm c\rbrace )\)  are nonbipartite. It is not difficult to see that they are also twin-free (since \(|b| = 4\)  and the valency of the graph is so small).
\(\begin{pmatrix} \text{see} \\[-3pt] \text{note} \\[-3pt] \text{\ref {val7pf-case1-order-ab-346-aid}} \end{pmatrix}\) Since the set of \(b\) -edges is invariant under \(\operatorname{Aut}BX\)  and the set of \(c\) -edges is also invariant, we know that the set of \(\lbrace b,c\rbrace \) -edges is invariant. It therefore follows from Val4Subgraph(REF ) that \(X\)  is stable.
So \(b\)  and \(c\)  must have the same parity. However, they cannot both be even, since \(a\)  is known to be even, and \(X\)  is not connected if every element of \(S\)  is even. So \(b\)  and \(c\)  are odd. Since \(|a| = 6\) , we now see that \(X\)  is listed in part (REF ) of the val7.
Subsubcase 1.7.2. 
Assume \(|b|\notin \lbrace 3,4,6\rbrace \) .
By symmetry, we may additionally suppose that \(|c|\notin \lbrace 3,4,6\rbrace \) . Then, by applying order2orbit one last time, we see that no automorphism of \(BX\)  maps an \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) -edge to a \(b\) -edge or a \(c\) -edge. This implies that the set of \(\lbrace a, \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\rbrace \) -edges is invariant under all automorphisms of \(BX\) , and the set of \(\lbrace b,c\rbrace \) -edges is also invariant.
If \(|a| = 3\) , then the connected components of \(\operatorname{Cay}(\mathbb {Z}_n,S_0)\)  are isomorphic to \(\operatorname{Cay}(\mathbb {Z}_6,\lbrace \pm 2,3\rbrace )\) , which is stable by small(REF ). It follows by StableSubgraph that \(X\)  is also stable.
If \(|a| = 4\) , then the connected components of \(\operatorname{Cay}(\mathbb {Z}_n,S_0)\)  are isomorphic to \(\operatorname{Cay}(\mathbb {Z}_4,\lbrace 1,2,3\rbrace )\) , which is further isomorphic to \(K_4\) , which is stable by KnStable. It follows again by StableSubgraph that \(X\)  is stable.
We now only have the case \(|a| = 6\)  to consider. Let \(n = 6m\) . Note that then \(\lbrace \pm a, \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\rbrace  = \lbrace \pm m,3m\rbrace \) . We focus on
\( X_0 \operatorname{Cay}(\mathbb {Z}_n, \lbrace \pm b, \pm c\rbrace ) .\) 
Let \(X_0^{\prime }\)  be the connected component of \(X_0\)  that contains 0. As \(X\)  is assumed to be unstable and \(X_0\)  is 4-valent, we can conclude from Val4Subgraph that \(|V(X_0^{\prime })|\)  is even and that either \(X_0^{\prime }\)  is bipartite or \(X_0^{\prime }\)  is not twin-free.
Suppose, first, that \(X_0^{\prime }\)  is bipartite. This implies that \(b\)  and \(c\)  are of the same parity.

If \(b\)  and \(c\)  are even, then \(m\)  must be odd. (Otherwise, \(S\)  would contain only even integers, so \(X\)  would not be connected.) Consequently, since \(n = 6m\) , it follows that \(b\)  and \(c\)  are both of odd order, so \(X_0^{\prime }\)  contains an odd cycle. This contradicts the assumption that \(X_0^{\prime }\)  is bipartite.

If \(b\)  and \(c\)  are odd, then \(m\)  must be even. (Otherwise, every element of \(S\)  is odd, so \(X\)  is bipartite, which contradicts the fact that \(X\)  is nontrivially unstable.). Hence, we may write \(m = 2k\) , and then we see that \(X\)  is listed in part (REF ) of the val7.

We can now assume that \(X_0^{\prime }\)  is not bipartite and is not twin-free. By nottwinfree(REF ), it follows that \(X_0^{\prime }\)  is isomorphic to \(K_{4,4}\)  or \(C_\ell \wr \overline{K_2}\)  with \(\ell =|V(X_0^{\prime })| / 2\) . As \(X_0^{\prime }\)  is assumed to be nonbipartite, the first case is not possible, and in the second case, we see that \(|V(X_0^{\prime })|/2\)  is odd.
From the fact that \(X_0^{\prime }\)  is not twin-free (and the valency of \(X\)  is small — only 4
\(\begin{pmatrix} \text{see} \\[-3pt] \text{note} \\[-3pt] \text{\ref {val7pf-case1-order-b-not-346-AID}} \end{pmatrix}\)) we obtain that \(c = b + \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\)  (perhaps after replacing \(b\)  with \(-b\) ). For every \(v \in \mathbb {Z}_n \times \mathbb {Z}_2\) , we deduce that \(v + (\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}},0)\)  is the unique twin of \(v\)  in the graph \(BX_0\) . Since automorphisms must map twin vertices to twin vertices, and the set of \(\lbrace b,c\rbrace \) -edges is invariant under \(\operatorname{Aut}BX\) , we conclude that the cosets of the subgroup \(\langle (\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}},0)\rangle \)  are blocks for the action of \(\operatorname{Aut}BX\)  (see BlockDefn). Note that quotient graph of \(BX_0^{\prime }\)  with respect to the partition induced by cosets of \(\langle (\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}},0)\rangle \)  is a cycle. Since \(|V(X_0^{\prime })|/2\)  is odd, the length of this cycle is \(|V(X_0^{\prime })|\) . Therefore, in this cycle, the vertices corresponding to the cosets \(\lbrace (0,0),(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}},0)\rbrace \)  and \(\lbrace (0,1),(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}},1)\rbrace \)  are at maximum distance.
It follows that if \(\alpha \)  is an automorphism of \(BX\)  that fixes \((0,0)\) , then \(\alpha \)  must fix the coset \(\lbrace (0,1),(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}},1)\rbrace \)  set-wise. Also note that \(\alpha \)  must fix the set of neighbors of \((0,0)\)  in \(BX_1\)  with \(X_1\operatorname{Cay}(\mathbb {Z}_n, \lbrace  \pm a, \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\rbrace )\)  (because \(\lbrace a, \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\rbrace \) -edges are invariant); this set of neighbors is \(\lbrace \pm (a,1),(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}},1)\rbrace \) . Then \(\alpha \)  must fix the intersection of these two sets, which is \(\lbrace (\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}},1)\rbrace \) . The automorphism \(\alpha \)  must therefore also fix the twin of the vertex \((\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}},1)\) , which is \((0,1)\) . We now conclude from StableIffStabilizer that \(X\)  is stable.
This completes the proof of val7pf-NotInvt. For the remaining cases, we may assume that every automorphism of \(BX\)  maps \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) -edges to \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) -edges, and is therefore an automorphism of the canonical double cover of the following subgraph \(X_0\)  of \(X\) :
Notation 7.4 For the remainder of the proof, we let
\( X_0 \operatorname{Cay}(\mathbb {Z}_n,\lbrace \pm a,\pm b, \pm c\rbrace ) \) 
be the graph that is obtained from \(X\)  by removing all of the \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) -edges.

Case 2. Assume \(X_0\)  is not connected.
(We also assume that every automorphism of \(BX\)  maps \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) -edges to \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) -edges, for otherwise val7pf-NotInvt applies.)
Then \(\langle a,b,c \rangle \)  is a proper subgroup of \(\mathbb {Z}_n\) , but \(\langle a,b,c,\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\rangle \)  is the whole group \(\mathbb {Z}_n\) . It follows that \(n = 2m\) , where \(m\)  is odd, and \(|\langle a,b,c \rangle | = m\) . Let \(X_0^{\prime }\)  be the connected component of \(X_0\)  that contains 0. Note that \(X_0^{\prime }\)  is connected by definition and also that it is not bipartite (since it is vertex-transitive and of odd order).
If \(X_0^{\prime }\)  is twin-free, then it follows by OddCirculant that \(X_0^{\prime }\)  is stable. By StableSubgraph, we conclude that \(X\)  is stable, which is a contradiction.
Therefore, we know that \(X_0^{\prime }\)  is not twin-free. Then by nottwinfree(REF ), \(X_0^{\prime } \cong Y\wr \overline{K_d}\) , where \(Y\)  is a vertex-transitive, connected graph and \(d \ge 2\) . Let \(\delta \)  be the valency of \(Y\) . Since \(X_0^{\prime }\)  is 6-valent, it follows that \(6 = \delta d\)  and therefore, \(d \in \lbrace 2,3,6\rbrace \) . Because \(d \, |V(Y)| = |V(X_0^{\prime })|\)  is odd, it cannot happen that \(d\)  is even. Hence, we conclude that \(d = 3\) . It follows that \(\delta = 2\) , so \(Y\)  must be a cycle. Letting
\( k := |V(Y)| = m/3 = n/6 , \) 
we conclude that \(X_0^{\prime } \cong C_k \wr \overline{K_3}\) . Since \(X_0\)  is the disjoint union of two copies of \(X_0^{\prime }\) , we now see that
\( X_0 = \operatorname{Cay}(\mathbb {Z}_{6k}, \lbrace  \pm s, 2k \pm s, 4k \pm s \rbrace ), \) 
for some \(s \in \mathbb {Z}_n\) , such that \(|\langle s, 2k \rangle | = n/2\) . (This final condition means \(\gcd (s, 2k, 6k) = 2\) , so \(s\)  must be even; write \(s = 2t\) . Then
\( X = \operatorname{Cay}(\mathbb {Z}_{6k}, \lbrace  \pm 2t, 2k \pm 2t, 4k \pm 2t, 3k \rbrace ). \) 
This graph is listed in part (REF ) of the val7.
Case 3. Assume that \(X_0\)  is bipartite and that \(BX_0\)  is arc-transitive.
(We also assume that every automorphism of \(BX\)  maps \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) -edges to \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) -edges, and that \(X_0\)  is connected, for otherwise a previous case applies.)
Since \(X_0\)  is bipartite, it follows that \(BX_0\)  is isomorphic to a disjoint union of two copies of \(X_0\) . Since \(BX_0\)  is assumed to be arc-transitive, it follows that \(X_0\)  is a connected arc-transitive circulant graph. Consequently, it is one of the four types that are listed in ArcTrans. Type REF (REF ) is impossible because \(X_0\)  is bipartite (and has valency 6). By ReduceNonNormal, it follows that \(X_0\)  is not a normal Cayley graph, so it does not have type REF (REF ) either.
Subcase 3.1. Assume \(X_0\)  has type  REF( REF).
Then \(X_0 = Y\wr \overline{K_d}\) , where \(Y\)  is a connected arc-transitive circulant graph, and \(d \ge 2\) . Let \(\delta \)  be the valency of \(Y\) . Since \(X_0\)  has valency 6, it follows that \(\delta d=6\) , so \(d \in \lbrace 2, 3, 6\rbrace \) .
Subsubcase 3.1.1. 
Assume \(d=6\) .
Then \(X_0\cong K_{6,6}\) . It follows that \(n=12\)  and we obtain \(X=\operatorname{Cay}(\mathbb {Z}_{12},\lbrace \pm 1, \pm 3, \pm 5, 6\rbrace )\) . We have already seen this graph; it is listed in part (REF ) of the val7 with parameters \(k=t=1\) .
Subsubcase 3.1.2. Assume \(d=3\) .
Then \(Y\)  is a cycle of even length \(2m\) . We obtain that
\( X_0 = \operatorname{Cay}(\mathbb {Z}_{6m},\lbrace \pm t, 2m\pm t, 4m\pm t\rbrace ) . \) 
Then \(X = \operatorname{Cay}(\mathbb {Z}_{6m},\lbrace \pm t, 2m\pm t, 4m\pm t, 3m\rbrace )\) . Since \(X_0\)  is connected, we have \(\gcd (t, 2m) = 1\) . In particular, \(t\)  is odd. Since \(X\)  is not bipartite, this implies \(m\)  is even. Writing \(m=2k\) , we get that
\( X = \operatorname{Cay}(\mathbb {Z}_{12k},\lbrace \pm t, 4k\pm t, 8k\pm t,6k\rbrace ). \) 
So \(X\)  is listed in part (REF ) of the val7.
Subsubcase 3.1.3. Assume \(d=2\) .
Then \(Y\)  is a connected, cubic, arc-transitive, circulant graph, so CubicArcTransCirculant tells us that \(Y\)  is either \(K_4\)  or \(K_{3,3}\) . Since \(X_0\)  is bipartite, it follows that \(Y\)  is isomorphic to \(K_{3,3}\) . We obtain that \(X_0 \cong K_{6,6}\) , a case that has already been considered in val7pt-d=6.
Subcase 3.2. Assume \(X_0\)  has type  REF( REF).
Letting \(n = |V(X_0)|\) , we have \(X_0 = Y\wr \overline{K_d} - d Y\) , where \(n = md\) , \(d > 3\) , \(\gcd (d,m) = 1\)  and \(Y\)  is a connected arc-transitive circulant graph of order \(m\) . Let \(\delta \)  be the valency of \(Y\) . Since \(X_0\)  has valency 6, we must have \(\delta (d-1) = 6\) . Since \(d > 3\) , this implies that either \(d = 7\)  and \(\delta = 1\)  or \(d = 4\)  and \(\delta = 2\) .
If \(\delta = 1\) , then \(Y = K_2\)  (so \(m = 2\) ). This implies \(n = md = 2 \cdot 7 = 14\) . Then \(X_0=K_2\wr \overline{K_7}-7K_2\)  and \(X=K_2\wr \overline{K_7}\cong K_{7,7}\) . Hence, \(X\)  is bipartite and trivially unstable.
Assume, now, that \(\delta = 2\)  and \(d = 4\) . Since \(\delta = 2\) , we have \(Y = C_m\) . Then \(m\)  must be even, because \(X_0\)  is bipartite. This contradicts the fact that \(\gcd (d,m) = 1\) .
Case 4. 
Assume that none of the preceding cases apply.
This means that:

every automorphism of \(BX\)  maps \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) -edges to \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) -edges,

\(X_0\)  is connected,
and

either \(X_0\)  is not bipartite or \(BX_0\)  is not arc-transitive.

Subcase 4.1. 
Assume there exists \(s \in \lbrace a,b,c\rbrace \) , such that the set of \(s\) -edges is invariant under the action of \(\operatorname{Aut}(BX)\) , and the graph \(\operatorname{Cay}(\mathbb {Z}_n, \lbrace \pm s, \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\rbrace )\)  is not bipartite.
Let \(X_1\operatorname{Cay}(\mathbb {Z}_n,\lbrace \pm s, \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\rbrace )\) , and let \(X_1^{\prime }\)  be a connected component of \(X_1\) . Then \(X_1^{\prime }\)  is connected, cubic, and nonbipartite. The graph \(X_1^{\prime }\)  must also be twin-free, because otherwise nottwinfree(REF ) would imply that \(X_1^{\prime }\cong K_{3,3}\) , which contradicts the fact that \(X_1^{\prime }\)  is not bipartite. We therefore conclude from val3 that \(X_1^{\prime }\)  is stable. By our assumptions, the set of \(s\) -edges is invariant under the action of \(\operatorname{Aut}(BX)\) , and the set of \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) -edges is also invariant. So it follows by StableSubgraph that \(X\)  is stable, which is a contradiction.
Subcase 4.2. Assume there exists \(s \in \lbrace a,b,c\rbrace \) , such that the set of \(s\) -edges is invariant under \(\operatorname{Aut}BX\) .
Since \(X\)  is not bipartite, we know that \(S\)  contains two elements of opposite parity. Therefore, we may assume without loss of generality that \(a + \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\)  is odd. We may assume that the set of \(a\) -edges is not invariant under \(\operatorname{Aut}BX\) , for otherwise allinv applies (with \(s = a\) ). So \(s \ne a\) . Hence, we may assume, without loss of generality, that \(s = c\) , which means the set of \(c\) -edges is invariant under \(\operatorname{Aut}BX\) . This implies that the \(a\) -edges and the \(b\) -edges are in the same orbit of \(\operatorname{Aut}BX\) .
We consider the following two subgraphs of \(X\) :
\( \text{$X_1\operatorname{Cay}(\mathbb {Z}_n,\lbrace \pm c, \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\rbrace )$ and $X_2\operatorname{Cay}(\mathbb {Z}_n,\lbrace \pm a, \pm b\rbrace )$.} \) 
Denote their connected components containing 0 by \(X_1^{\prime }\)  and \(X_2^{\prime }\) , respectively.
We may assume that \(X_1^{\prime }\)  is bipartite. (Otherwise, allinv applies with \(s = c\) .) This implies that \(|c|\)  is even, so \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\in \langle c \rangle \) . More precisely, we have \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}= (|c|/2) \, c\) . Since \(X_1^{\prime }\)  is bipartite, this implies that \(|c|/2\)  is odd.
Also, since \(X\)  is unstable, it follows from Val4Subgraph that \(|V(X_2^{\prime })|\)  is even and either \(X_2^{\prime }\)  is not twin-free or \(X_2^{\prime }\)  is bipartite.
Subsubcase 4.2.1. 
Assume \(X_2^{\prime }\)  is not twin-free.
We claim that \(X_2^{\prime }\cong K_{4,4}\) . From nottwinfree(REF ), we obtain that \(X_2^{\prime }\)  is isomorphic to \(K_{4,4}\)  or \(C_{\ell } \wr \overline{K_2}\)  with \(\ell |\langle a,b\rangle | / 2\) . Let \(X_2^*\)  be the connected component of \(\operatorname{Cay}(\mathbb {Z}_n,\lbrace \pm a,\pm b,\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\rbrace )\)  containing 0. Note that \(X_2^*\)  is obtained by adding \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) -edges to \(X_2^{\prime }\) . Since \(X_2^{\prime }\cong C_\ell \wr \overline{K_2}\) , this implies \(X_2^*\cong C_{\ell }\wr K_2\) . However, since \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) -edges are also invariant, \(X_2^*\)  cannot be stable, since in this case StableSubgraph would imply that \(X\)  is stable. By CycWr, we therefore conclude that \(\ell = 4\) . Finally, note that \(C_4\wr \overline{K_2}\cong K_{4,4}\) . Hence, we may assume that \(X_2^{\prime }\cong K_{4,4}\) . This completes the proof of the claim.
It follows from the claim that \(|V(X_2^{\prime })| = |\langle a, b\rangle |= 8\) , so we may write \(n=8k\) . The claim then implies that \(\lbrace \pm a,\pm b\rbrace  = \lbrace \pm k,\pm 3k\rbrace \) . We also obtain:
\(8k = n = |\langle a,b,c,\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\rangle | = |\langle a,b,c\rangle |=\frac{|\langle a,b\rangle | \cdot |c|}{|\langle a,b \rangle \cap \langle c \rangle |} = \frac{8|c|}{|\langle a,b \rangle \cap \langle c \rangle |}\) 
This immediately implies that \(k\)  divides \(|c|\) . More precisely, since \(|c|/2\)  is odd, and the denominator of the right-most term is a divisor of \(|\langle a,b \rangle | = 8\)  (and is a multiple of \(|\langle \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\rangle | = 2\) ), the only possibility is that \(k = |c|/2\)  (so \(k\)  is odd). We conclude that:
\(X = \operatorname{Cay}(\mathbb {Z}_{8k},\lbrace \pm c, \pm k, \pm 3k, 4k\rbrace ) .\) 
Since \(|c| = 2k = 8k/4\) , we know that \(\gcd (c, 8k) = 4\) ; this means that we may write \(c = 4t\)  with \(t\)  odd. So \(X\)  is listed in part (REF ) of the val7 (with parameter \(4t = c\) ).
Subsubcase 4.2.2. Assume \(X_2^{\prime }\)  is bipartite.
Then \(a\)  and \(b\)  must be of the same parity, but as \(X\)  is nonbipartite, it follows that their parity is opposite to that of \(c\)  and \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) . Therefore, if we let \(X_2^*\)  be a connected component of \(\operatorname{Cay}(\mathbb {Z}_n, \lbrace \pm a, \pm b, \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\rbrace )\) , then \(X_2^*\)  is a connected, nonbipartite, 5-valent circulant graph.
By nottwinfree(REF ), it is also twin-free (since it is not bipartite, and therefore cannot be isomorphic to \(K_{5,5}\) ).
We conclude that \(X_2^*\)  is not trivially unstable.
Due to StableSubgraph and the fact that \(X\)  is unstable, we see that \(X_2^*\)  is not stable. Hence, it is nontrivially unstable. From our assumptions, we already know that \(a\) -edges and \(b\) -edges are in the same orbit under the action of \(\operatorname{Aut}B X_2^*\) . This implies that if the set of \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) -edges is not invariant, then all edges of \(BX_2^*\)  are in the same orbit, which would contradict val5orbits. Hence, the set of \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) -edges must be invariant, so val5nhInvt tells us that \(X_2^*\)  is isomorphic to \(\operatorname{Cay}(\mathbb {Z}_8,\lbrace  \pm 1, \pm 3,4\rbrace )\) . Therefore, \(X_2^{\prime } \cong \operatorname{Cay}(\mathbb {Z}_8,\lbrace  \pm 1, \pm 3\rbrace ) \cong K_{4,4}\)  is not twin-free, so val7pf-twins applies.
Subcase 4.3. Assume all edges of \(BX\)  besides \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) -edges are in the same orbit of \(\operatorname{Aut}BX\) .
As every automorphism of \(BX\)  is also an automorphism of \(BX_0\) , it follows that \(BX_0\)  is arc-transitive. Then by the assumption of final, \(X_0\)  must be nonbipartite.
Subsubcase 4.3.1. 
Assume \(|a|=4\) .
Since \(BX_0\)  is arc-transitive, there exist automorphisms of \(BX_0\)  mapping an \(a\) -edge to a \(b\) -edge and a \(c\) -edge. Since \(|a|=4\) , by order2orbit it follows that all generators of the subgroups \(\langle b \rangle \)  and \(\langle c \rangle \)  are in \(S\) . As all elements of \(S\)  are pairwise distinct, it is clear that either \(b\)  and \(c\)  generate distinct subgroups with exactly 2 generators each or \(b\)  and \(c\)  generate the same subgroup with exactly 4 generators.
In the first case, we get that \(|b|\ne |c|\)  and both lie in \(\lbrace 3,4,6\rbrace \) . As \(|a|=4\) , we conclude that \(\lbrace |a|, |b|, |c| \rbrace  = \lbrace 3,4,6\rbrace \) , so \(X = \operatorname{Cay}(\mathbb {Z}_{12},\lbrace \pm 2,\pm 3,\pm 4,6\rbrace )\) . By part (REF ) of small, this graph is stable.
In the second case, it follows that \(|b|=|c|\in \lbrace 5,8,10,12\rbrace \) .
Then \(X\)  is one of the following graphs:

\(|b| = |c| = 5\)  \(\Rightarrow \)  \(X = \operatorname{Cay}(\mathbb {Z}_{20},\lbrace \pm 4,\pm 5,\pm 8,10\rbrace )\) . This is stable by small(REF ).

\(|b| = |c| = 8\)  \(\Rightarrow \)  \(X = \operatorname{Cay}(\mathbb {Z}_8,\lbrace \pm 1,\pm 2,\pm 3,4\rbrace ) \cong K_8\) . This is stable by KnStable.

\(|b| = |c| = 10\)  \(\Rightarrow \)  \(X = \operatorname{Cay}(\mathbb {Z}_{20},\lbrace \pm 2,\pm 5,\pm 6,10\rbrace )\) . We find this graph in part (REF ) of the val7 (with parameters \(k=1\)  and \(t = 5\) ).

\(|b| = |c| = 12\)  \(\Rightarrow \)  \(X = \operatorname{Cay}(\mathbb {Z}_{12},\lbrace \pm 1,\pm 3,\pm 5,6\rbrace \) . We find this graph in part (REF ) of the val7 (with parameters \(k=t=1\) ).

Subsubcase 4.3.2. Assume \(2s \ne 2t\) , for all \(s,t \in S\) , such that \(s \ne t\) .
Then from 2S'-BX, it follows that any automorphism of \(BX_0\)  (and consequently of \(BX\) , as well) is an automorphism of
\( \operatorname{Cay}(\mathbb {Z}_n \times \mathbb {Z}_2, \lbrace (\pm 2a,0),(\pm 2b,0),(\pm 2c,0)\rbrace ) . \) 
Therefore, (the vertex sets of) the connected components of this graph are blocks for the action of \(\operatorname{Aut}BX_0\) . These blocks are the four cosets of the subgroup \(2\mathbb {Z}_n \times \lbrace 0\rbrace \) . As \(BX_0\)  is 6-valent and arc-transitive (and all neighbors of \((0,0)\)  are in \(\mathbb {Z}_n \times \lbrace 1\rbrace \) ), it follows that either all 6 neighbors of \((0,0)\)  in \(BX_0\)  lie in the same coset of \(2\mathbb {Z}_n\times \lbrace 0\rbrace \)  or three of its neighbors lie in \(2\mathbb {Z}_n \times \lbrace 1\rbrace \)  and the other three lie in \((1+ 2\mathbb {Z}_n) \times \lbrace 1\rbrace \) . In the first case, it follows that \(a,b,c\)  are all of the same parity, which contradicts the fact that \(X_0\)  is connected and nonbipartite. In the second case, it follows that exactly three elements of the set \(\lbrace \pm a, \pm b,\pm c\rbrace \)  are odd, which is impossible, since \(-s\)  has the same parity as \(s\) .
Subsubcase 4.3.3. 
Assume that neither of the two preceding val7pf-a=4s apply.
This means that:

\(S\)  contains no element of order 4,
and

we may assume, without loss of generality, that \(2a = 2b\) .

By 2S'-BX, every automorphism of \(BX_0\)  is also an automorphism of \(\operatorname{Cay}(\mathbb {Z}_n \times \mathbb {Z}_2,\lbrace (\pm 2c,0)\rbrace )\) . This implies that the cosets of \(\langle 2c \rangle \times \lbrace 0\rbrace \)  are blocks for the action of \(\operatorname{Aut}BX_0\) . The two \(c\) -neighbors of \((0,0)\)  are both in the coset \((c,1) + \bigl ( \langle 2c \rangle \times \lbrace 0\rbrace  \bigr )\) . Therefore, by arc-transitivity, either all neighbors of \((0,0)\)  in \(BX_0\)  are in this coset or there are three different cosets, each containing two neighbors of \((0,0)\) .
However, if all neighbors of \((0,0)\)  are in \((c,1) + \bigl ( \langle 2c \rangle \times \lbrace 0\rbrace  \bigr )\) , then \(a\)  and \(b\)  have the same parity as \(c\) . This contradicts the fact that \(X_0\)  is connected and nonbipartite.
So there are three different cosets that each contain two neighbors of \((0,0)\) . Consider the quotient graph of \(BX_0\)  with respect to the coset partition induced by \(\langle 2c \rangle \times \lbrace 0\rbrace \) . This is a cubic, connected, bipartite, arc-transitive graph \(Q\) , which is a Cayley graph on \(\mathbb {Z}_m \times \mathbb {Z}_2\) , where \(m\)  is the index of \(\langle 2c \rangle \)  in \(\mathbb {Z}_n\) . It follows from ArcTrans that there are only three cubic, connected Cayley graphs on abelian groups (up to isomorphism): \(K_4\) , \(K_{3,3}\) , and the cube \(Q_3\) .

\(K_4\)  is not bipartite.

If \(Q\cong K_{3,3}\) , then \(\langle 2c \rangle \)  is of index 3 in \(\mathbb {Z}_n\) . But this means \(\langle 2c \rangle \)  cannot be of index 2 in \(\langle c \rangle \) , so it follows that \(\langle 2c \rangle = \langle c \rangle \) , so \(c\)  is of odd order. Then \(n=3|c|\)  is also odd. By OddCirculant, \(X\)  is stable.

Therefore, \(Q\)  must be the cube (and therefore has exactly 8 vertices).
It follows that \(\langle 2c \rangle \times 0\)  is of index 8 in \(\mathbb {Z}_n \times \mathbb {Z}_2\) , so the order of \(2c\)  is \(n/4\) . This means \(n / {\gcd (n,2c)} = n/4\) , so \(\gcd (n,2c)=4\) . Therefore, \(c\)  is an even integer, and \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\)  is also even. Since \(X\)  is connected, then \(a\)  and \(b=a+\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\)  must be odd.
Note that the five non-zero neighbors of \((a,1)\)  in \(BX_0\)  are
\( (a \pm c, 0),\ (2a, 0) = (2b, 0), \ (a \pm b, 0) .\) 
There is more than one path of length 2 from \((0,0)\)  to each of these vertices. Due to arc-transitivity, this implies that the the path \((0,0), (c,1), (2c,0)\)  is not the only path of length 2 from \((0,0)\)  to \((2c,0)\) . Because the first coordinate of \((2c,0)\)  is an even integer, we conclude that \(2c\)  is a sum of two integers from \(\lbrace \pm a, \pm a+ \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}},\pm c\rbrace \)  of the same parity, besides \(c+c\) . As we have assumed there is no element of order 4 in \(S\) , the case \(2c = (-c)+(-c)\)  is not possible. So \(2c\)  must be a sum of two (odd) integers from \(\lbrace \pm a, \pm a+ \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\rbrace \) . Recalling that \(2c \ne 2s\)  for \(s \ne c\) , we see that (up to relabeling \(a,-a\)  and \(a+\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) ), we must have either
\( \text{$2c = a + (a + \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}) = 2a + \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}$ \ or \ $2c = a - (a + \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}) = \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}$.} \) 
However, the case \(2c = \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\)  is not possible, because no element of \(S\)  has order 4. Therefore, we have \(2c = 2a + \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) . This means \(2(c - a) = \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\) , so either \(c = a + (n/4)\)  or \(c = a - (n/4)\) . However, if \(c = a + (n/4)\) , then \(-c = -a - (n/4)\) ; therefore, we may assume \(c = a - (n/4)\) , by replacing \(a\) , \(b\) , and \(c\)  with their negatives, if necessary.
As \(a\)  is an odd integer, we know that \(n/|a| = \gcd (a, n)\)  is odd, so \(\langle a \rangle \)  contains every element of \(\mathbb {Z}_n\)  whose order is a power of 2. In particular, it contains \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\)  and \(\pm n/4\) . Since \(b = a + \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\)  and \(c = a + (n/4)\) , we conclude that \(\langle a \rangle = \mathbb {Z}_n\) . Then, writing \(n = 4k\) , we have:
\(X = \operatorname{Cay}(\mathbb {Z}_{4k},\lbrace \pm a, \pm (a + 2k), \pm (a - k), 2k\rbrace ) . \) 
If \(a \equiv k \ (\mathrm {mod}~4)\) , then this is listed in part (REF ) of the val7 (with parameter \(t = a\) ).
To complete the proof, we will show that if \(a \lnot \equiv k \ (\mathrm {mod}~4)\) , then the subgraph \(X_0\)  is stable. This then implies by StableSubgraph that \(X\)  is stable as well, which is a contradiction.
Suppose, for a contradiction, that \(X_0\)  is unstable (and \(a \equiv -k \ (\mathrm {mod}~4)\) ). To work around a conflict of notation, let us change our notation for \(X_0\) , by writing \(\alpha \)  and \(\kappa \)  instead of \(a\)  and \(k\) :
\(X_0 = \operatorname{Cay}(\mathbb {Z}_{4 \kappa },\lbrace \pm \alpha , \pm (\alpha + 2\kappa ), \pm (\alpha - \kappa )\rbrace ) .\) 
Recall that \(\kappa \)  is odd, and \(\alpha \equiv -\kappa \ (\mathrm {mod}~4)\) .
Since \(X_0\)  is connected, nonbipartite, and twin-free, 
\(\begin{pmatrix} \text{see} \\[-3pt] \text{note} \\[-3pt] \text{\ref {val7pf-NO-order4-NO-2a=2b-AID}} \end{pmatrix}\)it is nontrivially unstable. So it must appear in the list of nontrivially unstable 6-valent graphs in explicit6. However:

Since \(\kappa \)  is odd, we know that \(|V(X_0)|=4\kappa \)  is not divisible by 8. So \(X_0\)  cannot appear under (REF ), (REF ), or (REF ) in explicit6.

Since the connection set of \(X_0\)  has 4 odd elements (\(\pm \alpha \)  and \(\pm (\alpha + 2\kappa )\) ), we can also rule out the family REF (REF ).

If \(X_0\)  is a member of the family REF (REF ), then, since \(\alpha - k\)  and its negative are the only even elements of the connection set for \(X_0\)  (and the four elements \(\pm (a + k)\)  and \(\pm (a - k)\)  all have the same parity), the element \(a\)  of REF (REF ) must be \(\alpha - \kappa \)  (perhaps after replacing \(a\)  with \(-a\) ). Since \(\alpha \equiv -\kappa \ (\mathrm {mod}~4)\) , this implies
\( a = \alpha - \kappa \equiv 2\alpha \equiv 2 \ (\mathrm {mod}~4) , \) 
which contradicts the requirement of REF (REF ) that \(a \equiv 0 \ (\mathrm {mod}~4)\) .

Assume \(X_0\)  is a member of the family REF (REF ). Then we can find \(m \in \mathbb {Z}\)  with \(\gcd (m,4\kappa )=1\)  and \(m^2\equiv 1\ (\mathrm {mod}~4\kappa )\)  satisfying the identity listed in REF (REF ). Using the notation from explicit6, we observe the following cases:

Assume \(a=\alpha \) . We then obtain that:
\((m-1)\alpha \equiv (m+1)(\alpha +2\kappa )\ (\mathrm {mod}~4\kappa ),\) 
so \(2\mid (\alpha +\kappa (m+1))\) . This is clearly a contradiction, since the right-most expression is odd, since \(\alpha \)  and \(m\)  are odd.

Assume \(a=\alpha +2\kappa \) . We then obtain a contradiction of the same type:
\((m-1)(\alpha +2\kappa ) \equiv (m+1)\alpha \ (\mathrm {mod}~4\kappa ),\) 
so \(2\mid (\kappa (m-1)-\alpha )\) .

Assume \(a=\alpha -\kappa \) . It then follows that:
\((m-1)(\alpha -\kappa )\equiv (m+1)\alpha \ (\mathrm {mod}~4\kappa ),\) 
so \(\kappa \mid \alpha \) .
This is a contradiction, since we have already established that \(\alpha \)  is a generator of the group \(\mathbb {Z}_{4\kappa }\) .


Finally, suppose \(X_0\)  is a member of the family REF (REF ). Since \(\alpha - \kappa \)  and its negative are the only even elements of the connection set of \(X_0\)  (and the four elements \(\pm b\)  and \(\pm m b + 2k\)  all have the same parity), the element \(a\)  of REF (REF ) must be \(\alpha - \kappa \)  (or its negative). Then \(a\)  and \(m - 1\)  are even (and \(k = n/4 = \kappa \)  is odd), so we have
\( (m - 1) a \equiv 0 \lnot \equiv 2 \equiv 2k \ (\mathrm {mod}~4) . \) 
This contradicts the requirement that \((m - 1)a \equiv 2k \ (\mathrm {mod}~n)\) .

Therefore \(X_0\)  does not appear on any of the lists in explicit6. This contradiction completes this final case of the proof of the val7.
toc


appendix

Notes to aid the referee
 1.1 
Let \(G^*\)  be the regular representation of \(G\) . Since \(G^*\)  is contained in \(\operatorname{Aut}X\) , it is clear that \(\mathcal {B}\)  is also a block for the action of \(G^*\) . Hence, [3]} tells us that \(\mathcal {B}\)  is an orbit of some subgroup \(H^*\)  of \(G^*\) . If we let \(H\)  be the corresponding subgroup of \(G\) , then the \(H^*\)  orbit of an element \(b\)  of \(G\)  is precisely \(b + H\) , so it is a coset of \(H\) .
We see from [3]} that every coset of \(H\)  is a block. Furthermore, since these cosets form a partition of \(G\) , we see that they are the entire “system of blocks” containing \(\mathcal {B}\) , so [3]} tells us that \(\operatorname{Aut}X\)  acts on this set of blocks.


 1.2 
Suppose \(u\)  and \(v\)  are two distinct vertices in the same coset of \(\langle (k, 0) \rangle \) . Since \(|k| = 4\) , we may assume that \(v\)  is either \(u + (k, 0)\)  or \(u + (2k, 0)\)  (after interchanging \(u\)  and \(v\)  if \(v = u + (3k, 0)\) ).
If \(v = u + (k, 0)\) , then both vertices are adjacent to
\(u + (c + k, 0) &= v + (c, 0) \\u + (c, 0) &= v + (c - k, 0) \\u - (c, 0) &= v - (c + k, 0) \\u - (c - k, 0) &= v - (c, 0)\) 

If \(v = u + (2k, 0)\) , then both vertices are adjacent to
\(u + (c + k, 0) &= v + (c - k, 0) \\u + (c - k, 0) &= v + (c + k, 0) \\u - (c + k, 0) &= v - (c - k, 0) \\u - (c - k, 0) &= v - (c + k, 0)\) 


 1.3 
Assume \(u\)  and \(v\)  are vertices of \(BX\)  that are in different cosets of \(\langle (k, 0) \rangle \) , and let \(w\)  be a common neighbor. Since \(S \subseteq (c + \langle k \rangle ) \cup (-c + \langle k \rangle )\) , we may assume \(w \in u + \tilde{c} + \langle (k, 0) \rangle \)  and \(w \in v - \tilde{c} + \langle (k, 0) \rangle \) , by interchanging \(u\)  and \(v\)  if necessary.
Since \(c \notin \langle k \rangle \)  and \(|\mathbb {Z}_{4k}/\langle k \rangle | = k = n/4\)  is odd, we know that \(4c \notin \langle k \rangle \) . Therefore, taking congruences modulo \(\langle (k, 0) \rangle \) , we have
\(u - \tilde{c}&= u + \tilde{c} - (2c, 0)\\& \equiv w - (2c, 0)\\&\equiv v - \tilde{c} - (2c, 0)\\&= v + \tilde{c} - (4c, 0)\\&\lnot \equiv v + \tilde{c}&& \begin{pmatrix} \text{$4c \notin \langle k \rangle $, so} \\ (4c, 0) \lnot \equiv 0 \ (\mathrm {mod}~) \end{pmatrix}. \) 

This implies that no vertex in \(u - c + \langle (k, 0) \rangle \)  is adjacent to \(v\) , so all of the common neighbors are in \(u + c + \langle (k, 0) \rangle \) . Since the only neighbors of \(u\)  that are in this coset are \(u + c\) , \(u + (c + k)\) , and \(u + (c - k)\) , this obviously implies that \(u\)  and \(v\)  have no more than 3 common neighbors.


 1.4 
Details missing in the proof of val7pf-case1-order-ab-346
We are assuming that \(b\)  and \(c\)  are of opposite parity, so the graph \(\Gamma \operatorname{Cay}(\mathbb {Z}_n,\lbrace \pm b,\pm c\rbrace )\)  is nonbiparite. Assume that it is not twin-free. Then by nottwinfree(REF ) and the fact that \(\Gamma \)  is nonbipartite, it follows that
\(\Gamma \cong C_\ell \wr \overline{K_2}\)  with \(\ell = |V(\Gamma )|/2\) . Furthermore, the unique twin of 0 is \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\)  i.e. \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}+ \lbrace \pm b,\pm c\rbrace  = \lbrace \pm b,\pm c\rbrace \) . Since \(|b|=4\) , it follows that \(b+\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}= -b\)  and \(-b+\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}= b\) . Hence, \(c + \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}= -c\)  and \(-c + \mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}= c\) , which implies \(|c|\)  is a divisor of 4, a contradiction.


 1.5 
Details missing in the proof of val7pf-case1-order-b-not-346.
By nottwinfree(REF ), 0 and \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\)  are twins. It follows that \(\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}+ \lbrace \pm b,\pm c\rbrace  = \lbrace \pm b,\pm c\rbrace \) . Clearly, \(b+\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\ne b\)  and since \(|b|\notin \lbrace 2,4\rbrace \) , it follows that \(b+\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\ne -b\) . Therefore, \(b+\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}\in \lbrace \pm c\rbrace \) , so up to relabelling \(c\)  and \(-c\) , it holds that \(b+\mathord {\mathchoice{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 6pt height 2.75pt depth -1.95pt\hss }n}{\hbox{t}o 0pt{\vrule width 5pt height 2pt depth -1.6pt\hss }n}{\hbox{t}o 0pt{\vrule width 4.3pt height 1.6pt depth -1.1pt\hss }n}}= c\) .


 1.6 
Proof that the graph \(X_0 = \operatorname{Cay}(\mathbb {Z}_{4 \kappa },\lbrace \pm \alpha , \pm (\alpha + 2\kappa ), \pm (\alpha - \kappa )\rbrace )\)  from val7pf-NO-order4-NO-2a=2b is connected, nonbipartite and twin-free.
We recall that it has already been established that \(\langle \alpha \rangle = \mathbb {Z}_n\)  and that \(\kappa \)  and \(\alpha \)  are both odd. Connectedness and nonbipartiteness follow immediately. Assume for contradiction that \(X_0\)  is not twin-free. Then there exists a non-zero \(h\)  in \(\mathbb {Z}_{4\kappa }\)  such that:
\(h + \lbrace \pm \alpha , \pm (\alpha + 2\kappa ), \pm (\alpha - \kappa )\rbrace  = \lbrace \pm \alpha , \pm (\alpha + 2\kappa ), \pm (\alpha - \kappa )\rbrace .\) 
Since the connection set of \(X_0\)  is of cardinality 6, it cannot contain equal number of even and odd elements, so it follows that \(h+ S_o = S_o\)  and \(h+S_e=S_e\) . In particular, since \(\pm \alpha \)  and \(\pm (\alpha +2\kappa )\)  are of the same parity (both are odd), it follows that \(h + (\alpha -\kappa ) = -(\alpha -\kappa )\)  and \(h - (\alpha -\kappa )=\alpha -\kappa \) . We obtain that \(2h=0\) , so \(h=2\kappa \) . But then \(2\kappa + (\alpha -\kappa )=-(\alpha -\kappa )\)  implies that \(2\alpha =0\)  and \(\alpha \in \lbrace 0,2\kappa \rbrace \) . This is a contradiction with \(\alpha \)  being odd.


