# Finite groups with geodetic Cayley graphs

Murray Elder  School of Mathematical and Physical Sciences, University of
Technology Sydney, Broadway NSW 2007, Australia<EMAIL_ADDRESS>,
Adam Piggott  Mathematical Sciences Institute, Australian National University,
Canberra ACT 2601, Australia<EMAIL_ADDRESS>,  Florian Stober
Institut für Formale Methoden der Informatik, Universität Stuttgart,
Universitätsstraße 38, 70569 Stuttgart, Germany<EMAIL_ADDRESS>stuttgart.de ,  Alexander Thumm  Institut für Formale Methoden der Informatik,
Universität Stuttgart, Universitätsstraße 38, 70569 Stuttgart, Germany
<EMAIL_ADDRESS>and  Armin Weiß  Institut für Formale
Methoden der Informatik, Universität Stuttgart, Universitätsstraße 38, 70569
Stuttgart, Germany<EMAIL_ADDRESS>
###### Abstract.

A connected undirected graph is called _geodetic_ if for every pair of
vertices there is a unique shortest path connecting them. It has been
conjectured that for finite groups, the only geodetic Cayley graphs which
occur are odd cycles and complete graphs. In this article we present a series
of theoretical results which contribute to a computer search verifying this
conjecture for all groups of size up to 1024. The conjecture is also verified
theoretically for several infinite families of groups including dihedral and
some families of nilpotent groups. Two key results which enable the computer
search to reach as far as it does are: if the center of a group has even
order, then the conjecture holds (this eliminates all $2$-groups from our
computer search); if a Cayley graph is geodetic then there are bounds relating
the size of the group, generating set and center (which cuts down the number
of generating sets which must be searched significantly).

###### Key words and phrases:

geodetic graph, geodetic group, finite group, Cayley graph, group center

###### 2020 Mathematics Subject Classification:

05C12, 05C25, 20F05

##  1\. Introduction

Cayley graphs of groups form an important subclass of the vertex-transitive
and regular graphs. The undirected Cayley graph of a group $G$ with respect to
a generating set $\Sigma$ is the connected graph on the set of vertices $V=G$
where $\\{g,h\\}\in E$ if and only if there is a generator $a\in\Sigma$ such
that $ga=h$. Besides being an important tool in combinatorial group theory,
there are also interesting graph-theoretic questions about Cayley graphs. One
example which has been much studied is the longstanding conjecture that every
finite undirected Cayley graph has a Hamiltonian cycle (see for example [25]).

A connected undirected graph $\Gamma=(V,E)$ is called _geodetic_ if for any
pair $u,v\in V$, the shortest path from $u$ to $v$ is unique. Research on
geodetic graphs began in 1962, when Ore posed the problem of classifying all
such graphs [24]. This goal has been achieved so far for planar geodetic
graphs, and geodetic graphs of diameter two [33, 32]; yet, after decades of
active research, a full classification of finite geodetic graphs has not been
attained (for some recent developments, see for example [14, 17, 34]).

In 1997, Shapiro [31] asked whether each finitely generated group that admits
a geodetic Cayley graph with respect to some finite generating set is _plain_
, that is, isomorphic to the free product of finitely many finite groups and
finitely many copies of $\mathbb{Z}$. It is well-known and not hard to see
that the converse holds: each plain group admits a geodetic Cayley graph (with
respect to the generating set consisting of each non-trivial element of each
finite factor, and a cyclic generator for each $\mathbb{Z}$ factor). Recently,
significant progress has been made on this question [11] and variants of it
[10, 12, 13] (see also the paragraph below on related work).

For a finite group, one may consider a generating set consisting of every non-
trivial element. Then the corresponding Cayley graph is the complete graph,
which is geodetic. For cyclic groups of odd order, there is a second
possibility: taking an arbitrary single generator, the Cayley graph is an odd
cycle, which is also geodetic. The question we study here is whether there is
any other possibility. In a 2017 PhD thesis [15], Federici conjectured there
is none.

######  Conjecture A ([15, Conjecture 6]).

Every finite geodetic Cayley graph is either a cycle of odd length or a
complete graph.

In this paper we report on a systematic computer experiment which confirms the
conjecture for a significant number of groups.

######  Theorem B.

All groups up to size 1024 satisfy A.

In fact, we can go even further than that by showing that all groups of even
order up to 2014, all simple groups of order below 5000, and the symmetric
group $S_{7}$ satisfy A. Given that there are approximately $49.5$ billion
groups of order at most $1024$, and each has exponentially many different
generating sets, a naive computer search could not possibly achieve the result
in B. Instead, our computer search relies on a series of theoretical results
concerning finite groups and when they can admit geodetic Cayley graphs. Some
of these results confirm the conjecture for infinite families of groups, as
summarized by the following.

######  Theorem C.

A finite group $G$ satisfies A if any one of the following conditions holds.

  1. (1)

The center $Z(G)$ of $G$ has even order (Theorem 3.14).

  2. (2)

The group $G$ contains an abelian subgroup of index two (Theorem 5.4).

  3. (3)

The group $G$ is nilpotent and its order does not have certain small divisors
depending on the nilpotency class of $G$ (see Theorem 5.9 for the precise
statement).

  4. (4)

The group $G$ has large commutativity degree (Theorem 5.17).

This cuts down the number of groups which need to be considered enormously,
from $49.5$ billion to $3197$. In fact, just excluding abelian groups and
groups with even-order center leaves $4734$ groups of order at most $1024$. We
note that A was shown to be satisfied by all abelian groups by Georgakopoulos
as reported in [15, Proposition 10].

A second key theoretical result is the following, which provides an upper
bound on the number of generating sets that the search must consider for each
group.

######  Theorem D.

Let $G$ be a finite group with generating set $\Sigma$ such that the Cayley
graph $\mathrm{Cay}(G,\Sigma)$ is geodetic and neither complete nor a cycle.
Then $\left|\mathinner{\Sigma}\right|<0.845\sqrt{|G|}$.

Article organization. Theorems C and D are proved via a series of results
presented in Sections 3 to 5. In Section 6 we give details of the
implementation of our computer program. We use GAP [18] and its small group
(SmallGrp) library [2] to enumerate the groups and check which of them are
already covered by Theorem C. Then we apply an exhaustive search to check
whether there is any geodetic generating set for any of the remaining groups.
This exhaustive search crucially relies on several pruning methods based on
variants of D and other theoretical results developed in Sections 3 and 4. The
code is available at

https://osf.io/9ay6s/?view_only=37e18301e4e74e12bfe4e07b90b924c0.

Related work. As noted above, the first mention of Conjecture A that we are
aware of is in the 2017 thesis of Federici [15], where the conjecture is
proved for abelian groups and where it is shown that the Cayley graph of a
semidirect product $C_{m}\rtimes C_{n}$ with $C_{n}$ acting faithfully on
$C_{m}$ with respect to the “standard” generating set is not geodetic. Notice
that for both $m$ and $n$ sufficiently large, this class of groups turns out
to be one of the most difficult cases for our computer search (see Section
6.5). Besides this result, Federici proves some helpful lemmas for general
geodetic Cayley graphs and runs computer experiments (unfortunately
undocumented) which do not find any geodetic Cayley graphs except the obvious
ones.

In 2022 Che [5] programmed an exhaustive computer search as part of an
undergraduate project supervised by Alexey Talambutsa establishing A for
subgroups of the symmetric group $S_{4}$. Moreover, for

  * •

all subgroups of $S_{6}$ with generating sets of size five,

  * •

all subgroups of $S_{7}$ with generating sets of size four,

  * •

all subgroups of $S_{9}$ with generating sets of size three,

  * •

all subgroups of $S_{10}$ with generating sets of size two,

Che showed that none of the corresponding Cayley graphs except complete ones
and odd cycles are geodetic. For the source code, see
https://gitlab.com/andr0901/kayley-geodesics. Be aware that restricting the
number of generators to five or less is a strong restriction. (Note that by
contrast, B verifies all generating sets for $S_{6}$, and Theorem 6.6 below
verifies all generating sets for $S_{7}$. The groups $S_{9}$ and $S_{10}$ are
beyond our scope.)

For the case of infinite groups, Gardam, Spriano, Townsend and the first two
authors have proved that if a quasi-transitive locally-finite graph is
geodetic, then it is quasi-isometric to a tree [11]. This implies that the
only groups that can have geodetic Cayley graphs are the virtually free
groups. Moreover, they show that the class of groups admitting geodetic Cayley
graphs are a strict subclass of virtually free ([11, Theorem B]), which almost
resolves Shapiro’s question. To make further progress it will be useful to
understand finite geodetic Cayley graphs as, if A is false and some
interesting (family of) counterexamples can be obtained, these might be used
to construct non-trivial infinite geodetic Cayley graphs for virtually free
groups that are not plain groups.

A crucial role for the study of infinite geodetic Cayley graphs is played by
so-called _inverse-closed finite confluent length-reducing rewriting systems_
(icfclrrs). Indeed, it is an easy exercise to show that a group presented by
an icfclrrs has a geodetic Cayley graph. For finite groups the converse is
also straightforward; hence, in this case the two properties are equivalent.
Recently, as a corollary of the above-mentioned result, this equivalence has
been shown to be true for all finitely generated groups [11, Theorem C] –
yielding a connection between a rather geometric property (being geodetic) and
another coming from formal languages (being presented by an icfclrrs).
Earlier, Eisenberg and the second author [10] solved a variant of a conjecture
of Madlener and Otto [22, p. 143] (known as Gilman’s conjecture) by showing
that all groups presented by a monadic (all right-hand sides are of length
one) finite confluent length-reducing rewriting system are plain. Furthermore,
[12] shows that groups presented by icfclrrs with left-hand sides of length at
most three are also plain. In [26, Corollary 3.13] it is shown that the finite
cyclic groups of order at least three are the only finite groups admitting
more than one “normalized” finite confluent monadic rewriting system, and
those groups admit exactly two such rewriting systems.

In [13] Townsend and the first two authors generalize the concept of a
geodetic graph to graphs which have at most $k$ different geodesics between
any pair of vertices for some constant $k$, which they call _$k$ -geodetic_,
and study properties of groups which admit $k$-geodetic Cayley graphs. While
the main focus in [13] is on infinite groups, [13, Example 1.1] gives examples
of Cayley graphs of finite groups that are $k$-geodetic but not
$(k-1)$-geodetic or complete for $k\geq 2$. The easiest such examples are
cyclic groups of even order with a non-complete 2-geodetic Cayley graph as
well as a complete bipartite Cayley graph.

A graph is called _strongly geodetic_ if for every pair of vertices there is
at most _one_ non-backtracking path connecting them that has length at most
the diameter of the graph [3]. Clearly, all strongly geodetic graphs are
geodetic. By [3, Theorem 1] the class of strongly geodetic regular graphs
coincides with the class of so-called _Moore graphs_ , which also have been
thoroughly studied in graph theory (for a definition see [20] or the survey
paper [23]). Interestingly, for diameter two the Moore graphs coincide exactly
with the regular geodetic graphs [32]. Moreover, by [1, 7] the Moore graphs
are completely classified: cycles of odd length, complete graphs, the Petersen
graph, Hoffman-Singleton graph, and potentially hypothesized graphs (not known
to exist) with 3250 vertices and degree 57. Of these, only the cycles and the
complete graphs are Cayley graphs [4, 23] (we provide an alternative proof of
this fact in Proposition 3.17 below). Hence, A is true if we replace
“geodetic” with “strongly geodetic”. On the other hand, Cayley graphs provide
examples that are “close” to being Moore graphs [9].

##  2\. Preliminaries

###  2.1. Groups and words

