# Forbidden subgraphs in generating graphs
of finite groups

Andrea Lucchini  Andrea Lucchini
Università degli Studi di Padova
Dipartimento di Matematica “Tullio Levi-Civita”
Via Trieste 63, 35121 Padova, Italy
email<EMAIL_ADDRESS>and  Daniele Nemmi  Daniele Nemmi
Università degli Studi di Padova
Dipartimento di Matematica “Tullio Levi-Civita”
Via Trieste 63, 35121 Padova, Italy
email<EMAIL_ADDRESS>
###### Abstract.

Let $G$ be a $2$-generated group. The generating graph $\Gamma(G)$ is the
graph whose vertices are the elements of $G$ and where two vertices $g_{1}$
and $g_{2}$ are adjacent if $G=\langle g_{1},g_{2}\rangle.$ This graph encodes
the combinatorial structure of the distribution of generating pairs across
$G.$ In this paper we study some graph theoretic properties of $\Gamma(G)$,
with particular emphasis on those properties that can be formulated in terms
of forbidden induced subgraphs. In particular we investigate when the
generating graph $\Gamma(G)$ is a cograph (giving a complete description when
$G$ is soluble) and when it is perfect (giving a complete description when $G$
is nilpotent and proving, among the others, that $\Gamma(S_{n})$ and
$\Gamma(A_{n})$ are perfect if and only if $n\leq 4$). Finally we prove that
for a finite group $G$, the properties that $\Gamma(G)$ is split, chordal or
$C_{4}$-free are equivalent.

##  1\. Introduction

If a finite group $G$ can be generated by $d$ elements, the question of which
sets of $d$ elements of $G$ generate $G$ is nontrivial. The simplest
interesting case is when $G$ is 2-generated. One tool developed to study
generators of 2-generated finite groups is the generating graph $\Gamma(G)$ of
$G.$ This is the graph which has the elements of $G$ as vertices and an edge
between two elements $g_{1}$ and $g_{2}$ if $G$ is generated by $g_{1}$ and
$g_{2}.$ Note that the generating graph may be defined for any group, but it
only has edges if $G$ is $2$-generated.

Several strong structural results about $\Gamma(G)$ are known in the case
where $G$ is simple, and this reflects the rich group theoretic structure of
these groups. For example, if $G$ is a nonabelian simple group, then the only
isolated vertex of $\Gamma(G)$ is the identity [12] and the graph $\Delta(G)$
obtained by removing the isolated vertex is connected with diameter two [2]
and, if $|G|$ is sufficiently large, admits a Hamiltonian cycle [3] (it is
conjectured that the condition on $|G|$ can be removed). Moreover, in recent
years there has been considerable interest in attempting to classify the
groups $G$ for which $\Gamma(G)$ shares the strong properties of the
generating graphs of simple groups. Recently it has been proved the remarkable
result that the identity is the unique isolated vertex of $\Gamma(G)$ if and
only if all proper quotients of $G$ are cyclic [4]. An open question is
whether the subgraph $\Delta(G)$ of $\Gamma(G)$ induced by the non-isolated
vertices is connected, for every finite group $G.$ The answer is positive if
$G$ is soluble [7] and in this case the diameter of $\Delta(G)$ is at most
three [15]. In [13] it is proved that when $G$ is nilpotent, then $\Delta(G)$
is maximally connected.

A number of important graph classes, can be defined either structurally or in
terms of forbidden induced subgraphs. The aim of this paper is to investigate
some properties of the forbidden subgraphs of the generating graph.

A perfect graph is a graph in which the chromatic number of every induced
subgraph equals the order of the largest clique of that subgraph (clique
number). A hole in a graph $\Gamma$ is an induced subgraph of $\Gamma$
isomorphic to a chordless cycle of length at least 4. An antihole is an
induced subgraph $\Delta$ of $\Gamma$, such that $\overline{\Delta}$ is a hole
of the complement graph $\overline{\Gamma}$. A hole (resp. an antihole) is odd
or even according to the number of its vertices. The strong perfect graph
theorem is a forbidden graph characterization of the perfect graphs as being
exactly the graphs that have neither odd holes nor odd antiholes. It was
conjectured by Claude Berge in 1961. A proof by Maria Chudnovsky, Neil
Robertson, Paul Seymour and Robin Thomas was announced in 2002 and published
by them in 2006 [6]. Motivated by the strong perfect graph theorem we analyze
the existence of $m$-holes or $m$-antiholes in the generating graph of a
finite group $G.$ The first result that can be proved with this approach is a
complete characterization of the 2-generated finite nilpotent groups with a
perfect generating graph.

######  Theorem 1.

Let $G$ be a finite 2-generated nilpotent group. Then $\Gamma(G)$ is perfect
if and only if the index of the Frattini subgroup is the product of at most 4
primes.

In general the condition on the number of prime divisors of the index of the
Frattini subgroup is neither necessary nor sufficient to ensure that the
generating graph is perfect, as it follows for example from the study of the
generating graph of dihedral groups.

######  Theorem 2.

Let $D_{n}$ be the dihedral group of order $2n$ and degree $n.$ Then
$\Gamma(D_{n})$ is perfect if and only if one of the following occurs:

  1. (1)

$n$ is even;

  2. (2)

$n$ is odd, divisible by at most two distinct primes.

An interesting and surprising consequence of Theorem 2 is that if $G$ is a
2-generated finite group and $N$ is a normal subgroup of $G$, then the fact
that $\Gamma(G)$ is perfect, does not imply that $\Gamma(G/N)$ is also
perfect. For example let $m=p_{1}\cdot p_{2}\cdot p_{3}$ be the product of
three distinct primes and let $G=D_{2m}$ be the dihedral group of order $4m.$
By Theorem 2, $\Gamma(G)$ is perfect, however $G$ has a normal subgroup $N$ of
order 2 such that $G/N\cong D_{m}$ and, again by Theorem 2, $\Gamma(G/N)$ is
not perfect.

We will prove (see Theorem 40) that the alternating group $A_{5}$ is the
smallest 2-generated finite group whose generating graph is not perfect.
Moreover:

######  Theorem 3.

$\Gamma(A_{n})$ and $\Gamma(S_{n})$ are perfect if and only if $n<5$.

The behaviour of the generating graph of the alternating groups suggest the
following conjecture.

######  Conjecture 1.

If $G$ is a finite non-abelian simple group, then $\Gamma(G)$ is not perfect.

Indeed, the proof of Theorem 3 shows that if $n\geq 5$ then $\Gamma(A_{n})$
and $\Gamma(S_{n})$ contain a 5-hole, so we may also formulate a stronger
conjecture.

######  Conjecture 2.

If $G$ is a finite non-abelian simple group, then there exists a subset $X$ of
$G$ such that the subgraph of $\Gamma(G)$ induced by $X$ is a 5-hole.

With the use of GAP [9], we have checked the existence of a $5$-hole in
$\Gamma(G)$, if $G$ is the Tits group or one of the sporadic simple groups
with the exception of the Janko group $J_{4}$, the Thompson group, the Lyons
group, the Baby Monster group and the Monster group. Moreover Conjecture 2 is
true when $G\cong\operatorname{PSL}_{2}(q)$, $G\cong{{}^{2}B}_{2}(q)$ or
$G\cong{{}^{2}G}_{2}(q)$ (see subsection 3.5).

A path graph is a graph whose vertices can be listed in the order
$v_{1},v_{2},\dots,v_{n}$ such that the edges are $\\{v_{i},v_{i+1}\\}$ where
$i=1,2,\dots,n-1.$ A path graph with $n$-vertices is usually denoted by
$P_{n}.$ A graph $\Gamma$ is called a cograph if $\Gamma$ has no induced
subgraph isomorphic to the four-vertex path $P_{4}.$ Several alternative
characterizations of cographs can be given: a cograph is a graph all of whose
induced subgraphs have the property that any maximal clique intersects any
maximal independent set in a single vertex; a cograph is a graph in which
every nontrivial induced subgraph has at least two vertices with the same
neighbourhoods; a cograph is a graph in which every connected induced subgraph
has a disconnected complement; a cograph is a graph all of whose connected
induced subgraphs have diameter at most 2. We will prove that if $N$ is a
normal subgroup of a 2-generated finite group $G$ and $\Gamma(G/N)$ contains
an induced subgraph isomorphic to $P_{n}$, then so does $\Gamma(G)$ (see Lemma
10). Thus, unlike the property that the generating graph is perfect, the
property that $\Gamma(G)$ is a cograph is inherited by the epimorphic images
of $G.$ This is a considerable advantage in the study of groups whose
generating graph is a cograph and allows to obtain quite general results. For
example we can completely characterize the 2-generating finite soluble group
whose generating graph is a cograph.

######  Theorem 4.

Let $G$ be a 2-generated finite soluble group. Then $\Gamma(G)$ is a cograph
if and only if one of the following occurs.

  1. (1)

$G$ is cyclic, and the order of $G$ is divisible by at most two different
prime numbers.

  2. (2)

$G$ is a $p$-group.

  3. (3)

$G/\operatorname{Frat}(G)\cong V\rtimes\langle x\rangle$ where $x$ has prime
order and $V$ is a faithful irreducible $\langle x\rangle$-module.

Moreover we will prove the following theorems.

######  Theorem 5.

Let $G$ be a finite group and assume that the identity element is the unique
isolated vertex of $\Gamma(G).$ If $\Gamma(G)$ is a cograph, then $G$ is
soluble.

######  Theorem 6.

Let $G$ be a 2-generated finite group. If $\Gamma(G)$ is a cograph and $N$ is
a maximal normal subgroup of $G,$ then $G/N$ is abelian.

######  Corollary 7.

Let $G$ be a non-trivial 2-generated finite group. If $G$ is perfect, then
$\Gamma(G)$ is not a cograph.

The previous result suggests the following stronger conjecture.

######  Conjecture 3.

Let $G$ be a 2-generated finite group. If $\Gamma(G)$ is a cograph, then $G$
is soluble.

A graph is chordal if it contains no induced cycle of length greater then 3\.
A graph is called split if its vertex set is the disjoint union of two subsets
$A$ and $B$ so that $A$ induces a complete graph and $B$ induces an empty
graph. In the final part of the paper, we will prove the following result.

######  Theorem 8.

Let $G$ be a 2-generated finite group. Then the following conditions are
equivalent.

  1. (1)

$\Gamma(G)$ is split.

  2. (2)

$\Gamma(G)$ is chordal.

  3. (3)

$\Gamma(G)$ is $C_{4}$-free.

  4. (4)

Either $G$ is a cyclic $p$-group or $|G|=2p$ for some prime $p.$

##  2\. Cographs

Our first result is that if $\Gamma(G)$ is a cograph, then $\Gamma(G/N)$ is
also a cograph, for every normal subgroup $N$ of $G.$ In order to prove a more
general statement which implies the previous sentence, we need to recall an
auxiliary result, which generalizes an argument due to Gaschütz [10]. Given a
subset $X$ of a finite group $G,$ we will denote by $d_{X}(G)$ the smallest
cardinality of a set of elements of $G$ generating $G$ together with the
elements of $X.$ In the particular case when $X=\varnothing$,
$d_{\varnothing}(G)=d(G)$ is the smallest cardinality of a generating set of
$G.$

######  Lemma 9.

[7, Lemma 6] Let $X$ be a subset of $G$ and $N$ a normal subgroup of $G$ and
suppose that $\langle g_{1},\dots,g_{r},X,N\rangle=G.$ If $r\geq d_{X}(G),$ we
can find $n_{1},\dots,n_{r}\in N$ so that $\langle
g_{1}n_{1},\dots,g_{r}n_{r},X\rangle=G.$

######  Lemma 10.

Let $G$ be a 2-generated finite group and $N$ a normal subgroup of $G$ and let
$t\in\mathbb{N}$ with $t\geq 2.$ If $\Gamma(G/N)$ contains an induced subgraph
isomorphic to $P_{t}$, then so does $\Gamma(G).$

###### Proof.

Assume that $(a_{1}N,a_{2}N,\dots,a_{t}N)$ is a $t$-vertex path in
$\Gamma(G/N).$ By Lemma 9 there exist $n_{1},n_{2}\in N$ such that $\langle
a_{1}n_{1},a_{2}n_{2}\rangle=G.$ In particular $d_{\\{a_{2}n_{2}\\}}(G)\leq
1,$ so, again by Lemma 9, if $t\geq 3$ then there exists $n_{3}\in N$ such
that $\langle a_{2}n_{2},a_{3}n_{3}\rangle=G.$ By repeating this argument, we
can find $n_{1},\dots,n_{t}\in N$ such that $\langle
a_{i}n_{i},a_{i+1}n_{i+1}\rangle=G$ for $1\leq i\leq t-1.$ If
$(r,s)\neq(i,i+1)$ for some $i\in\\{1,\dots,t-1\\}$, then $\langle
a_{r},a_{s}\rangle N\neq G,$ and consequently $\langle
a_{r}n_{r},a_{s}n_{s}\rangle\neq G.$ So $(a_{1}n_{1},\dots,a_{t}n_{t})$ is a
$t$-vertex path in $\Gamma(G).$ ∎

###### Proof of Theorem 5.

This can be proved with the same argument used by Cameron in [5, Theorem 8.8].
Let $\Delta(G)$ be the subgraph of $\Gamma(G)$ obtained by deleting the
identity element. By [4, Theorem 1] the graph $\Delta(G)$ is connected. The
join graph of $G$ is the graph whose vertices are the non-trivial proper
subgroups of $G$ and in which two vertices $H$ and $K$ are adjacent if and
only if $H\cap K\neq 1.$ By [18] if $G$ is not soluble, then this graph is
connected. It can be easily seen that this implies that the complement graph
$\overline{\Delta(G)}$ is connected. Since the graph complement of a connected
cograph is disconnected, it follows that $\Delta(G)$ (and consequently
$\Gamma(G)$) is not a cograph when $G$ is not soluble. ∎

###### Proof of Theorem 6.

If follows immediately combining Lemma 10 and Theorem 5. ∎

######  Lemma 11.

Let $G$ be a 2-generated finite nilpotent group. If $\Gamma(G)$ is a cograph,
then $|G/\operatorname{Frat}(G)|$ is the product of at most two primes.

###### Proof.

Assume that $|G/\operatorname{Frat}(G)|$ is divisible by $p_{1}p_{2}p_{3}$,
with $p_{1},p_{2},p_{3}$ prime numbers. Since $d(G)\leq 2,$ it cannot be
$p_{1}=p_{2}=p_{3},$ so we may assume $p_{3}\notin\\{p_{1},p_{2}\\}.$ Consider
$X=\langle x_{1}\rangle\times\langle x_{2}\rangle\times\langle x_{3}\rangle$
with $|x_{i}|=p_{i}$ for $1\leq i\leq 3.$ It can be easily checked that
$(x_{1},1,1),(1,x_{2},x_{3}),$ $(x_{1},1,x_{3}),$ $(1,x_{2},1)$ is a four-
vertex path in $\Gamma(X).$ Since $X$ is an epimorphic image of $G,$ Lemma 10
would imply that $\Gamma(G)$ is not a cograph. ∎

######  Lemma 12.

Let $H$ be a 2-generated finite soluble group and $V$ a non-trivial
irreducible $H$-module. Assume that there exist $a,b\in H$ such that

  1. (1)

$H=\langle a,b\rangle$;

  2. (2)

$H\neq\langle a\rangle,H\neq\langle b\rangle;$

  3. (3)

$a\notin C_{H}(V),b\notin C_{H}(V).$

Consider the semidirect product $G=V\rtimes H.$ If no complemented chief
factor of $H$ is $H$-isomorphic to $V$, then $\Gamma(G)$ contains a subgraph
isomorphic to the four-vertex path $P_{4}.$

###### Proof.

Let $|V|=p^{t},$ with $p$ a prime. Define

$\Omega_{a}=\\{v\in V\mid\langle a,bv\rangle=G\\},\quad\Omega_{b}=\\{v\in
V\mid\langle av,b\rangle=G\\}.$

Assume $v\notin\Omega_{a}.$ Then $\langle a,bv\rangle$ is a complement of $V$
in $G$. The fact that no complemented chief factor of $H$ is $H$-isomorphic to
$V$ ensures that all the complements of $V$ in $G$ are conjugated (see [11,
Satz 3]), so there exists $w\in V$ such that $(a,bv)=(a^{w},b^{w}).$ In
particular $w\in C_{V}(a)$ and $v=[b,w].$ This implies
$|V\setminus\Omega_{a}|\leq|[b,C_{V}(a)]|\leq|C_{V}(a)|.$ Since we are
assuming $C_{V}(a)<V$, we deduce

(2.1) $|\Omega_{a}|\geq|V|-|C_{V}(a)|\geq p^{t}-p^{t-1}.$

For the same reason

(2.2) $|\Omega_{b}|\geq|V|-|C_{V}(b)|\geq p^{t}-p^{t-1}.$

Let $\Omega=\\{(v_{1},v_{2})\in V^{2}\mid\langle av_{1},bv_{2}\rangle=G\\}.$
The number of pairs $(v_{1},v_{2})$ in $V^{2}\setminus\Omega$ coincides with
the number of complements of $V$ in $G$, so

(2.3) $|\Omega|=|V^{2}|-|V|.$

If $(v_{1},v_{2})\in\Omega\cap(\Omega_{b}\times\Omega_{a})$ then
$(a,bv_{2},av_{1},b)$ is a four-vertex path in $\Gamma(G).$ In particular, if
$|\Omega_{a}\times\Omega_{b}|+|\Omega|>|V|^{2},$ then
$(\Omega_{a}\times\Omega_{b})\cap\Omega\neq\varnothing,$ and $G$ contains
$P_{4}$. So we may assume

(2.4) $|\Omega_{a}||\Omega_{b}|\leq|V^{2}|-|\Omega|=|V|.$

In particular it follows from (2.1), (2.2) and (2.3), that
$(p^{t}-p^{t-1})^{2}\leq p^{t},$ i.e.

(2.5) $p^{t}\leq\left(\frac{p}{p-1}\right)^{2}.$

This implies $p=2$ and $t=2$, i.e. $V\cong C_{2}\times C_{2}$. We have two
possibilities:

a) $H/C_{H}(V)\cong\operatorname{GL}(2,2)\cong\operatorname{Sym}(3)$. In this
case $G/C_{H}(V)\cong\operatorname{Sym}(4).$ Since
$((1,2),(2,3,4),(1,4),(1,2,3))$ is a four-vertex path in
$\operatorname{Sym}(4),$ the conclusion follows from Lemma 10.

b) $H/C_{H}(V)\cong C_{3}.$ In this case $C_{V}(a)=C_{V}(b)=\\{0\\}$, but
then, by (2.1) and (2.2), $|\Omega_{a}|,|\Omega_{b}|\geq 3$, in contradiction
with (2.4). ∎

######  Lemma 13.

Let $G$ be a non-nilpotent 2-generated finite soluble group. If $\Gamma(G)$ is
a cograph, then $G/\operatorname{Frat}(G)\cong N\rtimes H,$ where $N$ is a
faithful irreducible $H$-module and $H$ is cyclic of prime order.

###### Proof.

Assume that $\Gamma(G)$ is a cograph. Then also
$\Gamma(G/\operatorname{Frat}(G))$ is a cograph. Moreover
$G/\operatorname{Frat}(G)$ is not nilpotent (otherwise $G$ would be nilpotent)
so it is not restrictive to assume $\operatorname{Frat}(G)=1.$ Since $G$ is
not nilpotent, there exists a minimal normal subgroup of $G$, say $N$, which
is not central in $G$. Set $H=G/C_{G}(N).$ Then $N$ is a faithful irreducible
$H$-module and the semidirect product $N\rtimes H$ is an epimorphic image of
$G.$ By Lemma 10, $\Gamma(N\rtimes H)$ is a cograph, so it follows from Lemma
12 that $H$ is a cyclic group and consequently
$\dim_{\operatorname{End}_{H}(N)}N=1$. Let $K$ be a complement of $N$ in $G.$
Since $G$ is 2-generated and $\dim_{\operatorname{End}_{H}(N)}N=1$, it follows
from [10, Satz 4] that no complemented chief factor of $K$ is $K$-isomorphic
to $N$. Since $G/C_{G}(N)$ is cyclic, there exists $x\in K$ such that
$K=\langle x,C_{K}(N)\rangle.$ Moreover, since $K$ is 2-generated, by Lemma 9
there exist $c_{1},c_{2}\in C_{K}(N)$ such that $\langle
xc_{1},xc_{2}\rangle=K$. If $K$ is not cyclic, then the two elements
$a=xc_{1}$ and $b=xc_{2}$ satisfy the assumptions of Lemma 12. But this would
imply that $G$ is not a cograph, a contradiction. With a similar argument we
can prove that $K/C_{K}(N)$ is a $p$-group. Indeed assume $|K/C_{K}(N)|=rs$
with $r,s\geq 2$ and $(r,s)=1.$ There exist $y_{1},y_{2}\in K$ such that
$\langle y_{1},y_{2}\rangle=K$, $|y_{1}C_{K}(N)|=r$ and $|y_{2}C_{K}(N)|=s.$
We take $y_{1},y_{2}$ in the role of $a,b$ in Lemma 12 and we deduce that $G$
is not a cograph. So we may assume $K=\langle xy\rangle$ where $|x|$ is a
$p$-power, $y\in C_{K}(N)$ and $(|y|,p)=1.$ If $y\neq 1,$ then, for any $1\neq
n\in N,$ $(n,xy,ny,x)$ is a four-vertex path in $\Gamma(G).$ So $y=1$ and $K$
is a cyclic $p$-group. In particular $C_{K}(N)\leq\operatorname{Frat}(K).$
However $\operatorname{Frat}(K)\cap C_{K}(N)\leq\operatorname{Frat}(G)=1,$ so
we deduce that $C_{K}(N)=1.$ We have so proved that $K=\langle x\rangle$ is
cyclic of order $p^{t}$, for some $t\in\mathbb{N}$ and $N$ is a faithful
irreducible $K$-module. In particular $K$ acts fixed-point-freely on $N$.
Choose $1\neq n\in N.$ Then $K$ and $K^{n}$ are two maximal subgroups of $G$
with trivial intersection. If $t>1,$ then $(x^{p},x^{n},x,(x^{n})^{p})$ is a
four-vertex path in $\Gamma(G)$. Since $\Gamma(G)$ is a cograph we conclude
$t=1.$ ∎

###### Proof of Theorem 4.

Assume that $\Gamma(G)$ is a cograph. If $G$ is nilpotent then, by Lemma 11,
$G/\operatorname{Frat}(G)$ is either a $p$-group or a cyclic group of order
$p_{1}p_{2}$, where $p_{1}$ and $p_{2}$ are two different primes. In the first
case $G$ is a $p$-group, in the second $G$ is a cyclic group and $p_{1},p_{2}$
are the only prime divisors of $|G|.$ If $G$ is not nilpotent, then, by Lemma
13, $G/\operatorname{Frat}(G)\cong V\rtimes\langle x\rangle$ where $x$ has
prime order and $V$ is a faithful irreducible $\langle x\rangle$-module.

Conversely we have to prove that if $G$ satisfies (1), (2) or (3), then
$\Gamma(G)$ is a cograph. If $(g_{1},g_{2},g_{3},g_{4})$ is a four-vertex path
in $\Gamma(G)$, then either $(g_{1}\operatorname{Frat}(G),$
$g_{2}\operatorname{Frat}(G),g_{3}\operatorname{Frat}(G),g_{4}\operatorname{Frat}(G))$
is a four-vertex path in $\Gamma(G/\operatorname{Frat}(G))$ or there exist
$1\leq i<j\leq 4$ with
$g_{i}\operatorname{Frat}(G)=g_{j}\operatorname{Frat}(G).$ However the second
possibility cannot occur, indeed there exists
$k\in\\{1,2,3,4\\}\setminus\\{i,j\\}$ such that $g_{k}$ is adjacent to $g_{j}$
but not to $g_{i}.$ This implies $G=\langle g_{k},g_{j}\rangle=\langle
g_{k},g_{j},\operatorname{Frat}(G)\rangle=\langle
g_{k},g_{i},\operatorname{Frat}(G)\rangle<G,$ a contradiction. Therefore it
suffices to prove that in our hypotheses and under the additional assumption
$\operatorname{Frat}(G)=1,$ the generating graph $\Gamma(G)$ is a cograph.
Assume by contradiction that $(g_{1},g_{2},g_{3},g_{4})$ is a four-vertex path
in $\Gamma(G)$. We have the following possibilities.

a) $G\cong C_{p}.$ There exists $i\in\\{1,2,3,4\\}$ such that $|g_{i}|=p,$ but
then $g_{i}$ is adjacent to $g_{j}$ for any $j\neq i,$ a contradiction.

b) $G\cong C_{p}\times C_{p}.$ In this case
$|g_{1}|=|g_{2}|=|g_{3}|=|g_{4}|=p.$ Since $g_{1}$ and $g_{3}$ are not
adjacent in $\Gamma(G),$ $\langle g_{1}\rangle=\langle g_{3}\rangle.$
Moreover, since $g_{3}$ and $g_{4}$ are adjacent $\Gamma(G),$ $\langle
g_{3}\rangle\neq\langle g_{4}\rangle.$ But then $\langle
g_{1}\rangle\neq\langle g_{4}\rangle$ and $g_{1}$ and $g_{4}$ are adjacent in
$\Gamma(G),$ a contradiction.

c) $G\cong C_{p_{1}}\times C_{p_{2}},$ with $p_{1}\neq p_{2}.$ There is no
$i\in\\{1,2,3,4\\}$ such that $|g_{i}|=p_{1}p_{2},$ since this would imply
$g_{i}$ adjacent to $g_{j}$ for any $j\neq i.$ It is not restrictive to assume
$|g_{1}|=p_{1}.$ This would imply $|g_{2}|=p_{2},|g_{3}|=p_{1},|g_{4}|=p_{2}$,
and consequently that $g_{1}$ and $g_{4}$ are adjacent, a contradiction.