Throughout this article, we only consider finite groups. We write these
multiplicatively, mostly omitting the operator altogether, and denote their
neutral element by $1$. As usual, we write $[g,h]=g^{-1}h^{-1}gh$ for the
_commutator_ of two elements $g,h$ of a group $G$. The _center_ of $G$ is the
subgroup $Z(G)=\\{g\in G\mid[g,h]=1\text{ for all }h\in G\\}$. Two elements
$g,g^{\prime}\in G$ are _conjugate_ if $g^{\prime}=h^{-1}gh$ $(\eqqcolon
g^{h})$ for some $h\in G$. Given $g\in G$ and $H\subseteq G$, we write
$g^{H}=\\{g^{h}\mid h\in H\\}$.

We denote by $\operatorname{ord}(g)$ the _order_ of $g\in G$, i.e., the
smallest positive integer $n$ with $g^{n}=1$. The _order_ (number of elements)
of the group $G$ is denoted by $\left|\mathinner{G}\right|$, and the
_exponent_ of $G$ by $\exp(G)$, i.e., the smallest positive integer $n$ such
that $g^{n}=1$ for all $g\in G$. Our notation is similar to [29].

For a subset $X\subseteq G$, we write $\left<\mathinner{X}\right>$ for the
subgroup generated by $X$. It consists of those group elements that can be
written as words over the alphabet $\Sigma=X\cup X^{-1}$. We denote the set of
all such words by $\Sigma^{\ast}$. Given words $v,w\in\Sigma^{\ast}$, we write
$v=w$ with the meaning that $v$ and $w$ evaluate to the same group element in
$G$, whereas $v\equiv w$ denotes equality of words.

A subset $\Sigma\subseteq G$ with $\left<\mathinner{\Sigma}\right>=G$ is
called a _generating set_ of $G$. Throughout, we assume that all generating
sets satisfy $1\not\in\Sigma$ and are _symmetric_ , i.e., $a\in\Sigma$ implies
$a^{-1}\in\Sigma$. We sometimes represent the inverse $a^{-1}$ of a generator
$a\in\Sigma$ by $\overline{a}$ to emphasize that it is a single letter.

The length of a word $w=a_{1}\cdots a_{n}\in\Sigma^{*}$ (with
$a_{i}\in\Sigma$) is denoted by $\left|\mathinner{w}\right|=n$. We denote the
set of words over $\Sigma$ of length $n$ by $\Sigma^{n}$. A word
$w\in\Sigma^{*}$ is called a _geodesic_ for (or representing) a group element
$g\in G$ if $w=g$ and $w$ is shortest among all words with that property. The
geodesic length of $g\in G$ is defined as the length of a geodesic word
representing $g$. If $g$ admits a unique geodesic, we denote its geodesic by
$\mathrm{geod}(g)$.

We use the following notation for specific groups. $C_{n}$ is the cyclic group
of order $n$, $D_{2n}$ the dihedral group of order $2n$, and $S_{n}$ (resp.
$A_{n}$) the symmetric (resp. alternating) group on $n$ elements. A direct
product is denoted by $\times$ and a _semidirect product_ by $\rtimes$, where
$G=N\rtimes H$ means that $N$ is a normal subgroup of $G$ and $H$ a subgroup
of $G$ such that $G=NH$ and $N\cap H=\\{1\\}$. Notice that $G/N=H$ in this
case. Be aware that writing $G=N\rtimes H$ does not completely define $G$ –
instead we need to also specify a homomorphism from $H$ to the automorphism
group of $N$ describing the action $(h,n)\mapsto hnh^{-1}$ of $H$ on $N$ (in
other words $H$ acts on $N$ via automorphisms).

###  2.2. Graphs and Cayley graphs

We consider only _undirected finite simple graphs_ $\Gamma=(V,E)$ where
$E\subseteq\binom{V}{2}$. The _Cayley graph_
$\operatorname{Cay}(G,\Sigma)=(V,E)$ of a group $G$ (with respect to a
generating set $\Sigma\subseteq G$) is defined by $V=G$ and
$E=\\{\\{g,ga\\}\mid g\in G,a\in\Sigma\\}$. In other literature sometimes the
_directed_ Cayley graph is considered; however, throughout this paper we only
consider the undirected graph defined as above. Moreover, we always assume
that $1\not\in\Sigma$; hence, $\operatorname{Cay}(G,\Sigma)$ contains no
loops.

The Cayley graph is connected because $\Sigma$ generates $G$. Note also that
$G$ acts on $\operatorname{Cay}(G,\Sigma)$ by left translations, i.e.,
$g.v=gv$ and $g.\\{h,ha\\}=\\{gh,gha\\}$. In particular,
$\operatorname{Cay}(G,\Sigma)$ is vertex-transitive.

Given a graph $\Gamma=(V,E)$, a _path_ of length $n$ from $v_{0}\in V$ to
$v_{n}\in V$ in $\Gamma$ is a sequence $v_{0},\ldots,v_{n}$ with
$\\{v_{i-1},v_{i}\\}\in E$ for all $1\leq i\leq n$. A _cycle_ is a path with
$v_{0}=v_{n}$. The _distance_ $d(u,v)$ between vertices $u$ and $v$ is defined
as the length, i.e., the number of edges, of a shortest path (_geodesic_)
connecting $u$ and $v$. The _diameter_ of $\Gamma$ is $\max\\{d(u,v)\mid
u,v\in V\\}$. Moreover, given $v\in V$ and $H\subseteq V$, we define
$d(v,H)=\min\\{d(v,h)\mid h\in H\\}$ to be the distance of $v$ to $H$,
$\mathcal{N}(v)=\\{u\mid\\{u,v\\}\in E\\}$ to be the neighborhood of $v$, and
$\mathcal{N}(H)=\\{u\mid\exists v\in H:\\{u,v\\}\in E\\}$ to be the
neighborhood of $H\subseteq V$.

A subset $H\subseteq V$ is called a _clique_ (resp. _independent set_) if
$\\{u,v\\}\in E$ (resp. $\\{u,v\\}\not\in E$) for all $u,v\in H$ with $u\neq
v$. A graph $\Gamma=(V,E)$ is called _complete_ if $V$ is a clique; it is
called a _cycle_ if $V=\\{v_{1},\dots,v_{n}\\}$ where
$\left|\mathinner{V}\right|=n$ such that $E=\\{\\{v_{i},v_{i+1}\\}\mid
i\in\\{1,\dots,n\\}\\}$ (calculating modulo $n$).

###  2.3. Geodetic graphs

######  Definition 2.1.

A graph is _geodetic_ if each pair of vertices is connected by a unique
geodesic.

The following equivalent definition using even cycles is due to Stemple.

######  Lemma 2.2 ([33, Theorem 2]).

A connected graph $\Gamma$ is geodetic if and only if $\Gamma$ contains no
even cycle $x_{0},\dots,x_{2n}=x_{0}$ such that $d(x_{i},x_{i+n})=n$ for all
$0\leq i\leq n$.

An important special case are cycles of length four or six, the conditions
under which those can exist are described in [32]. Of these we recall some
basic facts on 4-cycles.

######  Lemma 2.3 ([32, Theorem 3.3]).

Suppose that $\Gamma=(V,E)$ is a geodetic graph. Then the vertices of every
cycle $v_{0},v_{1},v_{2},v_{3},v_{0}$ of length four in $\Gamma$ induce a
complete subgraph.

######  Remark 2.4.

Throughout, we use Lemma 2.3 in the following way without giving further
reference. Suppose that $\Sigma$ be a generating set of a group $G$ such that
the corresponding Cayley graph is geodetic. Then, given $a,b,c,d\in\Sigma$
with $a\neq c$ such that $ab=cd$, we conclude that also
$ab,cd,c^{-1}a,bd^{-1}\in\Sigma$.

######  Lemma 2.5 ([32, Theorem 3.5]).

Let $\Gamma=(V,E)$ be a geodetic graph and $C\subseteq V$ be a clique in
$\Gamma$. If $v\in V$ is adjacent to at least two distinct vertices in $C$,
then $C\cup\\{v\\}$ is a clique.

######  Lemma 2.6.

Let $\Gamma=(V,E)$ be a geodetic graph. Then the neighbors of any vertex $v\in
V$ can be partitioned into a set of disjoint cliques.

###### Proof.

Assume for contradiction that $x,y,z\in\mathcal{N}(v)$ with $\\{x,y\\}\in E$,
$\\{y,z\\}\in E$ but $\\{x,z\\}\notin E$. Then there are two geodesics from
$x$ to $z$ (one via $v$ and one via $y$), contradicting $\Gamma$ being
geodetic. ∎

After fixing a starting point in a Cayley graph $\operatorname{Cay}(G,\Sigma)$
(for instance the vertex corresponding to the neutral element $1$) paths
starting at $1$ are in bijection with words $w\in\Sigma^{*}$ (recall that we
always assume the generating set $\Sigma\subseteq G$ to be symmetric). This
allows us to denote paths by words in $\Sigma^{*}$ rather than vertex
sequences and leads to the following observation.

######  Observation 2.7.

The Cayley graph $\operatorname{Cay}(G,\Sigma)$ of a group $G$ is geodetic if
and only if each group element $g\in G$ is represented by a unique geodesic
$w\in\Sigma^{\ast}$.

##  3\. Structure of geodetic Cayley graphs

###  3.1. Complete subgroups

######  Definition 3.1.