d) $G/\operatorname{Frat}(G)\cong V\rtimes\langle x\rangle$ where $x$ has
order $p$ and $V$ is a faithful irreducible $\langle x\rangle$-module. There
exists a prime $q\neq p$ such that $V$ is an elementary abelian $q$-group and
a non-trivial element $g$ of $G$ has either order $p$ or order $q.$ Assume
that $|g_{1}|=p.$ Then $\langle g_{1}\rangle$ is the unique maximal subgroup
of $G$ containing $g_{1}.$ Since $g_{3}$ and $g_{4}$ are not adjacent to
$g_{1},$ we must have $g_{3},g_{4}\in\langle g_{1}\rangle$, but then
$g_{3},g_{4}$ are not adjacent in $\Gamma(G).$ So $|g_{1}|=q.$ For the same
reason $|g_{4}|=q$ and consequently $|g_{2}|=|g_{3}|=p.$ But this would imply
that $g_{2}$ and $g_{4}$ are adjacent. ∎

##  3\. Perfect graphs

In the following, we will denote with $Y$ the following graph:

$x_{2}$$x_{1}$$x_{3}$$x_{4}$

######  Theorem 14.

[16, Theorem 3.2] The tensor product $\Gamma_{1}\wedge\Gamma_{2}$ is perfect
if and only if either

  * •

$\Gamma_{1}$ or $\Gamma_{2}$ is bipartite, or

  * •

both $\Gamma_{1}$ or $\Gamma_{2}$ do not contain and odd $n$-hole with $n\geq
5,$ or $Y$ as an induced subgraph.

######  Remark 15.

Let $\Gamma_{1}\cong Y$ be a graph with vertex-set
$\\{x_{1},x_{2},x_{3},x_{4}\\}$ and $\Gamma_{2}\cong K_{3}$ be a complete
graph with vertex-set $\\{y_{1},y_{2},y_{3}\\}.$ Then

$((x_{1},y_{1}),(x_{2},y_{3}),(x_{3},y_{1}),(x_{4},y_{2}),(x_{3},y_{3}))$

is a 5-hole in the tensor product $\Gamma_{1}\wedge\Gamma_{2}.$

######  Lemma 16.

Let $\operatorname{Frat}(G)$ be the Frattini subgroup of a finite group $G.$
Then $\Gamma(G)$ is perfect if and only if $\Gamma(G/\operatorname{Frat}(G))$
is perfect.

###### Proof.

By the strong graph perfect theorem, it suffices to prove that, when $m\geq
5,$ $\Gamma(G)$ contains an $m$-hole or an $m$-antihole if and only if so does
$\Gamma(G/\operatorname{Frat}(G)).$ Since $\langle
g_{1}\operatorname{Frat}(G),g_{2}\operatorname{Frat}(G)\rangle=G/\operatorname{Frat}(G)$
if and only if $\langle g_{1},g_{2}\rangle=G,$ if the subset
$\\{x_{1}\operatorname{Frat}(G),\dots,x_{m}\operatorname{Frat}(G)\\}$ induces
an $m$-hole or an $m$-antihole in $\Gamma(G/\operatorname{Frat}(G))$, then so
does $\\{x_{1},\dots,x_{m}\\}$ in $\Gamma(G).$ Conversely, assume that
$\\{x_{1},\dots,x_{m}\\}$ induces an $m$-hole or an $m$-antihole in
$\Gamma(G).$ If $1\leq i<j\leq m,$ then there exists
$k\in\\{1,\dots,m\\}\setminus\\{i,j\\}$ such that $x_{k}$ is adjacent to
$x_{i}$ but not to $x_{j}$, in particular $x_{i}\operatorname{Frat}(G)\neq
x_{j}\operatorname{Frat}(G)$ and
$\\{x_{1}\operatorname{Frat}(G),\dots,x_{m}\operatorname{Frat}(G)\\}$ induces
an $m$-hole or an $m$-antihole in $\Gamma(G/\operatorname{Frat}(G)).$ ∎

Let $I_{n}=\\{1,\dots,n\\}$ and consider the graph $\Delta_{n}$ whose vertices
are the subsets of $I_{n}$ and where $J_{1}$ and $J_{2}$ are adjacent if and
only if $J_{1}\cup J_{2}=I_{n}.$

######  Lemma 17.

The graph $\Delta_{n}$ is perfect if and only if $n\leq 4.$

###### Proof.

If $n\geq 5,$ then $(\\{1,2,4,6,\dots,n\\},\\{1,3,5,6,\dots,n\\},$
$\\{2,4,5,6,\dots,n\\},$$\\{1,3,4,6,\dots,n\\},$ $\\{2,3,5,6,\dots,n\\})$ is a
5-hole in $\Delta_{n}$ so $\Delta_{n}$ is not perfect. We may assume $n\leq
4.$ Let $m\geq 5$ be an odd integer and assume that $X$ is a subset of the
vertex-set of $\Delta_{n}$ inducing an $m$-hole or an $m$-antihole. Clearly
$I_{n}\notin X.$ As a consequence, $\varnothing\notin X.$ Moreover if
$\\{i\\}$ is a singleton, then $I_{n}\setminus\\{i\\}$ is the unique proper
subset of $I_{n}$ adjacent to $\\{i\\}$, so $\\{i\\}\notin X$. So we have at
most $2^{n}-n-2$ possible choices for an element of $X$. This implies that
$n=4$ and $X$ consists of sets of cardinality 2 or 3. Since $I_{4}$ contains
only four subsets of cardinality 3, it is not restrictive to assume $(1,2)\in
X.$ Note that a subset of cardinality 3 is adjacent to all the other subsets
of cardinality 3. So if $X$ induces an $m$-hole, then $X$ contains at most 2
(adjacent) subsets of cardinality 3. This implies that $X$ contains at least 3
subsets of cardinality 2, inducing a 3-vertex path. But this is impossible
since a subset of cardinality 2 is adjacent to only one subset of cardinality
2. If $X$ induces an $m$-antihole, then it contains at least one subset of
cardinality 2, say $Y$, and this must be adjacent to other $m-3$ elements of
$X$. However there are is a unique subset of cardinality 2 and two subsets of
cardinality 3 adjacent to $Y$, hence $m-3\leq 3.$ But this implies $m=5$ and
we may exclude this possibility since a $5$-antihole is isomorphic to a
$5$-hole. ∎

######  Lemma 18.

Let $g\in G$ be an element which is contained in a unique maximal subgroup of
$G$. Then $g$ cannot be the vertex of an $m$-hole or $m$-antihole in
$\Gamma(G)$ with $m\geq 5$.

###### Proof.

Let $M\leq G$ be the unique maximal subgroup containing $g$.

  * •

Let $(g,a_{2},\dots,a_{m})$ be an $m$-hole. We have $g\nsim a_{3},a_{4}$,
which implies $a_{3},a_{4}\in M$, so they cannot be adjacent in $\Gamma(G),$ a
contradiction.

  * •

Let $(g,a_{2},\dots,a_{m})$ be an $m$-antihole. We have $g\nsim a_{2},a_{m}$,
which implies $a_{2},a_{m}\in M$, so they cannot be adjacent in $\Gamma(G),$ a
contradiction.∎

######  Lemma 19.

Let $m\geq 5$ and suppose $(a_{1},\dots,a_{m})$ is an $m$-hole or an
$m$-antihole in $\Gamma(G)$. If $\left\langle a_{i}\right\rangle=\left\langle
a_{j}\right\rangle$, then $i=j$.

###### Proof.

Let $i\neq j$ and $\left\langle a_{i}\right\rangle=\left\langle
a_{j}\right\rangle$. We can assume without loss of generality that $i=1$ and
$2\leq j\leq\frac{m+1}{2}$. If $(a_{1},\dots,a_{m})$ is an $m$-hole, then
$a_{m}\sim a_{1}$, and this implies $a_{m}\sim a_{j}$ and consequently
$j=m-1$. But then $m-1\leq\frac{m+1}{2}$, hence $m\leq 3$, a contradiction. If
$(a_{1},\dots,a_{m})$ is an $m$-antihole, then $a_{m}\nsim a_{1}$, and so
$a_{m}\nsim a_{j}$ and we argue as before. ∎

###  3.1. Nilpotent groups

The aim of this subsection is to prove Theorem 1. First we prove the statement
in the particular case when $G$ is cyclic.

######  Lemma 20.

Let $G$ be a finite cyclic group. Then $\Gamma(G)$ is perfect if and only if
$|G|$ is divisible by at most four different primes.

###### Proof.

By Lemma 16, we may assume $\operatorname{Frat}(G)=1$, so $|G|=p_{1}\cdots
p_{t}$ where $p_{1},\dots,p_{t}$ are distinct primes. Assume that
$(a_{1},\dots,a_{m})$ is an $m$-hole or an $m$-antihole in $\Gamma(G).$ Let
$\pi=\\{p_{1},\dots,p_{t}\\}$ and for any $i\in\\{1,\dots,t\\}$, let $\pi_{i}$
be the set of prime divisors of $|a_{i}|$. By Lemma 19, if $i\neq j$, then
$\pi_{i}\neq\pi_{j}$, moreover $a_{i}$ and $a_{j}$ are adjacent in $\Gamma(G)$
if and only if $\pi_{i}\cup\pi_{j}=\pi.$ This implies that $\Gamma(G)$ is
perfect if and only if $\Delta_{t}$ is perfect, and the conclusion follows
from Lemma 17. ∎

The proof of the general case requires some preliminary lemmas and remarks.

######  Remark 21.

Let $p$ and $q$ be two different primes. If $P=\langle a_{1},a_{2}\rangle$ is
a finite, 2-generated, non-cyclic $p$-group and $Q=\langle b_{1},b_{2}\rangle$
is a finite, 2-generated, non-cyclic $q$-group, then $\Gamma(P\times Q)$
contains an induced subgroup isomorphic to $Y:$

$(a_{1},b_{1})$$(a_{2},b_{2})$$(a_{1}a_{2},b_{1}b_{2})$$(a_{1},b_{2})$

######  Remark 22.

If $P=\langle a_{1},a_{2}\rangle$ is a finite, 2-generated, non-cyclic finite
$p$-group and $C=\langle x\rangle$ is a non-trivial finite cyclic group whose
order is not divisible by $p$, then $\Gamma(P\times C)$ contains an induced
subgroup isomorphic to $Y:$

$(a_{1},1)$$(a_{2},x)$$(a_{1}a_{2},x)$$(a_{2},1)$

######  Remark 23.

If $G$ is a 2-generated finite group of order at least 3, then $\Gamma(G)$
contains an induced subgraph isomorphic to $K_{3}.$ In particular $\Gamma(G)$
is not a bipartite graph.

###### Proof.

If $G=\langle a,b\rangle$ is not cyclic, then we can take the subgraph of
$\Gamma(G)$ induced by $\\{a,b,ab\\}.$ If $G=\langle x\rangle,$ we can take
the subgroup induced by $\\{1,x,x^{-1}\\}.$ ∎

######  Lemma 24.

Let $G$ be a 2-generated finite nilpotent group. If $\Gamma(G)$ is perfect,
then the order of $G/\operatorname{Frat}(G)$ is the product of at most four
(not necessarily distinct) primes.

###### Proof.

By Lemma 16 we may assume $\operatorname{Frat}(G)=1.$ For any prime divisor
$p$ of $|G/\operatorname{Frat}(G)|$, the Sylow $p$-subgroup of $G$ is either
cyclic of order $p$ or elementary abelian of order $p^{2}.$ If all the Sylow
subgroups of $G$ are cyclic, then $G$ is cyclic and the conclusion follows
from Lemma 20. So we may assume that $G$ contains a non-cyclic Sylow
$p$-subgroup, say $P$, of order $p^{2}.$ Let $K$ be a complement of $P$ in
$G.$ Assume, by contradiction, that $|K|$ is the product of at least three
primes. If $K$ is not cyclic, then $K=Q_{1}\times Q_{2}\times H$ where
$Q_{1},Q_{2}$ are Sylow subgroups, $Q_{1}$ is non-cyclic and $Q_{2}\neq 1.$ By
Remarks 23 and 22, $\Gamma(P\times Q_{2})$ and $\Gamma(Q_{1}\times H)$ contain
an induced subgraph isomorphic, respectively, to $Y$ and $K_{3}.$ But then we
deduce from Remark 15 that $\Gamma(G)\cong\Gamma(P\times
Q_{2})\wedge\Gamma(Q_{1}\times H)$ is not perfect. So we may assume that
$K=\langle x\rangle$ and that $|x|$ is divisible by at least three different
primes $q_{1},q_{2},q_{3}.$ Let $\Omega$ be the set of the vertices $y$ of
$\Gamma(K)$ with the property that $\langle y\rangle\neq K$ and let $\Lambda$
be the subgraph of $\Gamma(K)$ induced by $\Omega.$ Notice that the subgroup
of $\Gamma(G)$ induced by the subset $P\times\Omega$ is isomorphic with
$\Gamma(P)\wedge\Lambda$ and that
$\\{x^{q_{1}},x^{q_{2}},x^{q_{3}},x^{q_{1}q_{2}}\\}$ induces a subgraph of
$\Lambda$ isomorphic to $Y$. But then, again by Remark 15,
$\Gamma(P)\wedge\Lambda$, and consequently $\Gamma(G)$, contains a 5-hole. ∎

######  Lemma 25.

Let $G$ be a non-cyclic 2-generated finite $p$-group. Then $\Gamma(G)$ is
perfect and does not contain an induced subgroup isomorphic to $Y$.

###### Proof.

We have $G/\operatorname{Frat}(G)\cong C_{p}\times C_{p}.$ If $g$ is a non-
isolated vertex of $\Gamma(G)$, then $|g\operatorname{Frat}(G)|=p$ and
$\langle g\rangle$ is the unique maximal subgroup of $G$ containing $g.$ It
follows from Lemma 18 that $\Gamma(G)$ contains no $m$-hole or $m$-antihole
with $m\geq 5$, so it follows from the strong perfect graph theorem that
$\Gamma(G)$ is perfect. Now assume by contradiction that
$\\{g_{1},g_{2},g_{3},g_{4}\\}$ induces a subgraph of $\Gamma(G)$ isomorphic
to $Y.$ We may order these four vertices in such a way that $g_{1}$ and
$g_{2}$ are adjacent while $g_{4}$ is not adjacent neither to $g_{1}$ nor to
$g_{2}.$ The latter condition implies $\langle
g_{4}\operatorname{Frat}(G)\rangle=\langle
g_{1}\operatorname{Frat}(G)\rangle=\langle
g_{2}\operatorname{Frat}(G)\rangle,$ in contradiction with $\langle
g_{1},g_{2}\rangle=G.$ ∎

###### Proof of Theorem 1.

By Lemma 16 we may assume that $\operatorname{Frat}(G)=1.$ By Lemma 24, the
condition that $|G|$ is the product of at most 4 primes is necessary for
$\Gamma(G)$ being perfect. We have to prove that this condition is also
sufficient. By Lemma 20, we may assume that $G$ is not cyclic. This means that
$G=P\times K,$ where $P\cong C_{p}\times C_{p}$ for a suitable prime $p$ and
$K$ is a nilpotent group whose order is coprime with $p$ and is the product of
at most two primes. By Lemma 25, we may assume $K\neq 1.$

If $K$ is not cyclic, then $K\cong C_{q}\times C_{q},$ for a prime $q\neq p$
and $\Gamma(G)\cong\Gamma(P)\wedge\Gamma(Q)$ is perfect, as a consequence of
Theorem 14 and Lemma 25.

The previous argument does not work if $K=\langle g\rangle$ is cyclic. Indeed
it is no more true that $\Gamma(G)\cong\Gamma(P)\wedge\Gamma(K)$. For example,
if $P=\langle a_{1},a_{2}\rangle$, then $(a_{1},g)$ and $(a_{2},g)$ are
adjacent in $\Gamma(G)$ but not in $\Gamma(P)\wedge\Gamma(K)$. However we can
argue in the following way. Assume that $X\subseteq G$ induces an $m$-hole or
an $m$-antihole, with $m\geq 5.$ If $K=\langle g\rangle$ and $y\in P,$ then
either $(y,g)$ is an isolated vertex of $\Gamma(G)$ (when $y=1$), or
$\langle(y,g)\rangle$ is the unique maximal subgroup of $G$ containing
$(y,g).$ In both the cases, by the fact that the vertices of an hole or an
antihole are not isolated and by Lemma 18, it follows that $(y,g)\notin X.$ In
particular this excludes that $K$ has prime order (no element of $K$ could
belong to $X$), so we remain with the case when $K$ is cyclic of order $r\cdot
s$, where $r$ and $s$ are different primes. In this case consider the subgraph
$\Delta$ of $\Gamma(K)$ induced by the elements of $K$ of prime order. From
what we said above, it follows that $X$ induces an $m$-hole or $m$-antihole in
$\Gamma(G)$ if and only if it induces an $m$-hole or $m$-antihole in
$\Gamma(P)\wedge\Delta.$ This would imply that $\Gamma(P)\wedge\Delta$ is not
perfect, and consequently, by Theorem 14 and Lemma 20, that $\Delta$ contains
an induced subgraph isomorphic to $Y.$ So assume by contradiction that
$\\{g_{1},g_{2},g_{3},g_{4}\\}$ induces a subgraph of $\Delta$ isomorphic to
$Y.$ We may order these four vertices in such a way that $g_{1}$ and $g_{2}$
are adjacent while $g_{4}$ is not adjacent neither to $g_{1}$ nor to $g_{2}.$
The latter condition implies $\langle g_{4}\rangle=\langle
g_{1}\rangle=\langle g_{2}\rangle,$ in contradiction with $\langle
g_{1},g_{2}\rangle=K.$ ∎

###  3.2. The dihedral group

In this subsection we analyse when the dihedral group

$D_{n}=\left\langle\rho,\iota\mid\rho^{n}=\iota^{2}=1,\rho^{\iota}=\rho^{-1}\right\rangle$

has a perfect generating graph. We start with a preliminary lemma.

######  Lemma 26.

Let $G$ be a finite group and $N\mathrel{\unlhd}G$ such that $G/N\cong
C_{2}\times C_{2}$. Then $\Gamma(G)$ has no $m$-antihole, for $m\geq 7$.

###### Proof.

Let $a,b,c\in G$ be such that $G/N:=\\{N,aN,bN,cN\\}$. Suppose
$(a_{1},\dots,a_{m})$ is a $m$-antihole. Since $a_{1}$ and $a_{3}$ are
adjacent vertices of $\Gamma(G),$ we may assume without loss of generality
that $a_{1}N=aN$ and $a_{3}N=bN$. Since $a_{5},\dots,a_{m-1}$ are adjacent to
both $a_{1}$ and $a_{3}$, it follows that $a_{5}N,\dots,a_{m-1}N$ are all
equal to $cN$. In particular, if $m>7$, then $a_{5}N=a_{7}N$ implies
$a_{5}\nsim a_{7}$, a contraction. So we may assume $m=7$. Since $a_{4}\sim
a_{1}$, $a_{4}\sim a_{6}$, $a_{1}N=aN$ and $a_{6}N=cN$, we must have
$a_{4}N=bN$. Analogously, from $a_{2}\sim a_{4}$ and $a_{2}\sim a_{6}$ it
follows $a_{2}N=aN$. But now consider $a_{7}N:$ $a_{7}N\neq aN$ since
$a_{7}\sim a_{2}$, $a_{7}N\neq bN$ since $a_{7}\sim a_{3}$ and $a_{7}N\neq cN$
since $a_{7}\sim a_{5}$. This would imply $a_{7}\in N$, and consequently that
$a_{7}$ is an isolated vertex of $\Gamma(G),$ a contradiction. ∎

###### Proof of Theorem 2.

Let $m\geq 5$ be odd. We start with two general remarks.

$(*)$ No rotation $\rho^{i}$ can appear in an $m$-hole or $m$-antihole. Indeed
if $|\rho^{i}|<n$, then $\rho^{i}$ is an isolated vertex of $\Gamma(D_{n})$.
If $|\rho^{i}|=n$, then $\langle\rho\rangle$ is the unique maximal subgroup of
$D_{n}$ containing $\rho^{i}$ and we conclude using Lemma 18. So every
$m$-hole or $m$-antihole in $\Gamma(D_{n})$ will be assumed of the form
$(a_{1},\dots,a_{m})$ with $a_{i}=\rho^{x_{i}}\iota$ for some
$x_{i}\in\mathbb{Z}.$

$(**)$ $\left\langle\rho^{a}\iota,\rho^{b}\iota\right\rangle=D_{n}$ if and
only if $(a-b,n)=1$.

First we prove that if $n$ is odd, then (2) is a necessary condition for
$\Gamma(D_{n})$ being perfect. Suppose $n$ is odd and $n=p^{a}q^{b}r^{c}k$
with $p,q,r$ distinct primes and $k$ not divisible by them, possibly $k=1$.
Consider the elements $\alpha_{1},\dots,\alpha_{4}$, obtained solving the
following systems (existence of solutions is guaranteed by the Chinese
Reminder Theorem):

$\begin{cases}\alpha_{1}\equiv 1&\mod p\\\ \alpha_{1}\equiv b&\mod q\\\
\alpha_{1}\equiv-1&\mod r\\\ (\alpha_{1}\equiv 1&\mod
k)\end{cases}\qquad\begin{cases}\alpha_{2}\equiv-1&\mod p\\\
\alpha_{2}\equiv-1-b&\mod q\\\ \alpha_{2}\equiv c&\mod r\\\ (\alpha_{2}\equiv
1&\mod k)\end{cases}$ $\begin{cases}\alpha_{3}\equiv 1&\mod p\\\
\alpha_{3}\equiv 1&\mod q\\\ \alpha_{3}\equiv d&\mod r\\\ (\alpha_{3}\equiv
1&\mod k)\end{cases}\qquad\begin{cases}\alpha_{4}\equiv a&\mod p\\\
\alpha_{4}\equiv-1&\mod q\\\ \alpha_{4}\equiv-c-d&\mod r\\\ (\alpha_{4}\equiv
1&\mod k)\end{cases}$

where the conditions in the round brackets are considered only when $k\neq 1$,
and $a,b,c,d$ are such that

$a\not\equiv 0,-1\\!\\!\mod p,\quad b\not\equiv 0,-1\\!\\!\mod q,\quad
c,d\not\equiv 0\\!\\!\mod r,\quad c+d\not\equiv 0\\!\\!\mod r.$

It can be easily checked that
$(\iota,\rho^{\alpha_{1}}\iota,\rho^{\alpha_{1}+\alpha_{2}}\iota,\rho^{\alpha_{1}+\alpha_{2}+\alpha_{3}}\iota,\rho^{\alpha_{1}+\alpha_{2}+\alpha_{3}+\alpha_{4}}\iota)$
is a $5$-hole in $\Gamma(D_{n})$.

Now we prove that if (1) and (2) are satisfied, then $\Gamma(D_{n})$ is
perfect. We distinguish the different possibilities.

a) $n$ is even. Since $D_{n}$ has an epimorphic image isomorphic to
$C_{2}\times C_{2}$, by Lemma 26 the graph $\Gamma(D_{n})$ has no $m$-antihole
with $m\geq 7$. Suppose that $\Gamma(D_{n})$ contains an $m$-hole
$(a_{1},\dots,a_{m})$, as described in $(*).$ Since
$D_{n}=\left\langle\rho^{x_{i}}\iota,\rho^{x_{i+1}}\iota\right\rangle$ for
every $i$ (where $m+1$ is considered to be $1$), by $(**)$ we should have
$x_{i+1}-x_{i}$ odd for every $1\leq i\leq m$. Then, consider

$0=\sum_{i=1}^{m}x_{i+1}-x_{i}.$

The right hand side should be odd, because it is a sum of an odd number of odd
terms, contradiction. We cannot have $m$-holes and $m$-antiholes (a $5$-hole
is the same as a $5$-antihole), so $\Gamma(D_{n})$ is perfect.

b) $n=p^{a}$ for a certain prime $p$. Suppose that $\Gamma(D_{n})$ contains an
$m$-hole $(a_{1},\dots,a_{m})$ in $\Gamma(D_{n})$. Since $a_{1}\nsim
a_{3},a_{4}$, we should have that $x_{4}-x_{1}$ and $x_{3}-x_{1}$ are
divisible by $p$, hence their difference (i.e. $x_{4}-x_{3}$) should be
divisible by $p$ and therefore $a_{3}\nsim a_{4}$, a contradiction. Suppose
now there is a $m$-antihole $(a_{1},\dots,a_{m})$. Since $a_{2}\nsim
a_{1},a_{3}$, the prime $p$ should divide $x_{3}-x_{2}$ and $x_{2}-x_{1}$ and
so $p$ should divide their sum (i.e. $x_{3}-x_{1}$), which means $a_{1}\nsim
a_{3}$, a contradiction.

c) $n=p^{a}q^{b}$ with $p\neq q$ primes. Suppose there is an $m$-hole
$(a_{1},\dots,a_{m})$ in $\Gamma(D_{n})$. Since $a_{1}\nsim a_{3},a_{4}$, the
differences $x_{3}-x_{1}$ and $x_{4}-x_{1}$ are divisible by at least one of
$p$ or $q$. We may assume without loss of generality that $x_{3}-x_{1}$ is
divisible by $p$. Then $x_{4}-x_{1}$ is divisible by $q$, otherwise
$a_{3}\nsim a_{4}$. For an analogous reasoning $x_{4}-x_{2}$ is divisible by
$p$ and $x_{m}-x_{3}$ is divisible by $q$. From the fact the $p$ divides
$x_{4}-x_{2}$, arguing as before we deduce that if $5\leq i\leq m$, then
$x_{i}-x_{2}$ is divisible by $q$ when $i$ is odd and by $p$ when $i$ is even.
In particular $x_{m}-x_{2}$ is divisible by $q$ and since $q$ divides also
$x_{m}-x_{3}$, we have $a_{2}\nsim a_{3}$, a contradiction. Suppose now there
is an $m$-antihole $(a_{1},\dots,a_{m})$ in $\Gamma(D_{n})$. Since $a_{i}\nsim
a_{i+1}$, the difference $x_{i+1}-x_{i}$ is divisible by at least one of $p$
or $q$. We have an odd number of possible $i$, so there must be a $k$ such
that $x_{k+1}-x_{k}$ and $x_{k}-x_{k-1}$ are both divisible by the same prime,
which means that $x_{k+1}-x_{k-1}$ is also divisible by the same prime, hence
$a_{k+1}\nsim a_{k-1}$, a contradiction. ∎

###  3.3. Groups of order $p^{a}q^{b}$ and $pqr$

We have seen in the previous subsections that if $G$ is a dihedral group or a
2-generated nilpotent group and $|G|$ is divisible by at most three distinct
primes, then $\Gamma(G)$ is perfect. However there exist 2-generated finite
groups whose generating graph is not perfect, although their order is
divisible only by two distinct primes. Let $H=C_{2}^{2}$ and let $h_{1}$,
$h_{2}$, $h_{3}$ be the nontrivial elements of $H$. Let $p$ be an odd prime
number and consider $N=\langle x_{1},x_{2},x_{3}\rangle\cong C_{p}^{3}.$ We
may define an action of $H$ on $N$ by setting