Let $G$ be a group with generating set $\Sigma$. We call $H\leq G$ a _complete
subgroup_ (with respect to $\Sigma$) if
$H\mathbin{\mathchoice{\raisebox{0.3pt}{\hbox{ \leavevmode\hbox to4.1pt{\vbox
to5.8pt{\pgfpicture\makeatletter\hbox{\hskip 0.3pt\lower-0.3pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{3.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{5.2pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to4.1pt{\vbox to5.8pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{3.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{5.2pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to2.65pt{\vbox to4.25pt{\pgfpicture\makeatletter\hbox{\hskip
0.22499pt\lower-0.22499pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{{}{}}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.45pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{2.2pt}{0.0pt}\pgfsys@lineto{0.0pt}{3.8pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to1.9pt{\vbox to3.2pt{\pgfpicture\makeatletter\hbox{\hskip
0.2pt\lower-0.2pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{{}{}}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{1.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.8pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}}1\subseteq\Sigma$
or, equivalently, if $H\subseteq G$ induces a complete subgraph of
$\operatorname{Cay}(G,\Sigma)$.

######  Lemma 3.2.

Let $\Gamma=\mathrm{Cay}(G,\Sigma)$ be geodetic and let $C\subseteq G$ be a
maximal clique of $\Gamma$ with $1\in C$.

  1. (1)

Then $g^{-1}C=C$ or $g^{-1}C\cap C=\\{1\\}$ for each $g\in C$.

  2. (2)

If $C$ is the only maximal clique of its size, then $C$ is closed under
inversion.

###### Proof.

Notice that all left translations are isomorphisms of $\Gamma$. Since $1\in
g^{-1}C\cap C$ for each $g\in C$, the first statement follows from Lemma 2.6.
For the second statement, note that $g^{-1}C=C$ holds for each $g\in C$ by
uniqueness of $C$. As such, $g^{-1}\in g^{-1}C=C$. ∎

Note that, in the second case of the previous lemma, where $C$ is the only
maximal clique of its size, $C$ is not only closed under inversion, it is also
a subgroup. We prove a more general statement.

######  Lemma 3.3.

Let $\Gamma=\mathrm{Cay}(G,\Sigma)$ be geodetic. If $X\subseteq G$ is a clique
of $\Gamma$ with $1\in X$ and such that $X$ is closed under inversion, then
$\langle X\rangle$ is a complete subgroup.

###### Proof.

Let $C\subseteq G$ be a maximal clique containing $X$. Then $g^{2}\in C$ for
each $g\in X$. If $g^{2}=1$ then this is obvious. Otherwise
$\\{1,g,g^{2}\\}\subseteq gX$ is a clique of $\Gamma$ and thus $g^{2}\in C$ by
maximality of $C$.

In particular, for each $g\in X$, we have $\\{1,g\\}\subseteq g^{-1}C=C$ and
thus $g^{-1}C=C$ by Lemma 3.2. As $X$ is closed under inversion, this proves
that $X^{2}=X\cdot X\subseteq X\cdot C=C$ is a clique of $\Gamma$. Moreover,
$X^{2}$ is closed under inversion and $1\in X^{2}\subseteq C$. Hence $\langle
X\rangle=X\cup X^{2}\cup X^{4}\cup\dotsc\subseteq C$ by induction. ∎

We observe that the second part of Lemma 3.2 and Lemma 3.3 together imply [15,
Lemma 14] of Federici.

######  Lemma 3.4.

Let $\mathrm{Cay}(G,\Sigma)$ be geodetic and let $H_{1},H_{2}\leq G$ be
complete subgroups. If $H_{1}\cap H_{2}\neq 1$ then $\langle
H_{1},H_{2}\rangle$ is also a complete subgroup of $G$.

###### Proof.

Under these assumptions $H_{1}\cup H_{2}$ is a clique (Lemma 2.5). Since $1\in
H_{1}\cup H_{2}$ and $H_{1}\cup H_{2}$ is closed under inversion, $\langle
H_{1},H_{2}\rangle$ is a clique by Lemma 3.3. ∎

######  Lemma 3.5.

Let $\Gamma=(V,E)$ be a biconnected vertex-transitive non-complete geodetic
graph and let $C\subseteq V$ be a clique of $\Gamma$ of size $k$. Then there
is an independent set $I\subseteq\mathcal{N}(C)$ of size $k^{2}-k$.

###### Proof.

By [19, Corollary 1] every biconnected non-complete geodetic graph containing
a clique of size $k$ also contains the star graph $K_{1,k}$ as an induced
subgraph. In other words, there exists a vertex $v\in V$ with an independent
set of size $k$ in its neighborhood $\mathcal{N}(v)$. As $\Gamma$ is vertex-
transitive, for every vertex $v\in V$ there is an independent set
$I(v)\subseteq\mathcal{N}(v)$ of size $k$.

Fix a maximal clique $\tilde{C}$ of $\Gamma$ with $C\subseteq\tilde{C}$ and
set $\tilde{I}(v)\coloneqq I(v)\mathbin{\mathchoice{\raisebox{0.3pt}{\hbox{
\leavevmode\hbox to4.1pt{\vbox to5.8pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{3.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{5.2pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to4.1pt{\vbox to5.8pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{3.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{5.2pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to2.65pt{\vbox to4.25pt{\pgfpicture\makeatletter\hbox{\hskip
0.22499pt\lower-0.22499pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{{}{}}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.45pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{2.2pt}{0.0pt}\pgfsys@lineto{0.0pt}{3.8pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to1.9pt{\vbox to3.2pt{\pgfpicture\makeatletter\hbox{\hskip
0.2pt\lower-0.2pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{{}{}}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{1.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.8pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}}\tilde{C}$. Since
an independent set can contain at most one vertex of any given clique, we have
$\left|\mathinner{\smash{\tilde{I}}(v)}\right|\geq\left|\mathinner{I(v)}\right|-1=k-1$.

We claim that $\tilde{I}(u)\cap\tilde{I}(v)=\emptyset$ for distinct $u,v\in
C$. If there were a vertex $x\in\tilde{I}(u)\cap\tilde{I}(v)$, then we would
have $x\in\tilde{C}$ by Lemma 2.5, because $x$ is adjacent to two vertices in
$\tilde{C}$. That contradicts the definition of $\tilde{I}$ which excludes
vertices in $\tilde{C}$.

Let $I\coloneqq\bigcup_{v\in C}\tilde{I}(v)\subseteq\mathcal{N}(C)$ and
observe that $\left|\mathinner{I}\right|\geq k(k-1)=k^{2}-k$, as the union is
disjoint. It remains to show that $I$ is indeed an independent set. Assume
there are $x,y\in I$ with $\\{x,y\\}\in E$. By definition of $I$ there are
$u,v\in C$ such that $x\in\tilde{I}(u)$ and $y\in\tilde{I}(v)$. We must have
$u\neq v$, as $\tilde{I}(u)$ is an independent set. Now we have a 4-cycle
$u,x,y,v$. By Lemma 2.3 this implies the existence of the edge $\\{u,y\\}$.
Now $y$ is a neighbor of both $u$ and $v$. That implies $y\in\tilde{C}$ by
Lemma 2.5, a contradiction with definition of $\tilde{I}$. ∎

######  Proposition 3.6.

Let $\Gamma=\mathrm{Cay}(G,\Sigma)$ be a geodetic but not complete Cayley
graph. If $H\leq G$ is a complete subgroup with respect to $\Sigma$, then
$\left|\mathinner{G}\right|\geq\left|\mathinner{H}\right|^{3}-\left|\mathinner{H}\right|^{2}+\left|\mathinner{H}\right|$.

###### Proof.

By Lemma 3.5 there is an independent set of size
$\left|\mathinner{H}\right|^{2}-\left|\mathinner{H}\right|$ in the
neighborhood of $H$. We now look at the left cosets of $H$. Each such coset is
a clique of $\Gamma$. Thus, each coset can contain at most one point of the
independent set. Since $H$ itself does not contain any point of the
independent set, the index of $H$ is at least
$\left|\mathinner{H}\right|^{2}-\left|\mathinner{H}\right|+1$. Hence,
$\left|\mathinner{G}\right|=\left|\mathinner{G:H}\right|\left|\mathinner{H}\right|\geq\left|\mathinner{H}\right|^{3}-\left|\mathinner{H}\right|^{2}+\left|\mathinner{H}\right|$.
∎

###  3.2. Conjugacy classes and elements of order two

######  Lemma 3.7 (Conjugacy class of generators).

Let $G$ be a group with geodetic Cayley graph $\mathrm{Cay}(G,\Sigma)$ and
$H\leq G$ such that $H=\langle H\cap\Sigma\rangle$. If $x^{H}\subseteq\Sigma$
for some $x\in\Sigma$, then $H\cap\Sigma=\\{x^{\pm 1}\\}$ or $H$ is a complete
subgroup.

###### Proof.

If $y\in H\cap\Sigma$ with $y\neq x^{\pm 1}$, then $x^{y}\in\Sigma$ and,
therefore, $yx^{y}=xy\in\Sigma$ as this element cannot have length zero or
two. We also have $x^{-1}y\in\Sigma$ and $yx^{\pm 1}\in\Sigma$ by symmetry.

If $H\cap\Sigma\neq\\{x^{\pm 1}\\}$, then there exists $y\in H\cap\Sigma$ with
$y\neq x^{\pm 1}$. We will show that every $uv\in G$ with $u,v\in H\cap\Sigma$
has length at most one. If $u\not\in\\{x^{\pm 1}\\}$ and $v\in\\{x^{\pm
1}\\}$, or vice versa, then this follows from the argument above. Otherwise,
first consider the case that $u,v\not\in\\{x^{\pm 1}\\}$ and define
$u^{\prime}\coloneqq ux$ and $v^{\prime}\coloneqq\overline{x}v$. As
$u^{\prime}=ux=x^{\overline{u}}u$, we have $u^{\prime}\in\Sigma$ and likewise
$v^{\prime}\in\Sigma$. Since $uv=u^{\prime}v^{\prime}$, it follows that
$uv\in\Sigma$. Finally, if $u,v\in\\{x^{\pm 1}\\}$, we set
$u^{\prime}\coloneqq uy$ and $v^{\prime}\coloneqq y^{-1}v$ and by the same
argument conclude that $uv\in\Sigma$. ∎

The above lemma may seem technical but is extremely useful, for example, as
demonstrated by the following consequences.

######  Corollary 3.8 (Commuting generators).

Let $\mathrm{Cay}(G,\Sigma)$ be geodetic. If $ab=ba$ and $a\neq b^{\pm 1}$ for
some $a,b\in\Sigma$, then the subgroup $\langle a,b\rangle$ is complete.

###### Proof.

Apply Lemma 3.7 with $H=\langle a,b\rangle$ and $x=a$. ∎

Since in any non-cyclic abelian group we must have two commuting generators,
we obtain the following result first shown by Georgakopoulos and presented in
[15].

######  Corollary 3.9 ([15, Proposition 10]).

Let $G$ be a non-cyclic abelian group with generating set $\Sigma$ such that
the Cayley graph is geodetic. Then $\mathrm{Cay}(G,\Sigma)$ is complete.

If in a cyclic group of order at least 3 we have $\Sigma=\\{a,\overline{a}\\}$
for some generator $a$ of $G$, then the Cayley graph is a cycle; hence, it is
geodetic if and only if $\left|\mathinner{G}\right|$ is odd. (Note that the
cyclic group of order 2 is a special (redundant) case: its only geodetic
Cayley graph comes from the generating set consisting of the unique non-
trivial element.) Otherwise, we can again apply Corollary 3.8 and obtain the
following.

######  Corollary 3.10.

Let $G$ be a cyclic group with generating set $\Sigma$ such that the Cayley
graph is geodetic. Then either the Cayley graph is a complete graph or a cycle
of odd length (and, hence, $\left|\mathinner{G}\right|$ is odd).

Another immediate consequence of Lemma 3.7 is that if a geodetic generating
set $\Sigma$ contains any (necessarily non-trivial) conjugacy class $x^{G}$,
then the associated Cayley graph $\mathrm{Cay}(G,\Sigma)$ is complete or an
odd cycle. As particular special cases of this observation, we obtain:

######  Corollary 3.11 (Generator in center).

Let $G$ be a group with generating set $\Sigma$ and
$Z(G)\cap\Sigma\neq\emptyset$. Then the Cayley graph $\mathrm{Cay}(G,\Sigma)$
is geodetic if and only if it is a complete graph or an odd cycle.

######  Corollary 3.12 (Complete normal subgroup).

Let $G$ be a group with generating set $\Sigma$ and $N\trianglelefteq G$ a
non-trivial normal subgroup which is complete with respect to $\Sigma$. Then
$\mathrm{Cay}(G,\Sigma)$ is geodetic if and only if it is a complete graph.

If a group has an element of order 2 we have the following.

######  Lemma 3.13 (Order-two elements).

Let $G$ be a group with generating set $\Sigma$ such that the Cayley graph is
geodetic. Let $g\in G$ be an element of order two. Then the geodesic for $g$
is of the form

$(w_{1}\cdots w_{\ell})\cdot
w_{\ell+1}\cdot(\overline{w_{\ell}}\cdots\overline{w_{1}})$

of length $2\ell+1$ where $\ell\in\mathbb{N}$ and each $w_{i}\in\Sigma$. In
particular, $\Sigma$ contains an element of order two conjugate to $g$, namely
$w_{\ell+1}$.

###### Proof.

Let $w_{1}\cdots w_{k}\in\Sigma^{\ast}$ be a geodesic for $g$. We have
$g=g^{-1}$ and thus $w_{1}\cdots
w_{k}=\overline{w_{k}}\cdots\overline{w_{1}}$. Hence, we have two paths of
length $k$ that lead from $1$ to $g$. Since $\operatorname{Cay}(G,\Sigma)$ is
geodetic, $g$ must have a unique geodesic, i.e., the two paths must coincide;
hence, $w_{i}=\overline{w_{k-i+1}}$ for $i\in\\{1,\dots,k\\}$.

If $k$ is even, then $g=(w_{1}\cdots w_{k/2})\cdot(w_{k/2+1}\cdots
w_{k})\equiv(w_{1}\cdots
w_{k/2})\cdot(\overline{w_{k/2}}\cdots\overline{w_{k}})=1$, contradicting the
assumption that $g$ is of order two. Thus, $k=2\ell+1$ must be odd and we
obtain the equation

$\displaystyle g$ $\displaystyle=(w_{1}\cdots w_{\ell})\cdot
w_{(\ell+1}\cdot(w_{(\ell+2}\cdots w_{k})$ $\displaystyle\equiv(w_{1}\cdots
w_{\ell})\cdot
w_{\ell+1}\cdot(\overline{w_{\ell}}\cdots\overline{w_{1}})\text{.}$

Hence, $g$ is conjugate to $w_{\ell+1}\in\Sigma$ and
$w_{\ell+1}=\overline{w_{\ell+1}}$, proving the lemma. ∎

The above results lead to the following observation which turns out to be
extremely useful in any computer search, since it shows that every $2$-group
immediately satisfies A.

######  Theorem 3.14 (Even order center).

Let $G$ a group such that $Z(G)$ is of even order. Then the only geodetic
Cayley graph of $G$ is the complete graph.

###### Proof.

Assume we have a geodetic Cayley graph of $G$. By Lemma 3.13, the generating
set $\Sigma$ must contain one element of each conjugacy class of order two
elements in $G$. Since $Z(G)$ is of even order it must contain an order two
element $g$. As $g$ is in the center of the group, it is not conjugate to any
other elements. Hence, $g\in\Sigma$ and by Corollary 3.11, the Cayley graph is
either complete, or an odd cycle. Since $G$ contains an even order subgroup,
$G$ itself has even order. Therefore, the Cayley graph cannot be an odd cycle,
so it must a be complete graph. ∎

######  Remark 3.15.

All but $4734$ groups of the approximately $49.5$ billion groups of order at
most $1024$ are covered by the combination of Theorem 3.14 and Corollary 3.9.

###  3.3. Cayley graphs of diameter two

######  Lemma 3.16.

If $\Gamma=\mathrm{Cay}(G,\Sigma)$ is geodetic and has diameter $2$, then
$\Gamma$ is the cycle $C_{5}$ of length $5$.

###### Proof.

From Stemple [32] we know that every geodetic graph of diameter two falls into
one of the following classes: block graphs joining all cliques in one vertex,
biconnected graphs with exactly two different vertex degrees, and Moore graphs
of diameter two.

Among these, the Moore graphs are the only regular graphs. The Moore graphs of
diameter two are the $C_{5}$, the Petersen graph, the Hoffman-Singleton graph
and a hypothetical graph of degree $57$ [1, 7]. A degree-57 Moore graph cannot
be vertex-transitive [4, Theorem 1.13], and, the Petersen graph and Hoffman-
Singleton graph are not Cayley graphs [28] (see also [23] or our own computer
search). Thus $C_{5}$ is the only geodetic Cayley graph of diameter 2. ∎

The combination of Lemma 3.13 and Lemma 3.7 affords a short elementary proof
of the (well-known) fact that the Moore graphs of diameter 2, other than
$C_{5}$, are not Cayley graphs.

######  Proposition 3.17.

The Petersen graph, the Hoffman-Singleton graph, and all of the hypothetical
Moore graphs of degree $57$ and diameter $2$ are not Cayley graphs.

###### Proof.

Assume that $\Gamma=\mathrm{Cay}(G,\Sigma)$ for one of these graphs. Then
$\left|\mathinner{G}\right|$ is even and, as such, there exist elements of
order two in $G$. Since $\Gamma$ is geodetic and has diameter two, each such
element is contained in $\Sigma$ by Lemma 3.13. But then $\Sigma$ contains an
entire conjugacy class. By Lemma 3.7, the graph $\Gamma$ would therefore have
to be complete or a cycle, both of which is absurd. ∎

###  3.4. Central elements

######  Lemma 3.18.

Let $\mathrm{Cay}(G,\Sigma)$ be geodetic and $b,t\in\Sigma$. Suppose that
$b^{2}\neq 1$, $t^{2}=1$, and $b^{2}t=tb^{\pm 2}$. Then the subgroup $\langle
b,t\rangle\leq G$ is complete with respect to $\Sigma$.

###### Proof.

If $bt=tb^{\pm 1}$, then the statement follows from Lemma 3.7, so assume that
$bt\neq tb^{\pm 1}$ holds. As $bbt=tbb$ or $bbt=t\overline{b}\overline{b}$, we
have $s\coloneqq bt\overline{b}=\overline{b}tb$ or $s\coloneqq
btb=\overline{b}t\overline{b}$, respectively. In particular, there are two
words of length three representing $s$; thus there must be a shorter one.
Moreover, since $s$ has order two, its geodesic must have odd length. Hence,
$s\in\Sigma$. The situation is as shown in Figure 1.

$t$$s$$t$$t$$s$$t$$b$$b$$b$$b$$b$$b$$b$

$t$$s$$t$$t$$s$$t$$b$$b$$b$$b$$b$$b$$b$

Figure 1. The situation in the proof of Lemma 3.18.

Let $H\coloneqq\langle b,t,s\rangle=\left<\mathinner{H\cap\Sigma}\right>\leq
G$. One may verify by straightforward computations (conjugating $st$ by
$b,\bar{b},s,t$) that $(st)^{H}=\\{st,ts\\}\subseteq\Sigma$. The statement
then follows using Lemma 3.7. ∎

######  Lemma 3.19.

Let $\mathrm{Cay}(G,\Sigma)$ be geodetic. If there exists some $b\in\Sigma$
with $b^{2}\neq 1$ and $(b^{2})^{G}\subseteq\\{b^{\pm 2}\\}$, then
$\mathrm{Cay}(G,\Sigma)$ is an odd cycle or a complete graph.

###### Proof.

Suppose first, that $(b^{2})^{G}=\\{b^{2}\\}$ and thus $b^{2}\in Z(G)$. Then
either $b\in Z(G)$ or $b\not\in Z(G)$. In the first case, the statement
follows immediately from Lemma 3.7. In the second case,
$\left|\mathinner{G:Z(G)}\right|$ is even; hence so is
$\left|\mathinner{G}\right|$. As such, there exists an element of order two in
$G$. In fact, there even exists $t\in\Sigma$ with $t^{2}=1$ by Lemma 3.13. The
statement now follows from Lemma 3.18 and Lemma 3.7.

Finally, suppose that $(b^{2})^{G}=\\{b^{\pm 2}\\}$ has two elements. Then
$\left|\mathinner{G:C_{G}(b^{2})}\right|=2$ and, as before, there thus exists
some $t\in\Sigma$ with $t^{2}=1$. The statement follows from Lemma 3.18 and
Lemma 3.7. ∎

######  Lemma 3.20 (Flat coset).

Let $G$ be a group with generating set $\Sigma$ such that the Cayley graph is
geodetic. If $w\in\Sigma^{m}$ is a geodesic of length $m$ and $a\in\Sigma$
such that $aw=wa$ and $w\neq a^{\pm m}$, then each $h\in w\langle a\rangle$
has a geodesic of length at most $m$.

Moreover, if $w\not\in\langle a\rangle$, then each $h\in w\langle a\rangle$
has a geodesic of length exactly $m$.

###### Proof.

By $w_{i}$ we denote the geodesic of $wa^{i}$. Let $r$ be the order of $a$ in
$G$. Observe that $w_{0}=w_{r}$.

First, we prove the lemma for the case $w\not\in\langle a\rangle$. Now
$aw_{i}$ and $w_{i}a$ are two different words of length $|w_{i}|+1$
representing $wa^{i+1}$. Thus, there must be a shorter word, implying that
$|w_{i+1}|\leq|w_{i}|$. Therefore,
$m=|w_{r}|\leq\dots\leq|w_{i}|\leq\dots\leq|w_{0}|=m$, and we conclude
$|w_{i}|=m$ for all $i$.

Second, we consider the case $w=a^{k}$. Recall that $w_{i}$ is the geodesic
for $wa^{i}=a^{i+k}$. Observe that, because the geodesic of $a^{k}$ has length
$m$, we must have $m\leq k$. In fact, because $w\neq a^{\pm m}$, we have
$m<k$. Using the same argument, we also have $m<r-k$. We proceed by induction
on $i$ that $|w_{i}|\leq m$. For $w_{0}=w_{r}=w$ this obviously holds.

If $0<i\leq r-k$, then we have two words, $w_{i-1}a$ and $aw_{i-1}$ of length
$|w_{i-1}|+1$ for $a^{i+k}=w_{i}$. The two words are different, because
$w_{i-1}\neq a^{|w_{i-1}|}$: If $w_{i-1}$ were a power of $a$, then
$w_{i-1}=a^{i+k-1}$. For $i=1$ this contradicts one of the conditions of the
lemma, for $i>1$ we have $|w_{i-1}|\leq m<k<i+k-1$. Thus, the geodesic $w_{i}$
has length at most $|w_{i-1}|\leq m$.

For $r-k\leq i<r$, we also use induction on decreasing values of $i$,
multiplying with $\overline{a}$. Now $w_{r}=w$ is the induction base. Assuming
the statement holds for $i+1$, the two words $w_{i+1}\overline{a}$ and
$\overline{a}w_{i+1}$ both correspond to the group element $a^{i+k}=w_{i}$.
For $i=r-1$ they are different because of the conditions of the lemma, for
$i<r-1$ we show that $w_{i+1}\neq a^{|w_{i+1}|}$: If $w_{i+1}$ were a power of
$\overline{a}$, then $w_{i+1}={\overline{a}}^{2r-k-i-1}$ leading to the
contradiction $2r-k-i-1>r-k>m\geq|w_{i+1}|$. Therefore, we must have
$|w_{i}|\leq|w_{i+1}|\leq m$. ∎

$\bar{a}\mathstrut$$\bar{a}\mathstrut$$\bar{a}\mathstrut$$a\mathstrut$$a\mathstrut$$a\mathstrut$$w_{0}=a^{k}$$w_{r-k}=1$$w_{r-1}=a^{k-1}$$w_{r-k+d+1}=a^{d+1}$$w_{r-k+d}\equiv
a^{d}$$w_{r-k+1}\equiv
a^{1}$$w_{1}=a^{k+1}$$w_{r-k-d-1}=\bar{a}^{d+1}$$w_{r-k-d}\equiv\bar{a}^{d}$$w_{r-k-1}\equiv\bar{a}^{1}$
Figure 2. The coset $w\langle a\rangle$ in the case $w=a^{k}$ in the proof of
Lemma 3.20.

The second case of the proof, where $w=a^{k}$ is illustrated in Figure 2. One
can observe the two inductions, starting at $w$, one multiplying with $a$, the
other multiplying with $\overline{a}$ covering the entire subgroup. Before
arriving at $1$ we encounter small powers of $a$, respectively $\overline{a}$.
In fact, there is an integer $d\leq|w|$, such that $a^{i}$ and
$\overline{a}^{i}$ are geodesic for $0\leq i\leq d$, but for $j>d$ the words
$a^{j}$ and ${\overline{a}}^{j}$ are not geodesics. By applying Lemma 3.20 to
the geodesic of $a^{d+1}$, which has length $d$, we obtain $d=m$.

######  Lemma 3.21 (Geodesics for central elements are powers of generators).

Let $G$ be a group with geodetic Cayley graph $\operatorname{Cay}(G,\Sigma)$,
and let $z\in Z(G)\mathbin{\mathchoice{\raisebox{0.3pt}{\hbox{
\leavevmode\hbox to4.1pt{\vbox to5.8pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{3.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{5.2pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to4.1pt{\vbox to5.8pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{3.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{5.2pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to2.65pt{\vbox to4.25pt{\pgfpicture\makeatletter\hbox{\hskip
0.22499pt\lower-0.22499pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{{}{}}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.45pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{2.2pt}{0.0pt}\pgfsys@lineto{0.0pt}{3.8pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to1.9pt{\vbox to3.2pt{\pgfpicture\makeatletter\hbox{\hskip
0.2pt\lower-0.2pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{{}{}}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{1.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.8pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}}1$. Then the
unique geodesic of $z$ is $a^{k}$ for some $a\in\Sigma$ and $k\geq 1$.

###### Proof.

Let $w_{1}\cdots w_{k}\in\Sigma^{*}$ be a geodesic for $z$. As $z$ is in the
center we have

$w_{1}w_{2}\cdots w_{k}=z=z^{w_{1}}=w_{2}\cdots w_{k}w_{1}\text{.}$

Now we have two words of length $k$ representing $z$. There cannot be a
shorter word, as we chose $w_{1}\cdots w_{k}$ to be a geodesic. The Cayley
graph is geodetic, thus the two words must coincide: we obtain
$w_{1}=w_{2}=\dots=w_{k}$. ∎

######  Theorem 3.22 (Geodesics for central elements are powers with the same
exponent).

Let $G$ be a group with geodetic Cayley graph $\operatorname{Cay}(G,\Sigma)$
and $\Sigma\cap Z(G)=\emptyset$. Then, there is an integer $k\geq 3$ such that
for each $z\in Z(G)\mathbin{\mathchoice{\raisebox{0.3pt}{\hbox{
\leavevmode\hbox to4.1pt{\vbox to5.8pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{3.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{5.2pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to4.1pt{\vbox to5.8pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{3.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{5.2pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to2.65pt{\vbox to4.25pt{\pgfpicture\makeatletter\hbox{\hskip
0.22499pt\lower-0.22499pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{{}{}}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.45pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{2.2pt}{0.0pt}\pgfsys@lineto{0.0pt}{3.8pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to1.9pt{\vbox to3.2pt{\pgfpicture\makeatletter\hbox{\hskip
0.2pt\lower-0.2pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{{}{}}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{1.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.8pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}}1$ there exists an
element $c_{z}\in\Sigma$ such that $c_{z}^{k}$ is the geodesic for $z$.

In light of this theorem, we can refer to the _length of central geodesics_ as
the integer $k$ so that $z=c_{z}^{k}$ for any element $z\in Z(G)$. Note that
$k$ divides the order of $G/Z(G)$. We refer to the above elements $c_{z}$ as
_central roots_.

###### Proof.

We know by Lemma 3.21 that the geodesic of every element in the center is a
power of a generator. We first show that no two central elements can have a
geodesic that is a power of the same generator (note that a generator and its
inverse is allowed and will happen). Let $b^{k}$ be a geodesic representing a
central element and assume $k$ is minimal so that $b^{k}$ is central. Let $g$
be a generator different to $b^{\pm}$ (such a generator must exist, otherwise
$G$ would be a cyclic group, but then $b\in Z(G)$). By Lemma 3.20 the elements
$b^{k}g$ and $b^{k}\overline{g}$ both have a geodesic of length at most $k$,
which we write as $(b^{k}g)$ and $(b^{k}\overline{g})$. Now
$(b^{k}g)(b^{k}\overline{g})$ is a word of length at most $2k$ representing
the central element $b^{2k}$. Thus, $b^{2k}$ is not a geodesic. It follows
that no power of $b$ other than $k$ gives a geodesic for a central element,
since $k$ is minimal and $b^{k+i}$ geodesic and central would imply $b^{i}$
geodesic and central, so $i\geq k$.

Next we show that the geodesics of all central elements have the same length.
For a central element and its inverse this is obvious. Assume there are
$c,d\in\Sigma$ with $c\notin\\{d,\overline{d}\\}$ and $k,\ell\in\mathbb{N}$
such that $c^{k}$ and $d^{\ell}$ both are geodesics representing different
central elements. Note that $c^{k}\neq\overline{d}^{\ell}$ because both are
geodesics. Now assume for a contradiction that $k\neq\ell$, w. l. o. g.
$k<\ell$. Lemma 3.20 tells us that $c^{k}d^{\ell}\in c^{k}\langle d\rangle$
has a geodesic $u$ of length at most $k$. But $c^{k}d^{\ell}$ is also in the
center (and non-trivial), so $u=f^{m}$ for some $f\in\Sigma,m\leq k$. Applying
Lemma 3.20 again to $d^{\ell}=f^{m}c^{-k}\in f^{m}\langle c\rangle$, we obtain
a geodesic $v$ of length at most $m\leq k<\ell$, contradicting $d^{\ell}$
being a geodesic.

It remains to show, that no central element has a geodesic of length two. In
that case the Cayley graph would be cyclic or complete by Lemma 3.19,
contradicting $\Sigma\cap Z(G)=\emptyset$. ∎

######  Lemma 3.23.

Let $\operatorname{Cay}(G,\Sigma)$ be geodetic. If there is an element $z\in
Z(G)$, with $\operatorname{ord}(z)\geq 4$, then the length of central
geodesics must be odd.

###### Proof.

Let $m=\operatorname{ord}(z)$. If $m$ is even, then the statement follows from
Corollary 3.11. Thus from here on $m\geq 5$.

Assume that $b^{2k}$ is the geodesic for $z$. Let $y$ be the geodesic for
$z^{(m-1)/2}$. By Theorem 3.22 it has length $2k$. As $m\geq 5$, we have
$y\neq b^{\pm 2k}$. By Lemma 3.20, the element $t=b^{km}=yb^{k}$ has length at
most $2k$. It also has order two, thus by Lemma 3.13 it must have odd length,
that is, the length of $t$ is at most $2k-1$. Applying Lemma 3.20 to
$y=t\overline{c}^{k}$ we obtain the contradiction $|y|\leq 2k-1$. ∎

##  4\. Bounds on the size of generating sets

In this section we establish bounds on the possible sizes of those generating
sets $\Sigma$ of a group $G$ which result in a geodetic but neither complete
nor cyclic Cayley graph $\Gamma=\mathrm{Cay}(G,\Sigma)$.

Our method utilizes the following properties of the structure balls of radius
one and two. Throughout, we denote the $r$-ball in $\Gamma$ centered at a
vertex $g\in G$ by $\mathcal{B}_{r}(g)\coloneqq\\{h\in G\,\mid\,d(g,h)\leq
r\\}$. As Cayley graphs are vertex-transitive, all balls of the same radius
$r$ are isomorphic subgraphs of $\Gamma$.

We begin by analyzing the structure of one-balls. By Lemma 2.6 the neighbors
of any $g\in G$ can be partitioned into a set of disjoint cliques. We denote
by $m$ the number of these disjoint cliques and by
$\delta_{1}\leq\delta_{2}\leq\dotsc\leq\delta_{m}$ their sizes. Clearly,
$\delta\coloneqq\sum_{i=1}^{m}\delta_{i}$ is the degree of $\Gamma$ and thus
$\delta=\left|\mathinner{\Sigma}\right|$.

######  Lemma 4.1.

We have $m\geq 1+\delta_{m}\geq 1+\delta/m$. If $\Gamma$ is not complete or a
cycle, then $m\geq 3$.

###### Proof.

The Cayley graph $\Gamma$ contains a clique of size $\delta_{m}+1$. By [19,
Corollary 1] the neighborhood of some and, hence, of every vertex contains an
independent set of size $\delta_{m}+1$. Thus $m\geq\delta_{m}+1$ by definition
of $m$. The second inequality follows from
$\delta=\sum_{i=1}^{m}\delta_{i}\leq\sum_{i=1}^{m}\delta_{m}\leq m\delta_{m}$.

For the final inequality, note that $m\leq 1$ holds if and only if $\Gamma$ is
complete. If $m=2$, then the above argument shows that
$\delta_{1}=\delta_{2}=1$ and thus $\delta=2$. If both elements of $\Sigma$
are of order two, then $G$ is a dihedral group and $\Gamma$ is an even cycle;
hence, $\Gamma$ is not geodetic. Otherwise, the two elements of $\Sigma$ are
inverses of one another and, as such, the group $G$ is cyclic. But then
$\Gamma$ is complete, a cycle, or not geodetic by Corollary 3.10. The only
remaining possibility is $m\geq 3$. ∎

######  Lemma 4.2.

For every $g\in G$, the size of the two-ball centered at $g$ satisfies

$\left|\mathinner{\mathcal{B}_{2}(g)}\right|=1+\delta+\delta^{2}-\sum_{i=1}^{m}\delta^{2}_{i}\geq
1+\delta+\tfrac{1}{2}\alpha\delta^{2}\quad\text{ where
}\quad\alpha=\alpha(m)\coloneqq\frac{3m-4}{2m-2}.$

###### Proof.

Every vertex at distance one from $g$ which is contained in a clique of size
$\delta_{i}$ has $\delta-\delta_{i}$ neighbors at distance two from $g$. As
each vertex at distance two from $g$ has a unique neighbor at distance one
from $g$, we obtain the equality

$\left|\mathinner{\mathcal{B}_{2}(g)}\right|=1+\delta+\sum_{i=1}^{m}\delta_{i}(\delta-\delta_{i})=1+\delta+\delta^{2}-\sum_{i=1}^{m}\delta_{i}^{2}.$

We then apply the reversed Cauchy-Schwarz inequality due to Pólya and Szegő
[27, pp. 57, 213–214] with the bounds $1\leq\delta_{i}\leq m-1$ obtained in
Lemma 4.1. This yields

$m\sum_{i=1}^{m}\delta_{i}^{2}=\left(\sum_{i=1}^{m}1^{2}\right)\cdot\left(\sum_{i=1}^{m}\delta_{i}^{2}\right)\leq\frac{1}{4}\frac{m^{2}}{m-1}\left(\sum_{i=1}^{m}\delta_{i}\right)^{2}=\frac{1}{4}\frac{m^{2}}{m-1}\delta^{2},$

from which the claimed inequality follows. ∎

######  Lemma 4.3.

Let $g,h\in G$. If $d(g,h)\geq 3$, then
$\left|\mathinner{\mathcal{B}_{2}(g)\cap\mathcal{B}_{2}(h)}\right|\leq
2\delta-1$.

###### Proof.

Let $h^{\prime}$ be the vertex preceding $h$ on the geodesic path from $g$ to
$h$. Then $\mathcal{B}_{2}(g)\cap\mathcal{B}_{1}(h)\subseteq\\{h^{\prime}\\}$
by uniqueness of geodesics. Hence,
$\left|\mathinner{\mathcal{B}_{2}(g)\cap\mathcal{B}_{1}(h^{\prime})}\right|\leq\delta$.
If
$h^{\prime\prime}\in\mathcal{N}(h)\mathbin{\mathchoice{\raisebox{0.3pt}{\hbox{
\leavevmode\hbox to4.1pt{\vbox to5.8pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{3.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{5.2pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to4.1pt{\vbox to5.8pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{3.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{5.2pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to2.65pt{\vbox to4.25pt{\pgfpicture\makeatletter\hbox{\hskip
0.22499pt\lower-0.22499pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{{}{}}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.45pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{2.2pt}{0.0pt}\pgfsys@lineto{0.0pt}{3.8pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to1.9pt{\vbox to3.2pt{\pgfpicture\makeatletter\hbox{\hskip
0.2pt\lower-0.2pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{{}{}}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{1.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.8pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}}\\{h^{\prime}\\}$,
then $d(g,h^{\prime\prime})\geq 3$ which implies
$\left|\mathinner{\mathcal{B}_{2}(g)\cap\mathcal{B}_{1}(h^{\prime\prime})}\right|\leq
1$. In total we obtain
$\left|\mathinner{\mathcal{B}_{2}(g)\cap\mathcal{B}_{2}(h)}\right|\leq
2\delta-1$. ∎

We now have all the tools necessary to prove the main result of this section.

######  Theorem 4.4.

Let $\mathrm{Cay}(G,\Sigma)$ be geodetic but neither complete nor a cycle. If

$\alpha_{0}=\alpha(m_{0})=\frac{3m_{0}-4}{2m_{0}-2}$

where $m_{0}\geq 3$ is any integer with
$\frac{1}{2}(m_{0}-1)(3m_{0}-4)(m_{0}-2)^{2}<\left|\mathinner{G}\right|$, then
$\alpha_{0}\left|\mathinner{\Sigma}\right|^{2}<\left|\mathinner{G}\right|$.

######  Remark 4.5.

Before proceeding with the proof, we note that the factor
$\alpha_{0}=\alpha(m_{0})$ is monotonically increasing in $m_{0}$. The choice
$m_{0}=3$ is always valid and yields $\alpha_{0}=\tfrac{5}{4}$. On the other
hand, $\alpha_{0}\to\frac{3}{2}$ as $m_{0}\to\infty$. Moreover, as a byproduct
of our computer experiments, we obtain _a posteriori_ that the conclusion of
Theorem 4.4 holds with $\alpha_{0}=\frac{7}{5}$, i.e., we obtain D: after
verifying that A holds every group of order at most $560$ (see B), we set
$m_{0}=6$.

We use a combination of the bound obtained in Theorem 4.4, as well as other
ones discussed hereafter, in our computer experiments. This results in a
massive reduction in the number of generating sets we have to consider. In
order to make these bounds as tight as possible, we choose the maximal value
$m_{0}$ that is permitted for the group currently under examination. For some
groups, we also employ Theorem 3.22 to establish an improved lower bound on
the diameter which, in turn, allows us to replace Lemma 4.3 with a better
estimate.

###### Proof.

For the sake of deriving a contradiction, we assume that
$\alpha_{0}\left|\mathinner{\Sigma}\right|^{2}\geq\left|\mathinner{G}\right|$.
We also continue to employ the notation established above. In particular, the
previous inequality becomes
$\alpha_{0}\delta^{2}\geq\left|\mathinner{G}\right|$, and Lemma 4.1 then
yields
$\alpha_{0}(m^{2}-m)^{2}\geq\alpha_{0}\delta^{2}\geq\left|\mathinner{G}\right|$.
We cannot have $m<m_{0}$, for otherwise

$\tfrac{1}{2}(m_{0}-1)(3m_{0}-4)(m_{0}-2)^{2}=\alpha_{0}\big{(}(m_{0}-1)^{2}-(m_{0}-1)\big{)}^{2}\geq\alpha_{0}(m^{2}-m)^{2}\geq\left|\mathinner{G}\right|$

which contradicts the choice of $m_{0}$. Hence $m\geq m_{0}$ and, therefore,
also $\alpha=\alpha(m)\geq\alpha(m_{0})=\alpha_{0}$.

Finally, observe that $\mathrm{Cay}(G,\Sigma)$ has diameter at least three by
Lemma 3.16. Hence there exist elements $g,h\in G$ with $d(g,h)=3$. Using Lemma
4.2 and Lemma 4.3 we arrive at

$\left|\mathinner{\mathcal{B}_{2}(g)\cup\mathcal{B}_{2}(h)}\right|=\underbrace{\left|\mathinner{\mathcal{B}_{2}(g)}\right|+\left|\mathinner{\mathcal{B}_{2}(h)}\right|}_{\geq
2+2\delta+\alpha\delta^{2}}-\underbrace{\left|\mathinner{\mathcal{B}_{2}(g)\cap\mathcal{B}_{2}(h)}\right|}_{\leq
2\delta-1}\geq 3+\alpha\delta^{2}\geq 3+\alpha_{0}\delta^{2}\geq
3+\left|\mathinner{G}\right|.$

As such,
$\left|\mathinner{G}\right|\geq\left|\mathinner{\mathcal{B}_{2}(g)\cup\mathcal{B}_{2}(h)}\right|\geq\left|\mathinner{G}\right|+3>\left|\mathinner{G}\right|$,
which is the desired contradiction. ∎

######  Corollary 4.6.

If $\mathrm{Cay}(G,\Sigma)$ is geodetic but not complete or a cycle, then
$\alpha_{0}\big{(}\lvert{Z(G)}\rvert-1\big{)}^{2}\leq\left|\mathinner{G}\right|$.

###### Proof.

This follows from Theorem 4.4, as
$\left|\mathinner{\Sigma}\right|\geq\left|\mathinner{Z(G)}\right|-1$ by
Theorem 3.22 and Corollary 3.11. ∎

In Theorem 4.4 we have used two balls of radius two at distance three from
each other to give a lower bound to the size of the group. In cases where the
group has a non-trivial center, we can improve upon this. By Theorem 3.22, the
distance between any two central elements is at least three. Using a subset of
these as centers of balls of radius two, and Lemma 4.3 to bound the size of
pairwise intersections, we arrive at the following.

######  Theorem 4.7.

Let $\mathrm{Cay}(G,\Sigma)$ be geodetic but neither complete nor a cycle.
Then the inequality

$\tfrac{1}{2}\alpha_{0}z_{0}\left|\mathinner{\Sigma}\right|^{2}-z_{0}(z_{0}-2)\left|\mathinner{\Sigma}\right|+\tfrac{1}{2}z_{0}(z_{0}-1)\leq\left|\mathinner{G}\right|,$

where

$\alpha_{0}=\alpha(m_{0})=\frac{3m_{0}-4}{2m_{0}-2},$

holds for all integers $z_{0}$ with $1\leq
z_{0}\leq\left|\mathinner{Z(G)}\right|$ and all lower bounds $m_{0}$ on the
number $m\geq m_{0}$ of maximal cliques in the neighborhood $\mathcal{N}(1)$
of $1\in G$.

###### Proof.

Choose a set of $z_{0}$ central elements, say $Z_{0}\subseteq Z(G)$. By Lemma
4.2 and Lemma 4.3,

$\left|\mathinner{G}\right|\geq\Big{\lvert}\;\bigcup_{\mathclap{g\in
Z_{0}}}\mathcal{B}_{2}(g)\;\Big{\rvert}\geq\sum_{\mathclap{g\in
Z_{0}}}\left|\mathinner{\mathcal{B}_{2}(g)}\right|-\sum_{\mathclap{\begin{subarray}{c}g,h\in
Z_{0}\\\ g\neq
h\end{subarray}}}\left|\mathinner{\mathcal{B}_{2}(g)\cap\mathcal{B}_{2}(h)}\right|\geq
z_{0}\big{(}1+\delta+\tfrac{1}{2}\alpha\delta^{2}\big{)}-\binom{z_{0}}{2}\big{(}2\delta-1\big{)}$

with $\alpha\geq\alpha_{0}$. Upon expanding the rightmost expression one
obtains the stated inequality. ∎

Note that for groups with small center, the best lower bound is achieved by
$z_{0}=|Z(G)|$. However, if the center is large enough, then at some point it
is no longer beneficial to place more balls, due to the way we approximate the
intersection. The best lower bound is obtained for
$z_{0}\approx\frac{1}{4}\alpha_{0}\delta$. Based on this observation we obtain
the following bound on the center using
$\left|\mathinner{\Sigma}\right|\geq\left|\mathinner{Z(G)}\right|-1$ and
setting
$z_{0}=\big{\lceil}\frac{1}{4}\alpha_{0}\big{(}\left|\mathinner{Z(G)}\right|-1\big{)}\big{\rceil}+1$.

######  Corollary 4.8.

If $\mathrm{Cay}(G,\Sigma)$ is geodetic but not complete or a cycle, then
$\frac{1}{16}\alpha_{0}^{2}\big{(}\lvert{Z(G)}\rvert-1\big{)}^{3}\leq\left|\mathinner{G}\right|$.

If the central geodesics are sufficiently long, then we can obtain an even
better bound by placing balls along these central geodesics (as opposed to
only their endpoints). We begin with the following estimate on the distance
between two points on two different central geodesics.

######  Lemma 4.9.

Let $\mathrm{Cay}(G,\Sigma)$ be geodetic but not complete or a cycle. Let
$g=ya^{i}$ and $h=zb^{j}$, where $y,z\in Z(G)$ and $a,b\in\Sigma$, be two
points on two different central geodesics. Then

$d(g,h)\geq\max\\{\min\\{i,k-i\\},\min\\{j,k-j\\}\\},$

where $k$ is the length of the central geodesics.

###### Proof.

If any of $y$, $ya^{k}$, $z$ and $zb^{k}$ coincide, then we may assume that
$ya^{k}=zb^{k}$. This can be achieved by replacing $y$ with $ya^{k}$ and $i$
with $k-i$ and/or replacing $z$ and $j$ suitably. This step is the origin of
the minima appearing in the statement. By Lemma 3.20, the geodesic from $y$ to
$h$ has length at least $k$, thus $d(g,h)\geq
k-\min\\{i,k-i\\}=\min\\{i,k-i\\}$. Similarly, $d(g,h)\geq\min\\{j,k-j\\}$. ∎

Multiple balls of radius two can be placed on each central geodesic if its
length permits that. However, we will only give an explicit bound for the
simplest case, placing a single such ball in the middle of each central
geodesic.

######  Proposition 4.10.

If $\mathrm{Cay}(G,\Sigma)$ is geodetic but not complete or a cycle,
$3\nmid|G|$, and $5,7\nmid|G:Z(G)|$, then
$\frac{1}{4}\alpha_{0}\big{(}\left|\mathinner{Z(G)}\right|-1\big{)}^{4}<\left|\mathinner{G}\right|$.

###### Proof.

As $3\nmid\left|\mathinner{G}\right|$, the length $k$ of central geodesics
must be odd by Lemma 3.23. As $5,7\nmid\left|\mathinner{G:Z(G)}\right|$ we
have $k\geq 11$. We place a 2-ball on the middle of each central geodesic. The
intersection between any pair of 2-balls is trivial, as the distance between
any two of their center points is at least 5. Thus we obtain

$\displaystyle\left|\mathinner{G}\right|$
$\displaystyle\geq\tfrac{1}{2}\left|\mathinner{Z(G)}\right|\big{(}\left|\mathinner{Z(G)}\right|-1\big{)}\left|\mathinner{\mathcal{B}_{2}(1)}\right|$
$\displaystyle\geq\tfrac{1}{2}\big{(}\left|\mathinner{Z(G)}\right|-1\big{)}^{2}\big{(}\tfrac{1}{2}\alpha\delta^{2}+\delta+1\big{)}$
$\displaystyle\geq\tfrac{1}{4}\alpha\big{(}\left|\mathinner{Z(G)}\right|-1\big{)}^{2}\delta^{2}\text{.}$

Using the inequality $\delta\geq\left|\mathinner{Z(G)}\right|-1$ yields the
desired bound. ∎

##  5\. Further cases: dihedral, nilpotent, groups with large commutativity
degree

In this section we show that further large families of groups satisfy A by
combining results from Section 3 with more detailed knowledge about finite
group theory and insights gleaned from the computer search.

We first consider groups that have an abelian subgroup of index two (which is
necessarily normal); these include the dihedral groups. Pushing this to index
three presents more challenges; so for that case we are able to prove the
conjecture only in the two important special cases when the subgroup is not
normal or when the center is trivial. For nilpotent groups we can prove the
conjecture holds in all groups of class two except for a particular subfamily
(see Corollary 5.16), and in groups of any class provided certain numerical
conditions are satisfied (see Theorem 5.9). Each of these families of groups
in some sense is close to abelian, which is emphasized by the fact that these
classes cover all groups with a high _commutativity degree_ (see Theorem
5.17).

###  5.1. Abelian subgroups of index two

######  Lemma 5.1.

Let $G$ be a group and $N\leq G$ a non-trivial subgroup with $\lvert
G:N\rvert=2$. If $\operatorname{Cay}(G,\Sigma)$ is geodetic then
$N\cap\Sigma\neq\emptyset$.

###### Proof.

If $\Sigma\cap N=\emptyset$, then every word $w\in\Sigma^{*}$ representing
$1\in G$ has even length. Hence, all cycles in $\operatorname{Cay}(G,\Sigma)$
must have even length. But then $\operatorname{Cay}(G,\Sigma)$ cannot be
geodetic (see Lemma 2.2). ∎

######  Theorem 5.2.

Let $\phi\colon A\to A$ be an order-two automorphism of an abelian group. Let

$D_{A,\phi}\coloneqq A\rtimes_{\phi}C_{2}=\langle X\cup\\{t\\}\mid
R\cup\\{t^{2},txt=\phi(x);x\in X\\}\rangle$

where $A=\langle X\mid R\rangle$ be the corresponding semidirect product. Then
the only geodetic Cayley graph of the group $D_{A,\phi}$ is the complete
graph.

###### Proof.

Assume that $\operatorname{Cay}(D_{A,\phi},\Sigma)$ is geodetic but not
complete (in particular, $Z(D_{A,\phi})\cap\Sigma=\emptyset$ by Corollary
3.11). Since $\mathrm{ord}(t)=2$, the generating set $\Sigma$ contains a
conjugate of $t$ by Lemma 3.13. Upon replacing $\Sigma$ with a suitable
conjugate if necessary, we may therefore assume that $t\in\Sigma$.

Since $\lvert D_{A,\phi}:A\rvert=2$, there exists some $x\in A\cap\Sigma$ by
Lemma 5.1. If $\phi(x)=x$, that is, $txt=x$ then $x\in Z(D_{A,\phi})$ which is
not possible. If $\phi(x)=\bar{x}$ then $x^{D_{A,\phi}}=\\{x^{\pm
1}\\}\subseteq\Sigma$. Since $\Sigma\neq\\{x^{\pm 1}\\}$, Lemma 3.7 implies
that $\operatorname{Cay}(D_{A,\phi},\Sigma)$ is complete. Thus
$\phi(x)\not\in\\{x^{\pm 1}\\}$. Note that $\phi(x)x$ commutes with $t$ since
$t\phi(x)x=ttxtx=xtxtt=x\phi(x)t=\phi(x)xt$ as $x,\phi(x)\in A$. Hence
$\phi(x)x\in Z(D_{A,\phi})\mathbin{\mathchoice{\raisebox{0.3pt}{\hbox{
\leavevmode\hbox to4.1pt{\vbox to5.8pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{3.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{5.2pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to4.1pt{\vbox to5.8pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{3.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{5.2pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to2.65pt{\vbox to4.25pt{\pgfpicture\makeatletter\hbox{\hskip
0.22499pt\lower-0.22499pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{{}{}}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.45pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{2.2pt}{0.0pt}\pgfsys@lineto{0.0pt}{3.8pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to1.9pt{\vbox to3.2pt{\pgfpicture\makeatletter\hbox{\hskip
0.2pt\lower-0.2pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{{}{}}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{1.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.8pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}}1$.

By Theorem 3.22, there exists $y\in\Sigma$ such that $\phi(x)x=y^{k}$ with
$k\geq 3$ and, therefore, with $k=3$ by uniqueness of geodesics (since
$\phi(x)x=txtx$). Thus, in particular, the length of central geodesics is
three. Now, suppose that $z\in\Sigma$ with $z^{3}\in Z(G)$. If $z\not\in A$
then $z=at$ for some $a\in A$. But then $z^{3}=atatat=a\phi(a)at$ and, since
this is central, $(a\phi(a)at)t=t(a\phi(a)at)=\phi(a)a\phi(a)$. As such,
$a^{2}\phi(a)=a\phi(a)^{2}$ which implies $a=\phi(a)$. Hence $t$ and $a$
commute, so $a$ is central. Now $z^{3}=a^{3}t$ implies $t=a^{-3}z^{3}\in
Z(G)$, which is a contradiction. It follows that every element of
$Z(D_{A,\phi})\mathbin{\mathchoice{\raisebox{0.3pt}{\hbox{ \leavevmode\hbox
to4.1pt{\vbox to5.8pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{3.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{5.2pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to4.1pt{\vbox to5.8pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{3.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{5.2pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to2.65pt{\vbox to4.25pt{\pgfpicture\makeatletter\hbox{\hskip
0.22499pt\lower-0.22499pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{{}{}}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.45pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{2.2pt}{0.0pt}\pgfsys@lineto{0.0pt}{3.8pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to1.9pt{\vbox to3.2pt{\pgfpicture\makeatletter\hbox{\hskip
0.2pt\lower-0.2pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{{}{}}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{1.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.8pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}}1$ is of the form
$z^{3}$ for some $z\in\Sigma\cap A$. In particular, this shows that
$y\in\Sigma\cap A$.

We now argue that we can find an element $z\in\Sigma\cap A$ with
$z\notin\\{y^{\pm 1}\\}$. If so, then $y$ and $z$ commute; hence
$z^{\left<\mathinner{y}\right>}=\\{z\\}\subseteq\Sigma$ and then we can apply
Lemma 3.7 to show that $\left<\mathinner{y}\right>$ is complete. However, this
implies $y^{3}\in\Sigma$ and thus $Z(G)\cap\Sigma\neq\emptyset$; contradicting
Corollary 3.11.

Firstly, suppose that $y=x$, then $x^{3}=y^{3}=\phi(x)x$ and thus
$\phi(x)=x^{2}$. We obtain the contradiction
$y^{3}=x^{3}=\overline{x}x^{4}=\overline{x}\phi(\phi(x))=\overline{x}x=1$.
Next, suppose that $y=x^{-1}$ holds. Then $x^{-3}=y^{3}=\phi(x)x$ and thus
$\phi(x)=x^{-4}$, or equivalently $\phi(y)=y^{-4}$. Then
$\phi(\phi(y))=\phi(y^{-4})=y^{16}$ and since $\phi$ is order two, this means
$y=y^{16}$ so $y^{15}=1$. This means the order of $y$ is either $3,5$, or
$15$. It cannot be $3$ since $y^{3}$ is a non-trivial element of the center.
If $y^{5}=1$ then $y\in Z(G)$ and so $Z(G)\cap\Sigma\neq\emptyset$ and we are
done. Thus $\operatorname{ord}(y)=15$. We then have $y^{6}\in Z(D_{A,\phi})$
and $y^{6}\notin\\{y^{\pm 3}\\}$. Thus $y^{6}=z^{3}$ for some $z\in\Sigma\cap
A$ with $z\notin\\{y^{\pm 1}\\}$. Lastly if $y\neq x^{\pm 1}$ then $z\coloneqq
x$ satisfies our requirements. Thus we have found an element $z\in\Sigma\cap
A$ with $\\{y^{\pm 1}\\}$ which by the above paragraph shows that the Cayley
graph is complete, contradicting our assumption. ∎

######  Corollary 5.3.

The only geodetic Cayley graph of a dihedral group is the complete graph.

We will now reduce the general case, of admitting an abelian subgroup of index
two, to the situation discussed in Theorem 5.2. In other words, we will prove
the following.

######  Theorem 5.4.

Let $G$ be a group. If there exists an abelian subgroup $A\leq G$ such that
$\lvert G:A\rvert=2$, then the only geodetic Cayley graph of $G$ is the
complete graph.

Our reduction will rely on a certain relationship between the structure of the
group $G$ and the parity of the order of $A$ as well as that of $Z(G)$. Part
of this relationship is captured by the following observation (with $p=2$). It
will be used again (with $p=3$) in Section 5.2.

######  Lemma 5.5.

Let $G$ be a group and $A\trianglelefteq G$ a normal abelian subgroup of prime
index $\lvert G:A\rvert=p$. If $g\in
G\mathbin{\mathchoice{\raisebox{0.3pt}{\hbox{ \leavevmode\hbox to4.1pt{\vbox
to5.8pt{\pgfpicture\makeatletter\hbox{\hskip 0.3pt\lower-0.3pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{3.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{5.2pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to4.1pt{\vbox to5.8pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{3.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{5.2pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to2.65pt{\vbox to4.25pt{\pgfpicture\makeatletter\hbox{\hskip
0.22499pt\lower-0.22499pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{{}{}}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.45pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{2.2pt}{0.0pt}\pgfsys@lineto{0.0pt}{3.8pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to1.9pt{\vbox to3.2pt{\pgfpicture\makeatletter\hbox{\hskip
0.2pt\lower-0.2pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{{}{}}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{1.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.8pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}}A$, then $g^{p}\in
Z(G)\cap A$. Moreover, if $p\nmid\left|\mathinner{A}\right|$, then there
exists some $\tilde{g}\in G\mathbin{\mathchoice{\raisebox{0.3pt}{\hbox{
\leavevmode\hbox to4.1pt{\vbox to5.8pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{3.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{5.2pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to4.1pt{\vbox to5.8pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{3.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{5.2pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to2.65pt{\vbox to4.25pt{\pgfpicture\makeatletter\hbox{\hskip
0.22499pt\lower-0.22499pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{{}{}}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.45pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{2.2pt}{0.0pt}\pgfsys@lineto{0.0pt}{3.8pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to1.9pt{\vbox to3.2pt{\pgfpicture\makeatletter\hbox{\hskip
0.2pt\lower-0.2pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{{}{}}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{1.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.8pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}}A$ with
$\tilde{g}^{p}=1$.

###### Proof.

The image of any given $g\in G\mathbin{\mathchoice{\raisebox{0.3pt}{\hbox{
\leavevmode\hbox to4.1pt{\vbox to5.8pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{3.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{5.2pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to4.1pt{\vbox to5.8pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{3.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{5.2pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to2.65pt{\vbox to4.25pt{\pgfpicture\makeatletter\hbox{\hskip
0.22499pt\lower-0.22499pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{{}{}}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.45pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{2.2pt}{0.0pt}\pgfsys@lineto{0.0pt}{3.8pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to1.9pt{\vbox to3.2pt{\pgfpicture\makeatletter\hbox{\hskip
0.2pt\lower-0.2pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{{}{}}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{1.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.8pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}}A$ in the quotient
$G/A\cong C_{p}$ has order $p$ and, as such, $g^{p}\in A$. In particular,
$g^{p}$ commutes with every element $a\in A$ and, clearly, $g^{p}$ also
commutes with $g$. We have $\langle A,g\rangle=G$ since $A\leq G$ is a maximal
subgroup (its index is prime) and $g\in
G\mathbin{\mathchoice{\raisebox{0.3pt}{\hbox{ \leavevmode\hbox to4.1pt{\vbox
to5.8pt{\pgfpicture\makeatletter\hbox{\hskip 0.3pt\lower-0.3pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{3.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{5.2pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to4.1pt{\vbox to5.8pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{3.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{5.2pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to2.65pt{\vbox to4.25pt{\pgfpicture\makeatletter\hbox{\hskip
0.22499pt\lower-0.22499pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{{}{}}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.45pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{2.2pt}{0.0pt}\pgfsys@lineto{0.0pt}{3.8pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to1.9pt{\vbox to3.2pt{\pgfpicture\makeatletter\hbox{\hskip
0.2pt\lower-0.2pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{{}{}}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{1.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.8pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}}A$. Therefore, the
element $g^{p}$ commutes with all elements of $G$, i.e., $g^{p}\in Z(G)$ as
claimed.

Now assume that $p\nmid\left|\mathinner{A}\right|$ and choose $g\in
G\mathbin{\mathchoice{\raisebox{0.3pt}{\hbox{ \leavevmode\hbox to4.1pt{\vbox
to5.8pt{\pgfpicture\makeatletter\hbox{\hskip 0.3pt\lower-0.3pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{3.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{5.2pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to4.1pt{\vbox to5.8pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{3.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{5.2pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to2.65pt{\vbox to4.25pt{\pgfpicture\makeatletter\hbox{\hskip
0.22499pt\lower-0.22499pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{{}{}}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.45pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{2.2pt}{0.0pt}\pgfsys@lineto{0.0pt}{3.8pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to1.9pt{\vbox to3.2pt{\pgfpicture\makeatletter\hbox{\hskip
0.2pt\lower-0.2pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{{}{}}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{1.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.8pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}}A$. By the above,
we have $g^{p}\in Z(G)\cap A$ and thus the cyclic subgroup $H\coloneqq\langle
g^{p}\rangle$ is contained in $Z(G)\cap A$ and, in particular, $H\leq A$. From
this we infer that $p\nmid\left|\mathinner{H}\right|$ and, as $p$ is prime,
there exists $a\in H$ with $a^{-p}=g^{p}$. The element $\tilde{g}\coloneqq ag$
has the desired properties. Indeed, $\tilde{g}=ag\in
G\mathbin{\mathchoice{\raisebox{0.3pt}{\hbox{ \leavevmode\hbox to4.1pt{\vbox
to5.8pt{\pgfpicture\makeatletter\hbox{\hskip 0.3pt\lower-0.3pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{3.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{5.2pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to4.1pt{\vbox to5.8pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{3.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{5.2pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to2.65pt{\vbox to4.25pt{\pgfpicture\makeatletter\hbox{\hskip
0.22499pt\lower-0.22499pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{{}{}}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.45pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{2.2pt}{0.0pt}\pgfsys@lineto{0.0pt}{3.8pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to1.9pt{\vbox to3.2pt{\pgfpicture\makeatletter\hbox{\hskip
0.2pt\lower-0.2pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{{}{}}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{1.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.8pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}}A$ holds since
$a\in A$ and $g\in G\mathbin{\mathchoice{\raisebox{0.3pt}{\hbox{
\leavevmode\hbox to4.1pt{\vbox to5.8pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{3.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{5.2pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to4.1pt{\vbox to5.8pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{3.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{5.2pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to2.65pt{\vbox to4.25pt{\pgfpicture\makeatletter\hbox{\hskip
0.22499pt\lower-0.22499pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{{}{}}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.45pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{2.2pt}{0.0pt}\pgfsys@lineto{0.0pt}{3.8pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to1.9pt{\vbox to3.2pt{\pgfpicture\makeatletter\hbox{\hskip
0.2pt\lower-0.2pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{{}{}}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{1.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.8pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}}A$, and
$\tilde{g}^{p}=(ag)^{p}=a^{p}g^{p}=1$ holds since $a\in Z(G)$. ∎

###### Proof of Theorem 5.4.

If $\left|\mathinner{Z(G)}\right|$ is even then Theorem 3.14 applies, so
assume $\left|\mathinner{Z(G)}\right|$ is odd. We claim that
$\left|\mathinner{A}\right|$ is odd as well. Suppose otherwise. Then there
exists some $a\in A$ with $\mathrm{ord}(a)=2$. Note that we cannot have $a\in
Z(G)$ for $\left|\mathinner{Z(G)}\right|$ is odd. Let $g\in
G\mathbin{\mathchoice{\raisebox{0.3pt}{\hbox{ \leavevmode\hbox to4.1pt{\vbox
to5.8pt{\pgfpicture\makeatletter\hbox{\hskip 0.3pt\lower-0.3pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{3.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{5.2pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to4.1pt{\vbox to5.8pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{3.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{5.2pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to2.65pt{\vbox to4.25pt{\pgfpicture\makeatletter\hbox{\hskip
0.22499pt\lower-0.22499pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{{}{}}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.45pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{2.2pt}{0.0pt}\pgfsys@lineto{0.0pt}{3.8pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to1.9pt{\vbox to3.2pt{\pgfpicture\makeatletter\hbox{\hskip
0.2pt\lower-0.2pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{{}{}}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{1.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.8pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}}A$ and consider
$\tilde{a}\coloneqq a^{g}a\in A$. Clearly, $a^{g}\neq a$ for otherwise we
would have $a\in Z(G)$. Therefore, $\tilde{a}\neq 1$. Since $\tilde{a}^{2}=1$,
we conclude that $\operatorname{ord}(\tilde{a})=2$. Moreover
$\tilde{a}^{g}=a^{gg}a^{g}=aa^{g}=a^{g}a=\tilde{a}$ since $g^{2}\in Z(G)$ by
Lemma 5.5. But then we conclude that $\tilde{a}\in Z(G)$ and, therefore,
$\left|\mathinner{Z(G)}\right|$ would have to be even.

Finally, since $\left|\mathinner{A}\right|$ is odd, there exists $t\in
G\mathbin{\mathchoice{\raisebox{0.3pt}{\hbox{ \leavevmode\hbox to4.1pt{\vbox
to5.8pt{\pgfpicture\makeatletter\hbox{\hskip 0.3pt\lower-0.3pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{3.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{5.2pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to4.1pt{\vbox to5.8pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{3.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{5.2pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to2.65pt{\vbox to4.25pt{\pgfpicture\makeatletter\hbox{\hskip
0.22499pt\lower-0.22499pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{{}{}}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.45pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{2.2pt}{0.0pt}\pgfsys@lineto{0.0pt}{3.8pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to1.9pt{\vbox to3.2pt{\pgfpicture\makeatletter\hbox{\hskip
0.2pt\lower-0.2pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{{}{}}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{1.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.8pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}}A$ with $t^{2}=1$
by Lemma 5.5. Consider the automorphism $\phi\colon A\to A$ with
$\phi(a)=a^{t}$. It satisfies $\phi^{2}=\mathrm{id}$ and $\phi\neq\mathrm{id}$
since $t^{2}=1$ and $t\not\in Z(G)$, respectively. As such, it has order two
and we can apply Theorem 5.2. ∎

###  5.2. Abelian subgroups of index three

For index 3 abelian we are able to show the conjecture holds for two cases:
first if $A$ is not normal, and second if the center of $G$ is trivial.

The general intuition is that, if a group has a lot of commuting elements (as
it does when it contains an abelian subgroup of small index), then all of its
Cayley graphs will need to have a lot of squares. However, we can only manage
to make this precise with particular hypothesis. In Section 5.4 we investigate
this further.

######  Lemma 5.6.

Let $G$ be a group. If there exists an abelian subgroup $A\leq G$ such that
$\lvert G:A\rvert=3$ and $A$ is not normal in $G$, then the only geodetic
Cayley graph of $G$ is the complete graph.

###### Proof.

Suppose that $A\leq G$ is abelian with $\lvert G:A\rvert=3$ and that $A$ is
not normal in $G$. Let $A^{g}\leq G$ be a conjugate subgroup with $A\neq
A^{g}$. Then $\langle A,A^{g}\rangle=G$ since $A$ is a maximal subgroup of $G$
(as its index is prime). Moreover, we observe that $A\cap A^{g}\subseteq Z(G)$
as every element of $A\cap A^{g}$ commutes with every element of $\langle
A,A^{g}\rangle$.

Now consider the action of $G$ by left-multiplication on the set of cosets
$G/A$. It gives rise to a homomorphism $\rho\colon G\to S_{3}$ with
$\mathrm{Ker}(\rho)=\\{h\in G\mid hgA=gA\text{ for all }g\in
G\\}=\bigcap_{g\in G}A^{g}\leq Z(G)$. The $\rho$-preimage of $C_{3}\leq S_{3}$
is an abelian subgroup $\rho^{-1}(C_{3})\leq G$, as it is an extension of
$Z(G)$ by a cyclic group. Since $\lvert G:\rho^{-1}(C_{3})\rvert=2$, the
statement now follows from Theorem 5.4. ∎

######  Remark 5.7.

In the situation described in Lemma 5.6, we have $\lvert G:Z(G)\rvert=6$. In
Corollary 4.6 we have proved an inequality relating the size of the center and
the size of the group, which in the case at hand gives us the bound $\lvert
G\rvert\leq 36$; these remaining groups are covered by our computer search.

We note that this alternative proof can be adapted, so as to cover groups with
an abelian but _not_ normal subgroup of index $5$ or $7$ (the center of such a
group has index at most $20$ or $42$ and, thus, by Corollary 4.8 we need only
consider such groups with order at most $300$ and $840$, respectively).

The other case is that $G$ contains a normal abelian subgroup of index three.
For this we can make progress when we restrict to the case the center is
trivial.

######  Theorem 5.8.

Let $G$ be a group with $Z(G)=1$. If there exists an abelian subgroup $A\leq
G$ such that $\lvert G:A\rvert=3$, then the only geodetic Cayley graph of $G$
is the complete graph.

###### Proof.

Let $G$ and $A$ be as in the hypothesis and assume that
$\mathrm{Cay}(G,\Sigma)$ is geodetic but not complete. By Lemma 5.6 we may
additionally assume that $A$ is a normal subgroup of $G$. Note that we then
have $\mathrm{ord}(\psi)=3$ for each
$\psi\in\Sigma\mathbin{\mathchoice{\raisebox{0.3pt}{\hbox{ \leavevmode\hbox
to4.1pt{\vbox to5.8pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{3.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{5.2pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to4.1pt{\vbox to5.8pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{3.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{5.2pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to2.65pt{\vbox to4.25pt{\pgfpicture\makeatletter\hbox{\hskip
0.22499pt\lower-0.22499pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{{}{}}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.45pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{2.2pt}{0.0pt}\pgfsys@lineto{0.0pt}{3.8pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to1.9pt{\vbox to3.2pt{\pgfpicture\makeatletter\hbox{\hskip
0.2pt\lower-0.2pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{{}{}}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{1.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.8pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}}A$ by Lemma 5.5
and our assumption on $Z(G)$. In order to derive a contradiction, we establish
two claims regarding the conjugacy classes of elements of $A$ with specific
geodesics, in particular, elements of the set $C\coloneqq\\{g\in
A\mid\mathrm{geod}(g)\equiv\psi_{1}\psi_{2}\text{ with
}\psi_{1},\psi_{2}\in\Sigma\mathbin{\mathchoice{\raisebox{0.3pt}{\hbox{
\leavevmode\hbox to4.1pt{\vbox to5.8pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{3.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{5.2pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to4.1pt{\vbox to5.8pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{3.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{5.2pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to2.65pt{\vbox to4.25pt{\pgfpicture\makeatletter\hbox{\hskip
0.22499pt\lower-0.22499pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{{}{}}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.45pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{2.2pt}{0.0pt}\pgfsys@lineto{0.0pt}{3.8pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to1.9pt{\vbox to3.2pt{\pgfpicture\makeatletter\hbox{\hskip
0.2pt\lower-0.2pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{{}{}}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{1.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.8pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}}A\\}$.

Claim (1). If $x\in\Sigma\cap A$, then
$x^{G}=\\{x,\psi_{1}\psi_{2},\psi_{2}\psi_{1}\\}$ for some
$\psi_{1},\psi_{2}\in\Sigma\mathbin{\mathchoice{\raisebox{0.3pt}{\hbox{
\leavevmode\hbox to4.1pt{\vbox to5.8pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{3.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{5.2pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to4.1pt{\vbox to5.8pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{3.5pt}{0.0pt}\pgfsys@lineto{0.0pt}{5.2pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to2.65pt{\vbox to4.25pt{\pgfpicture\makeatletter\hbox{\hskip
0.22499pt\lower-0.22499pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{{}{}}{{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.45pt}\pgfsys@invoke{ }\pgfsys@roundcap\pgfsys@invoke{
}{}\pgfsys@moveto{2.2pt}{0.0pt}\pgfsys@lineto{0.0pt}{3.8pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}