$\displaystyle x_{1}^{h_{1}}=x_{1},\quad x_{1}^{h_{2}}=x_{1}^{-1},\quad
x_{1}^{h_{3}}=x_{1}^{-1},$ $\displaystyle x_{2}^{h_{1}}=x_{2}^{-1},\quad
x_{2}^{h_{2}}={x_{2}},\quad x_{2}^{h_{3}}=x_{2}^{-1},$ $\displaystyle
x_{3}^{h_{1}}=x_{3}^{-1},\quad x_{3}^{h_{2}}=x_{3}^{-1},\quad
x_{3}^{h_{3}}=x_{3}.$

Let $G$ be the semidirect product $N\rtimes H.$ It can be easily checked that

$(x_{1}h_{1},x_{2}x_{3}h_{2},x_{1}x_{3}h_{3},x_{1}^{2}x_{2}h_{2},x_{2}x_{3}h_{3})$

is a 5-hole in $\Gamma(G).$

######  Lemma 27.

Let $G$ be a 2-generated finite group and let $m$ be an odd integer, with
$m\geq 5.$ Let $X\subseteq G.$ If there exist two maximal subgroups $M_{1}$
and $M_{2}$ of $G$ such that $X\subseteq M_{1}\cup M_{2},$ then $X$ does not
induce neither an $m$-hole nor an $m$-antihole.

###### Proof.

Suppose that $(a_{1},\dots,a_{m})$ is an $m$-hole induced by $X$. We may
assume $a_{1}\in M_{1}.$ Since $G=\langle a_{i},a_{i+1}\rangle$, it follows
$a_{i}\in M_{2}\setminus M_{1}$ if $i$ is even, $a_{i}\in M_{1}\setminus
M_{2}$ if $i$ is odd. In particular, since $m$ is odd, $G=\langle
a_{1},a_{m}\rangle\leq M_{1},$ a contradiction. Now suppose that
$(a_{1},\dots,a_{m})$ is an $m$-antihole induced by $X$. Again we may assume
$a_{1}\in M_{1}.$ If $3\leq i\leq m-1,$ then $G=\langle a_{1},a_{i}\rangle$
implies $a_{i}\in M_{2}$ and therefore $m=5,$ otherwise $G=\langle
a_{3},a_{m-1}\rangle\leq M_{2}.$ We may exclude this possibility since a
$5$-antihole is isomorphic to a $5$-hole. ∎

######  Lemma 28.

Suppose that $G=\left(\langle x\rangle\times\langle
y\rangle\right)\rtimes\langle z\rangle$, with $|x|=p_{1},$ $|y|=p_{2}$,
$|z|=p_{3},$ where $p_{1},p_{2},p_{3}$ are primes. If $G$ is 2-generated, then
$\Gamma(G)$ is perfect.

###### Proof.

If $G$ is abelian, then the conclusion follows from Theorem 1. So we may
assume $x\notin Z(G).$ Let $m\geq 5$ be an odd integer and suppose that
$X\subseteq G$ induces an $m$-hole or an $m$-antihole in $\Gamma(G).$

First we claim that if $y\in Z(G)$, then $p_{2}=p_{3}.$ Indeed assume $y\in
Z(G)$ and $p_{2}\neq p_{3}$ and let $g=x^{i}y^{j}z^{k}\in G.$ If
$|y^{j}z^{k}|=p_{2}p_{3},$ then $|g|=p_{2}p_{3}$, so $\langle g\rangle$ is the
unique maximal subgroup of $G$ containing $g$ and $g\notin X$ by Lemma 18. But
then $X\subseteq M_{1}\cup M_{2},$ with $M_{1}=\langle x,z\rangle$ and
$M_{2}=\langle x,y\rangle,$ in contradiction with Lemma 27.

Our second claim is that $\langle x\rangle$ and $\langle y\rangle$ are not
$\langle z\rangle$-isomorphic. This is obvious if $p_{1}\neq p_{2}$, otherwise
it is a necessary condition for $G$ being 2-generated.

The two previous claims imply that for every $r,s,u,v\in\mathbb{Z}$, $\langle
x^{r}y^{s},x^{u}y^{v}z\rangle=G$ if and only if $x^{r},y^{s}\neq 1.$ In
particular consider $w=x^{r}y^{s}\in\langle x,y\rangle.$ If either $x^{r}=1$
or $y^{s}=1,$ then $w$ is an isolated vertex in $\Gamma(G)$. Moreover, the
fact that $\langle x\rangle$ and $\langle y\rangle$ are not $\langle
z\rangle$-isomorphic implies that $\langle x,y\rangle$ is the unique maximal
subgroup of $G$ containing $u.$ In any case, $u$ cannot be an element of $X$.

Let $(a_{1},\dots,a_{m})$ be an $m$-hole or an $m$-antihole in $\Gamma(G)$
induced by $X$. By what we have said above, it is not restrictive to assume
$a_{i}=x^{r_{i}}y^{s_{i}}z$ with $r_{i},s_{i}\in\mathbb{Z}$ and we may assume
in particular $a_{1}=z.$ Notice that $\langle
x^{r_{i}}y^{s_{i}}z,x^{r_{j}}y^{s_{j}}z\rangle=G$ if and only if
$r_{i}\not\equiv r_{j}\\!\mod p_{1}$ and $s_{i}\not\equiv s_{j}\\!\mod p_{2}.$

If $(a_{1},\dots,a_{m})$ is an $m$-hole, then $a_{1}\not\sim a_{j}$ for any
$j\in\\{3,\dots,m-1\\}$. This implies that either $a_{j}\in\langle x,z\rangle$
or $a_{j}\in\langle y,z\rangle.$ On the other hand $a_{j}\sim a_{j+1}$, so it
is not restrictive to assume $s_{3}\equiv 0\\!\mod p_{2},\ r_{4}\equiv
0\\!\mod p_{1},\dots,s_{m-2}\equiv 0\\!\mod p_{2},\ r_{m-1}\equiv 0\\!\mod
p_{1}.$ On the other hand, $a_{1}\sim a_{2}$ and $a_{1}\sim a_{m}$ implies
$r_{2},r_{m}\not\equiv 0\\!\mod p_{1}$ and $s_{2},s_{m}\not\equiv 0\\!\mod
p_{2}.$ By Lemma 19, $r_{3}\not\equiv 0\\!\mod p_{1}$ and $s_{m-1}\not\equiv
0\\!\mod p_{2}.$ Since $a_{2}\not\sim a_{m-1}$ and $a_{3}\not\sim a_{m}$, we
deduce $s_{2}\equiv s_{m-1}\\!\mod p_{2}$ and $r_{3}\equiv r_{m}\\!\mod
p_{1}.$ Since $a_{2}\sim a_{3}$ and $a_{m-1}\sim a_{m},$ it follows
$r_{2}\not\equiv r_{3}\\!\mod p_{1}$ and $s_{m-1}\not\equiv s_{m}\\!\mod
p_{2},$ but then $r_{2}\not\equiv r_{m}\\!\mod p_{1}$ and $s_{2}\not\equiv
s_{m}\\!\mod p_{2}.$ This implies $a_{2}\sim a_{m}$, a contradiction.

Now suppose that $(a_{1},\dots,a_{m})$ is an $m$-antihole. We may assume
$m\geq 7$ since a 5-antihole is isomorphic to a $5$-hole. From the conditions
$a_{1}\not\sim a_{2}$ and $a_{1}\not\sim a_{m}$ it follows that is this not
restrictive to assume $s_{2}=0$ and $r_{m}=0$. Since $a_{i}\not\sim a_{i+1}$,
it follows

$a_{1}=z,\ a_{2}=x^{r_{2}}z,\ a_{3}=x^{r_{2}}y^{s_{3}}z,\
a_{4}=x^{r_{4}}y^{s_{3}}z,\ a_{5}=x^{r_{4}}y^{s_{5}}z,\
a_{6}=x^{r_{6}}y^{s_{5}}z\dots$

In particular

$a_{m-2}=x^{r_{m-3}}y^{s_{m-2}}z,\ a_{m-1}=x^{r_{m-1}}y^{s_{m-2}}z,\
a_{m}=y^{s_{m}}z.$

From $a_{m-1}\sim a_{1},$ it follows $r_{m-1}\not\equiv 0\\!\mod p_{1}$ and
from $a_{m}\sim a_{m-2},$ it follows $s_{m}\not\equiv s_{m-2}\\!\mod p_{2}$,
however this would imply $a_{m-1}\sim a_{m},$ a contradiction. ∎

######  Proposition 29.

If $G=p_{1}p_{2}$ with $p_{1},p_{2}$ primes, then $\Gamma(G)$ is perfect.

###### Proof.

It follows immediately from Lemma 18. ∎

######  Proposition 30.

If $|G|=p_{1}p_{2}p_{3},$ where $p_{1},$ $p_{2}$ and $p_{3}$ are three
distinct primes, then $G$ is 2-generated and $\Gamma(G)$ is perfect.

###### Proof.

By [17, 10.1.10], $G$ is 2-metacyclic. We may assume that $G$ is non-abelian,
so $G=\langle x\rangle\rtimes\langle y\rangle$, with $y\neq 1$ and $C_{\langle
y\rangle}(x)=1.$ If $|x|$ is the product of two different primes, then the
conclusion follows from Lemma 28. So we may assume that $|x|=p_{1}.$ Assume
that $X$ induces an $m$-hole or an $m$-antihole in $\Gamma(G)$, where $m\geq
5$ is an odd integer. By Lemma 18, $X$ contains only elements of prime order;
moreover an element of order $p_{1}$ is adjacent in $\Gamma(G)$ only to
elements of order $p_{2}p_{3}$, so $X$ can contain only elements of order
$p_{2}$ or $p_{3}.$ On the other hand two elements of the same order $p_{2}$
or $p_{3}$ are not adjacent in $\Gamma(G)$, and it is easy to see that this
implies that $X$ cannot induce neither an $m$-hole nor an $m$-antihole. ∎

######  Proposition 31.

If $|G|=p^{2}q,$ where $p$ and $q$ are distinct primes, then $\Gamma(G)$ is
perfect.

###### Proof.

First assume that the Sylow $p$-subgroup, say $P$, of $G$ is normal. If
$P\cong C_{p}\times C_{p},$ then the conclusion follows from Lemma 28. If
$P\cong C_{p^{2}},$ then $\operatorname{Frat}(G)$ has order $p$, so
$G/\operatorname{Frat}(G)$ is perfect by Proposition 29 and consequently, by
Lemma 16, also $\Gamma(G)$ is perfect. So we may assume that the Sylow
$p$-subgroups are not normal, which implies that the Sylow $q$-subgroup, say
$Q,$ is normal. Either $G\cong(C_{p}\times C_{q})\rtimes C_{p}$ or $G\cong
C_{q}\rtimes C_{p^{2}}.$ In the first case the conclusion follows again from
Lemma 28. In the second case the only non-trivial elements of $G$ that are
contained in at least two different maximal subgroups are those of order $p,$
so, by Lemma 18, if $X\subseteq G$ induces an $m$-hole or an $m$-antihole,
with $m\geq 5$ an odd integer, then $X$ contains only elements of order $p.$
However two elements of order $p$ are not adjacent in $\Gamma(G)$, so we
reached a contradiction. ∎

###  3.4. The symmetric and alternating group

In this subsection we determine for which values of $n$, the symmetric and
alternating group of degree $n$ have perfect generating graph. In the proofs
we will need the following elementary lemmas:

######  Lemma 32.

Let $H\leq S_{n}$ be a transitive permutation group. If $\sigma\in H$ is a
$(n-1)$-cycle, then $H$ is primitive.

###### Proof.

We may assume without loss of generality that the fixed point of $\sigma$ is
$1$. Suppose $H$ is imprimitive. Let $B$ be the imprimitivity block which
contains $1$, then $B^{\sigma}=B$ since $1^{\sigma}=1$. By the imprimitivity
assumption, there exists $1\neq i\in B$. But then
$i,i^{\sigma},i^{\sigma^{2}},\dots i^{\sigma^{n-2}}$ are all distinct
elements, so $B=\\{1,\dots,n\\}$, a contradiction. ∎

######  Lemma 33.

Let $n\geq 3$ be an odd natural number and $H\leq S_{n}$ be a transitive
permutation group. If $\sigma\in H$ is a $(n-2)$-cycle, then $H$ is primitive.

###### Proof.

Suppose, without loss of generality, that the fixed points of $\sigma$ are $1$
and $2$. Suppose $H$ is imprimitive. As in the proof of the previous Lemma,
take $B$ to be the block containing $1$. Since $n$ is odd, $|B|\geq 3$, so
there is at least an element $i$ in $B\setminus\\{1,2\\}$. Arguing as in the
proof of the previous lemma, we obtain that $|B|\geq n-1$ and, since $|B|$
divides $n$, we conclude $B=\\{1,\dots,n\\}$, a contradiction. ∎

######  Theorem 34.

$\Gamma(S_{n})$ is perfect if and only if $n\leq 4$.

###### Proof.

We distinguish the different possible values of $n.$

a) $n=2.$ In this case $\Gamma(S_{2})\cong K_{2}$ is perfect.

b) $n=3$. Since $S_{3}\cong D_{3}$, it follows from Theorem 2 that
$\Gamma(S_{3})$ is perfect.

c) $n=4$. Suppose there is an $m$-hole $(a_{1},\dots,a_{m})$ in
$\Gamma(S_{4}),$ with $m\geq 5.$ Two consecutive vertices $a_{i}$ and
$a_{i+1}$ are adjacent and therefore they cannot belong both to $A_{4}$. Since
$m$ is odd, there must be two consecutive vertices which are in
$S_{4}\setminus A_{4}$. Since two elements of order $2$ do not generate the
group, one of these two vertices should be a $4$-cycle. However a $4$-cycle is
contained in a unique maximal subgroup, so we have a contradiction by Lemma
18. Suppose now that there is an $m$-antihole $(a_{1},\dots,a_{m})$ in
$\Gamma(S_{4})$, with $m\geq 7$. Since $4$-cycles cannot occur in an
$m$-antihole and elements of the Klein subgroup cannot generate with another
element, the vertices of the antihole can be only transpositions and
$3$-cycles. There are at most two $3$-cycles among the vertices of the
antihole. Indeed if we pick three elements in an $m$-antihole, at least two of
them are adjacent but two $3$-cycles do not generate $S_{4}$. So, at least
$m-2$ of the vertices of the antihole $(a_{1},\dots,a_{m})$ are
transpositions. Since two transpositions do not generate $S_{4}$, we have a
contradiction. We conclude that $\Gamma(S_{4})$ is perfect.

d) $n=5,6,7$. It can be easily checked that the following are $5$-holes in
$\Gamma(S_{n}):$

$\displaystyle\Gamma(S_{5}):$
$\displaystyle\qquad((1,2,3,4,5),(2,4),(1,2,3,5,4),(2,4,5,3),(1,2,4,5));$
$\displaystyle\Gamma(S_{6}):$
$\displaystyle\qquad((1,3,2,4),(3,4,6,5),(1,2,3,4,5),(1,3,4,6),(2,3,4,5,6));$
$\displaystyle\Gamma(S_{7}):$
$\displaystyle\qquad((1,5,4,7,2,3),(2,6,5,7,3,4),(1,2,3,4,5,7,6),(4,5),(1,2,3,4,5,6,7)).$

e) $n\geq 8$ even. In this case we claim that

$\displaystyle a_{1}=(1,\dots,n-2)$ $\displaystyle a_{2}=(3,\dots,n)$
$\displaystyle a_{3}=(1,\dots,n-1)$ $\displaystyle a_{4}=(1,3,4,n)$
$\displaystyle a_{5}=(2,\dots,n)$

is a $5$-hole in $\Gamma(S_{n})$.

Notice that $\left\langle a_{1},a_{3}\right\rangle$, $\left\langle
a_{1},a_{4}\right\rangle$, $\left\langle a_{2},a_{4}\right\rangle$,
$\left\langle a_{2},a_{5}\right\rangle$ are intransitive subgroups and
$\left\langle a_{3},a_{5}\right\rangle\leq A_{n}$, so the pairs of
corresponding vertices are not joined by an edge. Since $a_{3}$ and $a_{5}$
are $(n-1)$-cycles, the transitive subgroups $\left\langle
a_{2},a_{3}\right\rangle$, $\left\langle a_{3},a_{4}\right\rangle$,
$\left\langle a_{4},a_{5}\right\rangle$, $\left\langle
a_{5},a_{1}\right\rangle$ are also primitive by Lemma 32. Let us now prove
that also the transitive subgroup $\left\langle a_{1},a_{2}\right\rangle$ is
primitive. Let $B$ be an imprimitive block which contains $1$. Clearly
$B^{a_{2}}=B$. If $B\cap\\{3,\dots,n\\}\neq\varnothing,$ then
$\\{1,3,\dots,n\\}\subseteq B$, a contradiction. So $B=\\{1,2\\}$, but then
$B\cap B^{a_{1}}=\\{2\\}$, another contradiction. Moreover

$\displaystyle a_{1}a_{2}^{-1}$ $\displaystyle=(1,2,n,n\\!-\\!1,n\\!-\\!2)$
$\displaystyle\in\left\langle a_{1},a_{2}\right\rangle$ $\displaystyle
a_{3}a_{2}^{-1}$ $\displaystyle=(1,2,n,n\\!-\\!1)$
$\displaystyle\in\left\langle a_{2},a_{3}\right\rangle$ $\displaystyle a_{4}$
$\displaystyle=(1,3,4,n)$ $\displaystyle\in\left\langle
a_{3},a_{4}\right\rangle$ $\displaystyle a_{4}$ $\displaystyle=(1,3,4,n)$
$\displaystyle\in\left\langle a_{4},a_{5}\right\rangle$ $\displaystyle
a_{1}a_{5}^{-1}$ $\displaystyle=(1,n,n\\!-\\!1,n\\!-\\!2)$
$\displaystyle\in\left\langle a_{5},a_{1}\right\rangle$

But then, by [14, Corollary 1.3], the five subgroups $\left\langle
a_{1},a_{2}\right\rangle,$ $\left\langle a_{2},a_{3}\right\rangle,$
$\left\langle a_{3},a_{4}\right\rangle,$ $\left\langle
a_{4},a_{5}\right\rangle$ and $\left\langle a_{5},a_{1}\right\rangle$ contain
$A_{n}$. Since they contain elements outside $A_{n}$, they must be the whole
$S_{n}$, so the pairs of corresponding vertices are joined by an edge.

f) $n\geq 9$ odd. In this case we claim that

$\displaystyle a_{1}=(1,\dots,n-3)$ $\displaystyle a_{2}=(4,\dots,n)$
$\displaystyle a_{3}=(1,\dots,n-2)$ $\displaystyle
a_{4}=(1,2,4,5,n\\!-\\!1,n\\!-\\!2)$ $\displaystyle a_{5}=(3,\dots,n)$

is a $5$-hole in $\Gamma(S_{n})$.
As in the discussion of the previous case, $\left\langle
a_{1},a_{3}\right\rangle$, $\left\langle a_{1},a_{4}\right\rangle$,
$\left\langle a_{2},a_{4}\right\rangle$, $\left\langle
a_{2},a_{5}\right\rangle$ are intransitive subgroups and $\left\langle
a_{3},a_{5}\right\rangle\leq A_{n}$, so the pairs of corresponding vertices
are not joined by an edge. Since $a_{3}$ and $a_{5}$ are $(n-2)$-cycles, the
transivite subgroups $\left\langle a_{2},a_{3}\right\rangle$, $\left\langle
a_{3},a_{4}\right\rangle$, $\left\langle a_{4},a_{5}\right\rangle$,
$\left\langle a_{5},a_{1}\right\rangle$ are also primitive by Lemma 33. Let us
now prove that also the transitive subgroup $\left\langle
a_{1},a_{2}\right\rangle$ is primitive. Let $B$ be an imprimitivity block
which contains $1$, so that $B^{a_{2}}=B$. If
$B\cap\\{4,\dots,n\\}\neq\varnothing,$ then $\\{1,4,\dots,n\\}\subseteq B$, a
contradiction. Since $|B|\geq 3$, the only possibility is $B=\\{1,2,3\\}$, but
this leads to a contradiction since $B\cap B^{a_{1}}=\\{2,3\\}$. Moreover

$\displaystyle a_{1}$ $\displaystyle=(1,\dots,n-3)$
$\displaystyle\in\left\langle a_{1},a_{2}\right\rangle$ $\displaystyle
a_{3}a_{2}^{-1}$ $\displaystyle=(1,2,3,n,n\\!-\\!1,n\\!-\\!2)$
$\displaystyle\in\left\langle a_{2},a_{3}\right\rangle$ $\displaystyle a_{4}$
$\displaystyle=(1,2,4,5,n\\!-\\!1,n\\!-\\!2)$ $\displaystyle\in\left\langle
a_{3},a_{4}\right\rangle$ $\displaystyle a_{4}$
$\displaystyle=(1,2,4,5,n\\!-\\!1,n\\!-\\!2)$ $\displaystyle\in\left\langle
a_{4},a_{5}\right\rangle$ $\displaystyle a_{1}$ $\displaystyle=(1,\dots,n-3)$
$\displaystyle\in\left\langle a_{5},a_{1}\right\rangle$

and, as in the previous case, we deduce from [14, Corollary 1.3] that
$\left\langle a_{1},a_{2}\right\rangle=\left\langle
a_{2},a_{3}\right\rangle=\left\langle a_{3},a_{4}\right\rangle=\left\langle
a_{4},a_{5}\right\rangle=\left\langle a_{5},a_{1}\right\rangle=S_{n}.$ ∎

######  Theorem 35.

$\Gamma(A_{n})$ is perfect if and only if $n\leq 4$.

###### Proof.

We distinguish the different possible values of $n.$

a) $n=3.$ In this case $\Gamma(A_{3})\cong K_{3}$ is perfect.

b) $n=4$. Let $m$ be an odd positive integer, with $m\geq 5.$ In an $m$-hole
or in an $m$-antihole, at least one vertex should be a $3$-cycle, since in a
pair of generators one should be outside the Klein subgroup. However a
$3$-cycle is contained in a unique maximal subgroup, so we conclude using
Lemma 18 that there is neither an $m$-hole nor an $m$-antihole.

c) $n=6$. In this case $\Gamma(A_{6})$ contains the following $5$-hole:

$((1,2,3,4,5),(1,3)(5,6),(1,2,4,5,6),(1,4,2,3,5),(1,2,6)).\\\ $

d) $n\geq 5$ odd. In this case we claim that

$\displaystyle a_{1}=(1,2,3,6\dots,n)$ $\displaystyle a_{2}=(2,4,5,6\dots,n)$
$\displaystyle a_{3}=(1,3,5,6\dots,n)$ $\displaystyle a_{4}=(2,3,4,6\dots,n)$
$\displaystyle a_{5}=(1,4,5,6\dots,n)$

is a $5$-hole in $\Gamma(A_{n})$. The cases $n=5,7,9$ can be easily checked by
hand, so we assume $n\geq 11$. Notice that $\left\langle
a_{1},a_{3}\right\rangle$, $\left\langle a_{1},a_{4}\right\rangle$,
$\left\langle a_{2},a_{4}\right\rangle$, $\left\langle
a_{2},a_{5}\right\rangle$ and $\left\langle a_{3},a_{5}\right\rangle$ are
intransitive subgroups, so the pair of corresponding vertices are not joined
by an edge. Since $a_{1},\dots,a_{5}$ are $(n-2)$-cycles, the transitive
subgroups $\left\langle a_{1},a_{2}\right\rangle$, $\left\langle
a_{2},a_{3}\right\rangle$, $\left\langle a_{3},a_{4}\right\rangle$,
$\left\langle a_{4},a_{5}\right\rangle$ and $\left\langle
a_{5},a_{1}\right\rangle$ are also primitive from Lemma 33. Moreover

$\displaystyle a_{1}^{2}a_{2}^{-2}$ $\displaystyle=(1,3,5,2,4,n,n\\!-\\!1)$
$\displaystyle\in\left\langle a_{1},a_{2}\right\rangle$ $\displaystyle
a_{2}a_{3}^{-1}$ $\displaystyle=(1,n,2,4,3)$ $\displaystyle\in\left\langle
a_{2},a_{3}\right\rangle$ $\displaystyle a_{3}^{2}a_{4}^{-2}$
$\displaystyle=(1,5,4,2,n\\!-\\!1)$ $\displaystyle\in\left\langle
a_{3},a_{4}\right\rangle$ $\displaystyle a_{4}^{2}a_{5}^{-2}$
$\displaystyle=(1,n\\!-\\!1,2,n,3,4,5)$ $\displaystyle\in\left\langle
a_{4},a_{5}\right\rangle$ $\displaystyle a_{5}a_{1}^{-1}$
$\displaystyle=(1,4,5,3,2)$ $\displaystyle\in\left\langle
a_{5},a_{1}\right\rangle$

and we can use [14, Corollary 1.3] to conclude that $\left\langle
a_{1},a_{2}\right\rangle=\left\langle a_{2},a_{3}\right\rangle=\left\langle
a_{3},a_{4}\right\rangle=\left\langle a_{4},a_{5}\right\rangle=\left\langle
a_{5},a_{1}\right\rangle=A_{n}.$

e) $n\geq 8$ even. In this case we claim that

$\displaystyle a_{1}=(1,2,3,4,5,9\dots,n)$ $\displaystyle
a_{2}=(1,3,6,7,8,9\dots,n)$ $\displaystyle a_{3}=(2,7,8,4,5,9\dots,n)$
$\displaystyle a_{4}=(1,6,3,4,5,9\dots,n)$ $\displaystyle
a_{5}=(1,2,6,7,8,9\dots,n)$

is a $5$-hole in $\Gamma(A_{n})$. The subgroups $\left\langle
a_{1},a_{3}\right\rangle$, $\left\langle a_{1},a_{4}\right\rangle$,
$\left\langle a_{2},a_{4}\right\rangle$, $\left\langle
a_{2},a_{5}\right\rangle$ and $\left\langle a_{3},a_{5}\right\rangle$ are
intransitive, so the pair of corresponding vertices are not joined by an edge.
We prove that the transitive subgroup $\left\langle a_{1},a_{2}\right\rangle$
is primitive (a similar argument works for the subgroups $\left\langle
a_{2},a_{3}\right\rangle$, $\left\langle a_{3},a_{4}\right\rangle$,
$\left\langle a_{4},a_{5}\right\rangle$ and $\left\langle
a_{5},a_{1}\right\rangle$). Suppose it is imprimitive. Let $B$ be an
imprimitive block containing $6$, so that $B^{a_{1}}=B$. We must have
$B\subseteq\\{6,7,8\\}$, otherwise we would have
$\\{1,2,3,4,5,6,9,\dots,n\\}\subseteq B$. Moreover, since $B\cap
B^{a_{2}}=\\{7,8\\}$, $B\neq\\{6,7,8\\}$, so either $B=\\{6,7\\}$ or
$B=\\{6,8\\}$. In the first case the block which contains $8$, contains also
an element different from $6,7,8$ and we get a contradiction as before; the
same happens in the second case considering the block which contains $7$.
Since $a_{1},\dots,a_{5}$ are $(n-3)$-cycles, we can conclude, using [14,
Corollary 1.3], that $\left\langle a_{1},a_{2}\right\rangle=\left\langle
a_{2},a_{3}\right\rangle=\left\langle a_{3},a_{4}\right\rangle=\left\langle
a_{4},a_{5}\right\rangle=\left\langle a_{5},a_{1}\right\rangle=A_{n}.$ ∎

###  3.5. Other simple groups

In this subsection we prove that Conjecture 2 is true also when
$G\cong\operatorname{PSL}_{2}(q)$, $G\cong{{}^{2}B}_{2}(q)$ or
$G\cong{{}^{2}G}_{2}(q).$ We need the following elementary observation.

######  Lemma 36.

Let $G$ be a permutation group on the set $\Omega$. Let
$\omega_{1},\dots,\omega_{5}\in\Omega$ such that
$\operatorname{Stab}_{G}(\omega_{i})<G$ for $i=1,\dots,5$. Let

$\displaystyle
a\in\operatorname{Stab}_{G}(\omega_{1})\cap\operatorname{Stab}_{G}(\omega_{2}),$
$\displaystyle
b\in\operatorname{Stab}_{G}(\omega_{3})\cap\operatorname{Stab}_{G}(\omega_{4}),$
$\displaystyle
c\in\operatorname{Stab}_{G}(\omega_{5})\cap\operatorname{Stab}_{G}(\omega_{1}),$
$\displaystyle
d\in\operatorname{Stab}_{G}(\omega_{2})\cap\operatorname{Stab}_{G}(\omega_{3}),$
$\displaystyle
e\in\operatorname{Stab}_{G}(\omega_{4})\cap\operatorname{Stab}_{G}(\omega_{5}).$

If $\left\langle a,b\right\rangle=\left\langle b,c\right\rangle=\left\langle
c,d\right\rangle=\left\langle d,e\right\rangle=\left\langle
e,a\right\rangle=G$, then $(a,b,c,d,e)$ is a $5$-hole in $\Gamma(G)$.

######  Proposition 37.

Let $G=\operatorname{PSL}_{2}(q),$ with $q>3$. Then $\Gamma(G)$ contains a
5-hole.

###### Proof.

We may assume $q\notin\\{4,5,9\\},$ since
$\operatorname{PSL}_{2}(4)\cong\operatorname{PSL}_{2}(5)\cong A_{5}$ and
$\operatorname{PSL}_{2}(9)\cong A_{6}$. The group $G$ has a faithful
2-transitive action on the $q+1$ points of the 1-dimensional projective space
$\operatorname{PG}(1,q)$ over the field $\mathbb{F}_{q}$ with $q$ elements.
Let $A,B,C,D$ be four distinct points of $\operatorname{PG}(1,q)$. The
subgroups $H=\operatorname{Stab}_{G}(A)\cap\operatorname{Stab}_{G}(B)$ and
$K=\operatorname{Stab}_{G}(C)\cap\operatorname{Stab}_{G}(D)$ are cyclic of
order $u=(q-1)/(q-1,2)$. Notice that $H\neq K$, since the only element of $G$
which fixes three distinct points is the identity. The list of the maximal
subgroups of $G$ is well-known (see for example [1, Table 8.1]). In particular
if $q\notin\\{7,11\\}$, then no maximal subgroup of $G$ contains two distinct
cyclic subgroups of order $u$. This implies $G=\langle H,K\rangle$. But then
we can use Lemma 36 to conclude.

If $q=7$, then $G\leq\operatorname{Sym}(8)$ and the following is a 5-hole in
$\Gamma(G):$

$((2,3,4)(5,8,7),(1,4,5)(3,7,6),(2,7,8)(3,6,5),(1,2,4)(6,7,8),(1,2,5,7)(3,8,6,4))$

If $q=11,$ then $G\leq\operatorname{Sym}(12)$ and the following is a 5-hole in
$\Gamma(G):$

$((3,9,5,11,7)(4,10,6,12,8),(1,6,3,4,12)(2,11,9,10,7),(1,3,8,5,4)(6,7,9,12,10),$
$(2,12,11,8,3)(4,7,9,10,6),(1,9,6,7,5)(2,4,12,3,10)).\qed$

######  Proposition 38.

Let $q=2^{2n+1}$ with $n\geq 1.$ If $G={{}^{2}B}_{2}(q)$ is a Suzuki group,
then $\Gamma(G)$ contains a 5-hole.

###### Proof.

The group $G$ has a faithful 2-transitive action on an ovoid $\Omega$ in
4-dimensional symplectic geometry. Moreover the following are up to conjugacy
the maximal subgroups of $G$ (see for example [1, Theorem 7.3.3]):

  1. (1)

the stabilizer of $\omega\in\Omega$ (the Borel subgroup of order
$q^{2}(q-1)$);

  2. (2)

the dihedral group of order $2(q-1)$;

  3. (3)

$C_{q+\sqrt{2q}+1}:C_{4}$;

  4. (4)

$C_{q-\sqrt{2q}+1}:C_{4}$;

  5. (5)

${{}^{2}B}_{2}(q_{0})$, where $q=q_{0}^{r}$, $r$ is prime and $q_{0}>2$.

If $\omega_{i}$ and $\omega_{j}$ are distinct elements of $\Omega,$ then
$\operatorname{Stab}_{G}(\omega_{i})\cap\operatorname{Stab}_{G}(\omega_{j})$
is cyclic of order $q-1$. Let $x$ be a generator of this cyclic group. Let now
$\omega_{l}$ and $\omega_{k}$ in $\Omega$ such that
$\omega_{i},\omega_{j},\omega_{k},\omega_{l}$ are all distinct, and call $y$
the generator of
$\operatorname{Stab}_{G}(\omega_{k})\cap\operatorname{Stab}_{G}(\omega_{l})$.
Since the only element fixing three points is the identity, we have that
$\left\langle x\right\rangle\neq\left\langle y\right\rangle$. Consider the
subgroup $H:=\left\langle x,y\right\rangle$. If $H$ is a proper subgroup, it
is contained in a maximal subgroup. However $H$ cannot be contained in
subgroups of type $(3)$, $(4)$ and $(5)$, since they do not contain elements
of order $q-1$. Since $\left\langle x\right\rangle\neq\left\langle
y\right\rangle$ we can exclude also the fact that $H$ is contained in the
subgroups of type $(2)$, since the dihedral group contains a unique subgroup
of order $q-1$. Finally, if $H\leq\operatorname{Stab}_{G}(\omega)$, for some
$\omega\in\Omega$, at least one of $x$ and $y$ should fix three different
points, which is impossible, therefore $H=G$ and using Lemma 36 we can build a
$5$-hole. ∎

######  Proposition 39.

Let $q:=3^{2n+1}$ with $n\geq 1.$ If $G:={{}^{2}G_{2}}(q)$, then $\Gamma(G)$
contains a 5-hole.

###### Proof.

The groups $G$ has a faithful 2-transitive action on an ovoid $\Omega$ in
7-dimensional orthogonal geometry. Moreover the following are up to conjugacy
the maximal subgroups of $G$ (see for example [1, Table 8.43]):

  1. (1)

the stabilizer of $\omega\in\Omega$ (the Borel subgroup of order
$q^{3}(q-1)$);

  2. (2)

the centralizer of an involution, which is isomorphic to
$C_{2}\times\operatorname{PSL}_{2}(q)$;

  3. (3)

the normalizer of a four-group, which is isomorphic to $(2^{2}\times
D_{(q+1)/4}):3;$

  4. (4)

$C_{q+\sqrt{3q}+1}:C_{6}$;

  5. (5)

$C_{q-\sqrt{3q}+1}:C_{6}$;

  6. (6)

${{}^{2}G}_{2}(q_{0})$, where $q=q_{0}^{r}$ and $r$ prime.

The intersection of two different point-stabilizers is cyclic with order
$q-1$. Moreover any involution $t$ in $G$ fixes precisely $q+1$ points in
$\Omega$, and the set of these $q+1$ elements is called the block of $t.$ Any
two blocks can intersect in at most 1 point and any two points are pointwise
fixed by a unique involution. Choose $\omega_{1},\dots,\omega_{5}\in\Omega$
all distinct in the following way: $\omega_{1}$, $\omega_{2}$ and $\omega_{3}$
are chosen randomly and let $\Omega_{i,j}$ be the unique block which contains
$\omega_{i}$ and $\omega_{j}$. Since $|\Omega|=q^{3}+1$ and a block has
cardinality $q+1$, it is possible to choose
$\omega_{4}\in\Omega\setminus\Omega_{2,3}$ and
$\omega_{5}\in\Omega\setminus(\Omega_{3,4}\cup\Omega_{1,2})$. Since the block
containing two elements is unique, we have that four of these five elements
never belong to the same block. Let
$\omega_{i},\omega_{j},\omega_{k},\omega_{l}$ be four of these five elements.
Let $x$ a generator of
$\operatorname{Stab}_{G}(\omega_{i})\cap\operatorname{Stab}_{G}(\omega_{j})$
and $y$ a generator of
$\operatorname{Stab}_{G}(\omega_{l})\cap\operatorname{Stab}_{G}(\omega_{k})$
and consider $H:=\left\langle x,y\right\rangle$. The subgroup $H$ cannot be
contained in maximal subgroups of type $(3)$, $(4)$, $(5)$ and $(6)$, since
these maximal subgroups do not contain elements of order $q-1$. There are no
elements in $G$ of order $q-1$ which fix three distinct elements on $\Omega$,
so $H$ is not contained in maximal subgroups of type $(1)$. Therefore, if
$H<G$ is proper, then $H\leq C_{G}(t)$ for a suitable involution $t$ of $G$.
This occurs when $t$ is contained in the intersection of the four stabilizers
of $\omega_{i},\omega_{j},\omega_{k},\omega_{l}$ but in this case
$\omega_{i},\omega_{j},\omega_{k},\omega_{l}$ belong to the same block,
against our choice of $\omega_{1},\dots,\omega_{5}$. So $H=G$ and we may
conclude by applying Lemma 36. ∎

###  3.6. Small groups

The alternating group $A_{5}$ of degree 5 is the smallest 2-generated finite
group whose generating graph is not perfect. More precisely the following
holds.

######  Theorem 40.

Let $G$ be a 2-generated finite group, with $|G|\leq 60.$ Then $\Gamma(G)$ is
perfect if and only if $G\neq A_{5}.$

###### Proof.

By Theorem 35, we have only to prove that if $|G|\leq 60$ and $G\neq A_{5},$
then $\Gamma(G)$ is perfect. By Theorem 1, $C_{30}\times C_{6}$ is the
smallest 2-generated finite nilpotent group whose generating graph is not
perfect. So we may assume that $G$ is not nilpotent, and by the results in
subsection 3.3 we may exclude $|G|\in\\{pq,pqr,p^{2}q\\}$ with $p,q,r$
different primes. Hence $|G|\in\\{24,36,40,48,54,56,60\\}.$ This requires a
case by case analysis. As an example we consider $G\cong C_{6}\times D_{5}$,
which is the case that requires more attention. The other cases can be
discussed with similar, but in general shorter, arguments. Let $m\geq 5$ be
odd. Set $\left\langle c\right\rangle=C_{6}$ and
$\left\langle\rho,\iota\right\rangle=D_{5}$, with $\rho$ a rotation of order
$5$ and $\iota$ a reflection. Since $C_{2}\times C_{2}$ is an epimorphic image
of $G$, it follows from Lemma 26 that $\Gamma(G)$ does not contain
$m$-antiholes with $m\geq 7$, so we have to check only the non-existence of
$m$-holes. To prove this, we need the list of maximal subgroups of $G$:

  * •

$M_{1}=\left\langle c^{2},\iota,\rho\right\rangle$;

  * •

$M_{2}=\left\langle c^{3},\iota,\rho\right\rangle$;

  * •

$M_{3}=\left\langle c,\rho\right\rangle$;

  * •

$M_{4}=\left\langle\rho,c\iota\right\rangle$;

  * •

$M_{5+\alpha}=\left\langle c,\rho^{\alpha}\iota\right\rangle$ with
$\alpha\in\\{0,1,2,3,4\\}.$

Suppose $(a_{1},\dots,a_{m})$ is a $m$-hole. Consider the two projections
$\pi_{1}:G\to\langle c\rangle,$
$\pi_{2}:G\to\left\langle\rho,\iota\right\rangle.$ There exists
$i\in\\{1,\dots,m\\},$ such that $\langle\pi_{1}(a_{i})\rangle=\langle
c\rangle.$ Otherwise $|\pi_{1}(a_{j})|\in\\{2,3\\}$ for every $1\leq j\leq m,$
and, since $m$ is odd, there would exist two consecutive vertices $a_{k}$ and
$a_{k+1}$ with $|\pi_{1}(a_{k})|=|\pi_{1}(a_{k+1})|=t\in\\{2,3\\}$, and
consequently $G=\left\langle a_{k},a_{k+1}\right\rangle\leq\left\langle
c^{6/t}\right\rangle\times D_{5}.$ So we may assume without loss of generality
$\pi_{1}(a_{1})=c.$ It must be $\pi_{2}(a_{1})\neq 1$ (otherwise $a_{1}$ would
be an isolated vertex of $\Gamma(G).$ Moreover
$\pi_{2}(a_{1})\notin\left\langle\rho\right\rangle,$ otherwise $M_{3}$ would
be the unique maximal subgroup of $G$ containing $a_{1},$ against Lemma 18. So
we may assume $a_{1}=c\iota$. Let $3\leq j\leq m-1.$ Since $\left\langle
a_{1},a_{j}\right\rangle\neq G$ and $M_{4}$, $M_{5}$ are the unique maximal
subgroups of $G$ containing $a_{1},$ it follows $a_{j}\in M_{4}\cup M_{5}$.
Two consecutive vertices of $(a_{1},\dots,a_{m})$ generate $G$, so they cannot
belong to the same maximal subgroup. Hence we can label the vertices of the
$m$-hole so that $a_{3}\in M_{5}$ (and consequently $a_{4}\in M_{4})$. So
$a_{3}=c^{\alpha}\iota$ with $\alpha\in\\{0,1,2,3,4,5\\}.$ Moreover
$\alpha\neq 3$ (otherwise $\left\langle a_{3},a_{4}\right\rangle\leq M_{4}$)
and $\alpha\notin\\{1,5\\}$ (since, by Lemma 19, $\left\langle
a_{3}\right\rangle\neq\left\langle a_{1}\right\rangle$), and so we have
$\alpha=\pm 2$. Notice that $M_{1}$ and $M_{5}$ are the unique maximal
subgroups of $G$ containing $a_{3},$ so $a_{m}\in M_{1}\cup M_{5}.$ On the
other hand, from $\left\langle a_{1},a_{m}\right\rangle=G$ and $a_{1}\in
M_{5},$ it follows $a_{m}\notin M_{5}$ and therefore $a_{m}\in M_{1}.$ Now let
$a_{2}=c^{x}\rho^{y}\iota^{z}$, with $0\leq x\leq 5,$ $0\leq y\leq 4$ and
$0\leq z\leq 1.$ We have $x\notin\\{0,2,4\\}$, otherwise $\left\langle
a_{2},a_{3}\right\rangle\leq M_{1}.$ If $x\in\\{1,5\\}$, then $z=1$ (otherwise
$a_{2}$ would have order 30 and consequently would be contained in a unique
maximal subgroup), but this would imply $\left\langle
a_{1},a_{2}\right\rangle\leq M_{4},$ a contradiction. So it must be $x=3$. If
$z=1$, then again $\left\langle a_{1},a_{2}\right\rangle\leq M_{4}$, a
contradiction, so $z=0$ and therefore $a_{2}=c^{3}\rho^{y}$ with $y\neq 0$. In
particular $M_{2}$ and $M_{3}$ are the unique maximal subgroups of $G$
containing $a_{2}$, and, since $a_{m}$ and $a_{2}$ are not adjacent, $a_{m}\in
M_{2}\cup M_{3}$. We have already proved that $a_{m}\in M_{1}$ so
$a_{m}\in(M_{1}\cap M_{2})\cup(M_{1}\cap M_{3}).$ Since $M_{1}\cap M_{3}\leq
M_{4}$ and $a_{1}\in M_{4},$ if $a_{m}\in M_{1}\cap M_{3},$ then $G=\langle
a_{1},a_{m}\rangle\leq M_{4},$ a contradiction. So $a_{m}\in M_{1}\cap
M_{2}=\langle\rho,\iota\rangle,$ and consequently we may assume
$a_{m-1}=c\rho^{s}\iota^{t}$. We have $t=1$, otherwise $a_{m-1}$ is contained
in a unique maximal subgroup. Then $\left\langle
a_{2},a_{m-1}\right\rangle=\left\langle
c\rho^{s}\iota,c^{3}\rho^{y}\right\rangle=\left\langle
c\rho^{s}\iota,c^{3},\rho\right\rangle=\left\langle
c\iota,c^{3},\rho\right\rangle=\left\langle c,\iota,\rho\right\rangle=G,$ a
contradiction. ∎

##  4\. Other forbidden graphs

######  Proposition 41.

Let $G$ be a non-trivial finite group. Then $G$ does not contain an induced
graph isomorphic to $P_{3}$ if and only if either $G\cong C_{2}\times C_{2}$
or $G\cong C_{p}$ for some prime $p.$

###### Proof.

Suppose that $G$ satisfies the following property: $(*)$ there exist $a,b\in
G$ such that $G=\langle a,b\rangle,$ $G\neq\langle a\rangle,$ $G\neq\langle
b\rangle$ and $a\neq a^{-1}.$ Then $(a,b,a^{-1})$ is a three-vertex path in
$\Gamma(G).$ Assume that $G=\langle a,b\rangle$ is not cyclic. If $G$ is not a
dihedral group, then $(|a|,|b|)\neq(2,2)$. If $G\cong D_{n}$ is a dihedral
group of order $2n,$ then we may choose $a,b$ such that $(|a|,|b|)=(n,2).$ So
if $G$ is not cyclic, then either $G$ satisfies $(*)$ or $G\cong C_{2}\times
C_{2}.$ In this latter case, assume that $(x_{1},x_{2},x_{3})$ is a three-
vertex path in $\Gamma(G)$: then $x_{i}\neq 1$ for any $i\in\\{1,2,3\\},$ but
then $\\{x_{1},x_{2},x_{3}\\}$ induces a complete graph $K_{3}.$ So we may
assume that $G=\langle x\rangle\cong C_{n}.$ If $n=rs$ and $(r,s)=1$, then
$G=\langle x^{r},x^{s}\rangle$ and $(|x^{r}|,|x^{s}|)=(s,r)\neq(2,2)$ so $G$
satisfies $(*)$. If $n=p^{t}$ with $p$ a prime and $t\geq 2,$ then
$(1,x,x^{p})$ is a three-vertex path in $\Gamma(G).$ If $n=p$ is a prime and
$x_{1},x_{2},x_{3}$ are three distinct elements of $G,$ then
$\\{x_{1},x_{2},x_{3}\\}$ induces a complete graph $K_{3}.$ ∎

######  Lemma 42.

Let $p$ be a prime and assume that either $G$ is a cyclic $p$-group or
$|G|=2p.$ Suppose that the subgraph of $\Gamma(G)$ induced by four distinct
non-isolated vertices contains at least one edge. Then at least one of the
four vertices is adjacent to all the others.

###### Proof.

Assume that $X=\\{g_{1},g_{2},g_{3},g_{4}\\}$ induces a non empty-edges
subgraph of $\Gamma(G).$ If $G\cong C_{p^{n}}$ is cyclic of prime power order,
then there exists $i$ with $|g_{i}|=p^{n}$ (otherwise all the elements of $X$
belong to the unique maximal subgroup of $G$). But then $g_{i}$ is adjacent to
$g_{j}$ whenever $j\neq i$. Assume $|G|=2p$. If $X$ contains an element of
order $2p$ then this element generates $G$ so it is adjacent to all the
others. Moreover we cannot have $|g_{j}|=p$ for every $j\in\\{1,\dots,4\\}$,
since all the elements of order $p$ belong to the same maximal subgroup. Thus
there exists $g_{i}\in X$ with $|g_{i}|=2$, but again this implies that
$g_{i}$ is adjacent to $g_{j}$ whenever $j\neq i$. ∎

A graph is chordal if it contains no induced cycle of length greater then 3\.
A graph is called split if its vertex set is the disjoint union of two subsets
$A$ and $B$ so that $A$ induces a complete graph and $B$ induces an empty
graph.

######  Proposition 43.

Let $G$ be a 2-generated finite group. Then the following conditions are
equivalent.

  1. (1)

$\Gamma(G)$ is split.

  2. (2)

$\Gamma(G)$ is chordal.

  3. (3)

$\Gamma(G)$ is $C_{4}$-free.

  4. (4)

Either $G$ is a cyclic $p$-group or $|G|=2p$ for some prime $p.$

###### Proof.

Clearly (2) implies (3).

Assume that (3) holds. If there exist $a,b\in G$ so that $G=\langle
a,b\rangle$, $\langle a\rangle\neq G$, $\langle b\rangle\neq G$, $|a|\neq 2,$
$|b|\neq 2$, then the subgraph of $\Gamma(G)$ induced by
$\\{a,b,a^{-1},b^{-1}\\}$ is a four-vertex cycle. If $G$ is cyclic of order
$n$, then we can find $a,b$ with the previous properties except when $n$ is a
prime-power or $n=2p$ with $p$ a prime. So we may assume that $G$ is non-
cyclic and $G=\langle a,b\rangle$ with $|a|=2.$ Moreover either $b$ or $ab$
has order 2, otherwise $(b,ab)$ is a generating pair with the previous
properties. Hence $G=\langle a,b\rangle=\langle a,ab\rangle$ can be generated
by two involutions, so $G$ is isomorphic to a dihedral group $D_{n}$ of order
$2n$ and we may assume $|b|=n.$ If $n$ is not a prime and $p$ is a prime
divisor of $n,$ then the subgroup of $\Gamma(G)$ induced by
$\\{a,b,ab^{p},b^{-1}\\}$ is a four-vertex cycle.

It follows from Lemma 42 that (4) implies (2).

It was shown in [8] that a graph is split if and only if it does not have an
induced subgraph isomorphic to one of the three forbidden graphs, $C_{4},$
$C_{5}$ or $2K_{2}.$ In particular (1) implies (3) and we may immediately
deduce from Lemma 42 that (4) implies (1). ∎

## References

  * [1] John N. Bray, Derek F. Holt, and Colva M. Roney-Dougal, _The maximal subgroups of the low-dimensional finite classical groups_ , vol. 407, Cambridge University Press, 2013.
  * [2] Thomas Breuer, Robert M. Guralnick, and William M. Kantor, _Probabilistic generation of finite simple groups, II_ , Journal of Algebra 320 (2008), no. 2, 443–494.
  * [3] Thomas Breuer, Robert M. Guralnick, Andrea Lucchini, Attila Maróti, and Gábor P. Nagy, _Hamiltonian cycles in the generating graphs of finite groups_ , Bulletin of the London Mathematical Society 42 (2010), no. 4, 621–633.
  * [4] Timothy C. Burness, Robert M. Guralnick, and Scott Harper, _The spread of a finite group_ , Annals of Mathematics 193 (2021), no. 2, 619–687.
  * [5] Peter J. Cameron, _Graphs defined on groups_ , (2021), https://arxiv.org/abs/2102.11177.
  * [6] Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas, _The strong perfect graph theorem_ , Annals of mathematics 164 (2006), no. 1, 51–229.
  * [7] Eleonora Crestani and Andrea Lucchini, _The generating graph of finite soluble groups_ , Israel Journal of Mathematics 198 (2013), no. 1, 63–74.
  * [8] Stéphane Foldes and Peter L. Hammer, _Split graphs_ , Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing, 1977, pp. 311–315.
  * [9] The GAP Group, _Gap – groups, algorithms, and programming, version 4.11.1_ , 2021, https://www.gap-system.org.
  * [10] Wolfgang Gaschütz, _Zu einem von B. H. und H. Neumann gestellten Problem_ , Mathematische Nachrichten 14 (1955), no. 4-6, 249–252.
  * [11] Wolfgang Gaschütz, _Die eulersche funktion endlicher auflösbarer gruppen_ , Illinois Journal of Mathematics 3 (1959), no. 4, 469–476.
  * [12] Robert M. Guralnick and William M. Kantor, _Probabilistic generation of finite simple groups_ , Journal of Algebra 234 (2000), no. 2, 743–792.
  * [13] Scott Harper and Andrea Lucchini, _Connectivity of generating graphs of nilpotent groups_ , Algebraic Combinatorics 3 (2020), no. 5, 1183–1195.
  * [14] Gareth A. Jones, _Primitive permutation groups containing a cycle_ , Bulletin of the Australian Mathematical Society 89 (2014), no. 1, 159–165.
  * [15] Andrea Lucchini, _The diameter of the generating graph of a finite soluble group_ , Journal of Algebra 492 (2017), 28–43.
  * [16] G. Ravindra and K. R. Parthasarathy, _Perfect product graphs_ , Discrete Mathematics 20 (1977), 177–186.
  * [17] Derek J. S. Robinson, _A course in the theory of groups_ , Second ed., Graduate Texts in Mathematics, vol. 80, Springer-Verlag, New York, 1996.
  * [18] Rulin Shen, _Intersection graphs of subgroups of finite groups_ , Czechoslovak mathematical journal 60 (2010), no. 4, 945–950.