The Clique Number of the Intersection Graph of a Finite Group

Abstract

For a nontrivial finite group G, the intersection graph $\Gamma (G)$ of G is the simple undirected graph whose vertices are the nontrivial proper subgroups of G and two vertices are joined by an edge if and only if they have a nontrivial intersection. In a finite simple graph $\Gamma$, the clique number of $\Gamma$ is denoted by $\omega (\Gamma )$. In this paper we show that if G is a finite group with $\omega (\Gamma (G))<13$, then G is solvable. As an application, we characterize all non-solvable groups G with $\omega (\Gamma (G))=13$. Moreover, we determine all finite groups G with $\omega (\Gamma (G))\in \{2,3,4\}$.

1 Introduction and Main Results

Let G be a group. There are several ways to associate a graph to G (see [8] and the references therein). In this paper, we consider the intersection graph of G which is denoted by $\Gamma (G)$. The intersection graph $\Gamma (G)$ of a nontrivial group G is a simple and undirected graph defined as follows: the vertex set is the set of all proper non-trivial subgroups of G, and there is an edge between two distinct vertices H and K if and only if $H\cap K\ne 1$, where 1 denotes the trivial subgroup of G. The graph $\Gamma (G)$ has been extensively studied (see, for example, [1, 10, 11, 14, 19, 21, 22, 26]), when G is finite. Also in [12], the subgraph $\Gamma M(G)$ whose vertices are maximal subgroups of a finitely generated group G is investigated. Intersection graphs of subsemigroups of a semigroup, submodules of a module, and ideals of a ring, were investigated in [2, 7] and [9, 15], respectively.

Let $\Gamma$ be a simple graph. The set of vertices of every complete subgraph of $\Gamma$ is called a clique of $\Gamma$. The maximum size of a complete subgraph of $\Gamma$ is called the clique number of $\Gamma$ and it is denoted by $\omega (\Gamma )$. For convenience, we write $\omega (\Gamma )=0$ if $\Gamma$ has no vertices (i. e. $\Gamma$ is the empty graph) and $\omega (\Gamma )=1$ if $\Gamma$ has a non-empty vertex set with no edges (i. e. $\Gamma$ is null).

In group theory, it is well known that the quantitative properties of some special subgroups play an important role in characterizing the solvability of groups (see [16, 17, 25]). In this paper we give a criterion for solvability of G by $\omega (\Gamma (G))$.

Theorem 1.1

Let G be a finite group such that $\omega (\Gamma (G))<13$. Then G is solvable.

We point out that $\omega (\Gamma (A_5))=13$, where $A_5$ is the alternating group on 5 letters (see the proof of Lemma 3.3), therefore, the bound in Theorem 1.1 is the best possible.

As a consequence of Theorem 1.1, we give a characterization of $A_5$.

Corollary 1.2

Let G be a non-solvable group. Then $\omega (\Gamma (G))=13$ if and only if $G\cong A_5$.

Remark 1.3

For a finite group G, it is clear that $\omega (\Gamma (G))=0$ if and only if $G\cong C_p$, where $C_p$ is a cyclic group of order p, for some prime number p. By Lemma 2.2 of [19], we see that $\omega (\Gamma (G)=1$ if and only if G is isomorphic to one of the following groups:

$$\begin{aligned} C_{p^2},~~~C_{pq},~~~C_p\times C_p,~~~C_p\rtimes C_q, \end{aligned}$$

where p and q are distinct prime numbers and the last group is the semidirect product of $C_p$ by $C_q$.

In what follows, we determine groups G with $2\le \omega (\Gamma (G))\le 4$.

Theorem 1.4

Let G be a finite group. Then $\omega (\Gamma (G))=2$ if and only if one of the following cases occurs::

$\mathrm{(a)}$ G is a cyclic group of order $p^3$, for a prime p.

$\mathrm{(b)}$ $G=N\rtimes H$ is Frobenius whose kernel N is the minimal normal subgroup of G such that $N\cong C_p\times C_p$ and $H\cong C_q$, where p and q are primes.

Theorem 1.5

Let G be a finite group. Then $\omega (\Gamma (G))=3$ if and only if one of the following statements holds:

$\mathrm{(a)}$ G is cyclic and $G\cong C_{p^4},~C_{p^2q}$ or $C_{pqr}$, where p, q and r are distinct primes.

$\mathrm{(b)}$ $G=N\rtimes H$ is Frobenius whose kernel N is the (unique) minimal normal subgroup of G and we have either

$\mathrm{(1)}$ $N\cong C_p$ and $H\cong C_{q^2}$ or $C_{qr}$ or

$\mathrm{(2)}$ $N\cong C_p\times C_p$, $H\cong C_{q^2}$ and G does not have any subgroup of order pq, where p, q and r are distinct primes.

Theorem 1.6

Let G be a finite group. Then $\omega (\Gamma (G))=4$ if and only if one of the following holds:

$\mathrm{(a)}$ G is abelian and $G\cong C_{p^5},~C_2\times C_2\times C_q$ or $C_4\times C_2$, where p, q are primes and q is odd..

$\mathrm{(b)}$ G is non-abelian and isomorphic to one of the followings:

$\mathrm{(1)}$ $D_8$ or $Q_8$ or

$\mathrm{(2)}$ $G=N\rtimes H$ is Frobenius whose kernel N is the (unique) minimal normal subgroup of G such that $N\cong C_p\times C_p$, $H\cong C_{qr}$ and G does not have subgroups of orders pr and pq, where p, q, r are distinct primes.

Now we give some examples of groups, satisfying in Theorems 1.4, 1.5 and 1.6. Since $A_4\cong (C_2\times C_2)\rtimes C_3$ satisfies in Theorem 1.4(b),we have $\omega (\Gamma (A_4))=2$. In GAP-System [23], two groups

$$\begin{aligned} G_1=AllSmallGroups(42, IsAbelian,false)[1]\cong C_7\rtimes C_6 \end{aligned}$$

and

$$\begin{aligned} G_2=AllSmallGroups(52, IsAbelian,false)[2]\cong C_{13}\rtimes C_4, \end{aligned}$$

satisfy in Theorem 1.5(b)(1) and so $\omega (\Gamma (G_1))=\omega (\Gamma (G_2)=3$. Also, for $G_3=AllSmallGroups(11^2. 4, IsAbelian,false)[5]\cong (C_{11}\times C_{11})\rtimes C_4$, we have $\omega (\Gamma (G_3))=3$, by Theorem 1.5(b)(2). Finally if $G_4=AllSmallGroups(11^2. 6, IsAbelian,false)[5]\cong (C_{11}\times C_{11})\rtimes C_6$, then $\omega (\Gamma (G_4))=4$, by Theorem 1.6(b)(2).

In this paper all groups are finite and we use the usual notation, for example $C_n$, $A_n$, $S_n$, PSL(2, q) and Sz(q), respectively, denote the cyclic group of order n, the alternative group on n letters, the symmetric group on n letters, the projective special linear group of degree 2 over the finite field of size q and the Suzuki group over the field with q elements. For a group G, $x\in G$ and $H\le G$, we denote by $Z(G), C_G(x), N_G(H), H^x$, the center of G, the centralizer of x in G, the normalizer of H in G and the conjugate of H in G by x, respectively. Also $\mathcal {S}(G)$ is the set of all subgroups of G. The rest of the notation is standard and can be found mainly in [18].

2 Preliminary Results

We frequently use the following results and we state it here for the reader’s convenience.

Lemma 2.1

(see 1.3.11 of [18]) Let G be a group and H and K be subgroups of G. Then $|G: H\cap K|\le |G:H||G:K|$, with equality if the indices |G : H| and |G : K| are coprime.

Theorem 2.2

(see 8.5.5 of [18]) If G is a finite group with a subgroup H such that $H\cap H^x = 1$, for all $x \in G{\setminus } H$, then $N = (G{\setminus } (\cup _{x\in G}H^x))\cup \{1\}$ is a normal subgroup of G and $G =N\rtimes H$.

A group G which has a proper nontrivial subgroup H, satisfying in the hypothesis of Theorem 2.2 is called a Frobenius group, H is called a Frobenius complement and N the Frobenius kernel. In this case, $Z(G)=1$ and |H| divides $|N|-1$, by Exercises 8.5 (2) and (6) of [18] respectively. Note that if $1\ne x\in N$, then $C_G(x)\le N$, by Exercise 8.5 (5) of [18].

Recall that a subgroup H of a group G is supplemented in G if there is a subgroup K of G such that $G=HK$. Moreover if $H\cap K=1$, then H is complemented in G by K.

Proposition 2.3

Let G be a group and N be a proper minimal normal abelian subgroup of G. If $G=HN$, for some subgroups H of G and N is complemented in G by H, then H is a maximal subgroup of G.

Proof

Assume that there is a subgroup K of G such that $H\lvertneqq K$. Since $G=HN$, we have $K=H(K\cap N)$. Therefore, $K\cap N\ne 1$. Since N is the abelian normal subgroup of G and $G=KN$, we have $K\cap N\lhd G$. Thus $K\cap N=N$, by minimality of N and so $N<K$. Consequently $K=G$, as required. $\square$

Recall that a finite group G is said to be primitive if it has a maximal subgroup M with $Core_G(M):=\cap _{g\in G}M^g=1$. In this situation we call M a stabilizer of G. We need the following theorem of R. Baer on primitive groups.

Theorem 2.4

(see [3]) Let G be a finite primitive group with a stabilizer M. Then one of the following three statements holds:

• (1) G has a unique minimal normal subgroup N, this subgroup N is self-centralizing, and N is complemented by M in G.

• (2) G has a unique minimal normal subgroup N, this N is non-abelian, and N is supplemented by M in G.

• (3) G has exactly two minimal normal subgroups N and $N^*$, and each of them is complemented by M in G. Also $C_G(N) = N^*$, $C_G(N^*) = N$ and $N\cong N^*\cong NN^* \cap M$.

The following lemma is straightforward but is useful in the sequel.

Lemma 2.5

Let G be a finite group.

$\mathrm{(i)}$ If $1<H<G$, then $\omega (\Gamma (H))< \omega (\Gamma (G))$.

$\mathrm{(ii)}$ If $1<N\lhd G$, then $|\mathcal {S}(\frac{G}{N})|-1+\omega (\Gamma (N))\le \omega (\Gamma (G))$.

$\mathrm{(iii)}$ Suppose that $\Omega$ is a clique in $\Gamma (G)$, and $H\in \Omega$. If |H| is prime, then $H\le K$, for every $K\in \Omega$.

Proof

The proofs of (i) and (iii) are clear. For (ii), if $\omega (\Gamma (N))=k$, for some positive integer k, then there are proper subgroups $N_1, \ldots , N_k$ of N such that $N_i\cap N_j\ne 1$, for each $1\le i<j\le k$. If T is a subgroup of $\frac{G}{N}$, then there exists a unique subgroup K of G such that $N\le K$ and $T=\frac{K}{N}$. Now assume that $|\mathcal {S}(\frac{G}{N})|=l$, for some positive integer l. Then there exist subgroups $K_1=N, K_2, \ldots , K_{l-1}, K_l=G$ containing N of G such that $\mathcal {S}(\frac{G}{N})=\{\frac{K_1}{N}, \frac{K_2}{N}, \ldots , \frac{K_l}{N}\}$. So we have $\{N_1, \ldots , N_k, K_1,\ldots , K_{l-1}\}$ is a clique in $\Gamma (G)$. It follows that $\omega (\Gamma (G))\ge k+l-1$, as required. $\square$

We denote by m(G) the number of maximal subgroups of a group G. In the following, we give m(G), for any p-group G, where p is a prime number.

Lemma 2.6

Let G be a finite p-group. Then $m(G)=m(\frac{G}{\Phi (G)})=\frac{|\frac{G}{\Phi (G)}|-1}{p-1}$.

Proof

Since $\Phi (G)$ is contained in any maximal subgroup of G, it is easy to see that $\frac{M}{\Phi (G)}$ is a maximal subgroup of $\frac{G}{\Phi (G)}$ whenever M is a maximal subgroup of G. On the other hand, similar to the proof of Lemma 2.5(ii), if T is a maximal subgroup of $\frac{G}{\Phi (G)}$, then there is a unique maximal subgroup M of G such that $T=\frac{M}{\Phi (G)}$. Thus we conclude that there exists a one-one correspondence from the set of all maximal subgroups of G to the set of all maximal subgroups of $\frac{G}{\Phi (G)}$ and then $m(G)=m(\frac{G}{\Phi (G)})$. By the proof of 5.3.2 of [18], we have $\frac{G}{\Phi (G)}$ is elementary abelian. Now if $|\frac{G}{\Phi (G)}|=p^m$, then every maximal subgroup of $\frac{G}{\Phi (G)}$ has order $p^{m-1}$ and so by [5, Exercise 1(d), p. 81]] we have $m(\frac{G}{\Phi (G)})=1+p+\cdots +p^{m-1}$. It follows that $m(\frac{G}{\Phi (G)})=\frac{|\frac{G}{\Phi (G)}|-1}{p-1}$, as desired. $\square$

3 A Criterion for Solvability by $\omega (\Gamma (G))$

In this section, we prove Theorem 1.1 and Corollary 1.2. The famous family of simple finite groups are minimal simple groups (i.e., finite non-abelian simple groups all of whose proper subgroups are solvable). The classification of minimal simple groups is given by Thompson (see Corollary 1 of [24]). As Thompson’s classification of the minimal simple groups is a very useful tool to obtain solvability criteria in the class of finite groups. In Lemmas 3.3, 3.4, 3.5, 3.6 and 3.7, we show that if G is a minimal simple group non-isomorphic to $A_5$, then $\omega (\Gamma (G)>13$. We need these results in the proof of Theorem 1.1 and Corollary 1.2.

In the following we give some facts about subgroups of $G=A_5$. The proofs are elementary (for example, one may check by software GAP [23]).

Fact 1. $|\mathcal {S}(A_5)|=59$ and if $n_k$ is the number of subgroups of G of order k, then $n_2=15, n_3=n_6=10, n_4=n_{12}=5$ and $n_5=n_{10}=6$.

Fact 2. If M is a maximal subgroup of G, then $|M|\in \{6, 10, 12\}$. Also all maximal subgroups of G of the same order are conjugate in G.

Fact 3. If $M_1, M_2$ and $M_3$ are maximal subgroups of G such that $|M_1|=6, |M_2|=10$ and $|M_3|=12$, then $|M_i^x\cap M_j^y|\ne 1$, for every $1\le i<j\le 3$ and $x, y\in G$. Moreover, $|M_2\cap M_2^a|=2$ and $|M_3\cap M_3^b|=3$, for each $a\in G{\setminus } M_2$ and $b\in G{\setminus } M_3$. Therefore, $\Lambda =\{M_1, M_2^g, M_3^g:~~g\in G\}$ is a clique in $\Gamma (G)$ and so $\omega (\Gamma (G))\ge 1+n_{10}+n_{12}=12$.

Fact 4. Assume that $M_1, M_2$ and $M_3$ are the same as in Fact 3. If $M_i, M_i^x$ and $M_i^y$ are distinct conjugates of $M_i$ in G, for some $x, y\in G$, then $|M_i\cap M_i^x\cap M_i^y|=1$, for each i and $\{M_1, M_1^x, M_1^y\}$ does not form a clique in $\Gamma (G)$. Also we have $|M_1\cap M_1^g|\le 2$, for every $g\in G{\setminus } M_1$ and there is $z\in G$ such that $|M_1\cap M_1^z|=2$. Thus $\Lambda \cup \{M_1, M_1^z\}$ is a clique, by Fact 3, and so $\omega (\Gamma (G))\ge 13$.

We use of above facts in the proof of the following lemma.

Lemma 3.1

We have $\omega (\Gamma (A_5))=13$.

Proof

Let $\Omega$ be a clique in $\Gamma (A_5)$ of maximum size. Then $|\Omega |\ge 13$, by Fact 4. Now, we consider the following cases:

Case 1. In this case, we show that $\Omega$ does not have any member of size 2. Assume that there is $H_2\in \Omega$ with $|H_2|=2$. Then other subgroups of order 2, all subgroups of order 3 and all subgroups of order 5 of $A_5$ do not belong to $\Omega$ and so $|\Omega |\le 57-((n_2-1)+n_3+n_5)=27$, by Fact 1. Since the intersection of any two distinct subgroups of order 4 is trivial, there is only one subgroup $H_4$ of order 4 containing $H_2$. Thus, $|\Omega |\le 27-(n_4-1)=23$. Note that if $X\in \Omega$, then $H_2\subseteq X$, by Lemma 2.5(iii). By Fact 4, $\Omega$ has at most two subgroups of order 6. Also, by Facts 3, 4 and Lemma 2.5 (iii), $\Omega$ has at most two subgroups of order 10. Since the intersection of any two distinct subgroups of order 12 has order 3 by Fact 3, $\Omega$ has at most one subgroup of order 12. It follows that $|\Omega |\le 23-((10-2)+(6-2)+(5-1))=7$, a contradiction.

Case 2. In this case, we show that $\Omega$ does not have any member of size 3. Assume that there exists $H_3\in \Omega$ with $|H_3|=3$. Then $\Omega$ does not have any subgroup of order 2, 4, 5 and 10 and so $|\Omega |\le 57-(n_2+n_4+n_5+n_{10})=25$, by Fact 1. Since $\Omega$ does not have two subgroups of order 3, we have $|\Omega |\le 25-9=16$. Also if $X\in \Omega$, then $H_3\subseteq X$, by Lemma 2.5(iii). By Fact 4, $H_3$ is contained in only one subgroup of order 6. Therefore, $|\Omega |\le 16-9=7$, which is impossible.

Case 3. In this case, we show that $\Omega$ does not have any member of size 4. Assume that there exists $H_4\in \Omega$ with $|H_4|=4$. By Case 1, $\Omega$ does not have any subgroup of order 2. Since $n_2=15, n_3=10, n_4=5$ and $n_5=6$, we have $|\Omega |\le 57-(15+10+4+6)=22$. Since every clique can contain at most two subgroups of order 6 by fact 4, we have $|\Omega |\le 22-(n_6-2)=14$. Note that $H_4$ is contained in at least one maximal subgroup, which is certainly of order 12. By Fact 3, there is only one subgroup K of order 12 such that $H_4\subset K$ and hence $|\Omega |\le 14-4=10$, which is a contradiction.

Case 4. In this case, we show that $\Omega$ does not have any member of size 5. Assume that there exists $H_5\in \Omega$ with $|H_5|=5$. Since $n_2=15, n_3=n_6=10, n_4=n_{12}=5$ and $n_5=6$, we have $|\Omega |\le 57-(15+ 20+10+5)=7$, a contradiction.

Case 5. In this case, we first show that $\Omega$ has at least one member of size 6 and then prove that $|\Omega |=13$. Suppose, for a contradiction, that $\Omega$ does not have any member of size 6. By Cases 1–4, we conclude that $\Omega$ does not have any subgroup of order 2, 3, 4 and 5. By Fact 1, every member of $\Omega$ has size either 10 or 12 and so $|\Omega |\le n_{10}+ n_{12}=11$, a contradiction. It follows that there exists $H_6\in \Omega$ with $|H_6|=6$. Again, by Cases 1-4, we have $|\Omega |\le n_6+ n_{10}+ n_{12}=16$. On the other hand $\Omega$ has at most two members of size 6 by Fact 4. Thus $|\Omega |=13$ by Fact 4 and this completes the proof. $\square$

In the proofs of Lemmas 3.3, 3.4 and 3.5, we need the following result about the Sylow p-subgroups of $PSL(2, p^n)$, where p is a prime number and n is a positive integer.

Proposition 3.2

Let $G=PSL(2, p^n)$. Then a Sylow p-subgroup P of G is elementary abelian of order $p^n$ and the number of Sylow p-subgroups of G is $p^n+1$ (or equivalently, we have $|G: N_G(P)|=p^n+1$).

Proof

See Satz 8.2, p. 191 of [13]. $\square$

Lemma 3.3

For any odd prime p, we have $\omega (\Gamma (PSL(2, 2^p))>13$.

Proof

If $p=3$, then $G=PSL(2,8)$ has a maximal subgroup M of index 28 in G. Since G is simple, M is not normal in G and so $N_G(M)=M$. It follows that M has 28 conjugates in G,  say $M_1=M, M_2,\ldots , M_{28}$. It is easily checked by GAP [23] that $|M_i\cap M_j|=2$, for all distinct i, j and so $\omega (\Gamma (PSL(2, 2^m))\ge 28$, as required.

If $p\ge 5$, then $q=2^p\ge 32$. By Proposition 3.2, we have $|G: N_G(P)|=q+1$, where $P\in Syl_2(G)$. Since $N_G(N_G(P))=N_G(P)$, the number of conjugates of $N_G(P)$ is $q+1$. It follows that $N_G(P)$ has $q+1$ conjugates in G. If $N_G(P)\ne N_G(P)^g$, for some $g\in G$, then $|G: N_G(P)\cap N_G(P)^g|\le (q+1)^2$, by lemma 2.1. Since $|G|=\frac{q(q^2-1)}{2}$, we have $|N_G(P)\cap N_G(P)^g|\ne 1$. Therefore, $\{N_G(P)^x:~x\in G\}$ is a clique in the $\Gamma (G)$ and so $\omega (\Gamma (G))\ge q+1>13$, as claimed. $\square$

Lemma 3.4

$\omega (\Gamma (PSL(2, 3^p))>13$, for any odd prime p.

Proof

By Proposition 3.2, we have $|G: N_G(P)|=3^p+1$, where $P\in Syl_3(G)$. Similar to the proof of Lemma 3.3, $\{N_G(P)^x:~x\in G\}$ is a clique in the $\Gamma (G)$ and so $\omega (\Gamma (G))\ge 3^p+1>13$ and this completes the proof. $\square$

Lemma 3.5

$\omega (\Gamma (PSL(2, p))>13$, where $p > 3$ is a prime with $p^2 + 1$ divisible by 5.

Proof

If $G=PSL(2,7)$, then G has 14 (maximal) subgroups of index 7 ( one can check it by GAP [23]), say $M_1, M_2,\ldots , M_{14}$. Since $|G|=168$ and $|G:M_i\cap M_j|\le 49$, for every $1\le i\ne j\le 14$, we have $|M_i\cap M_j|\ne 1$, by Lemma 2.1 and so $\{M_1, \ldots , M_{14}\}$ is a clique in the $\Gamma (G)$ and so $\omega (\Gamma (G))\ge 14$, as wanted.

Now if $p\ge 13$, then by the similar argument in the proof of Lemmas 3.3 and 3.4, we see that $\omega (\Gamma (G))\ge p+1>13$ and the proof is complete. $\square$

Lemma 3.6

We have $\omega (\Gamma (PSL(3, 3))>13$.

Proof

By GAP [23], G has 26 maximal subgroups of index 13, say $M_1, M_2,\ldots , M_{26}$. Since $|G|=5616$ and $|G:M_i\cap M_j|\le 169$, for every $1\le i\ne j\le 26$, we have $|M_i\cap M_j|\ne 1$ and so $\omega (\Gamma (G))\ge 26$, as required. $\square$

Lemma 3.7

We have $\omega (\Gamma (Sz(2^m)))>13$, where m is an odd prime.

Proof

Suppose that $q=2^m$, $G=Sz(q)$ and $F\in Syl_2(G)$. Then it is well-known that $|F|=q^2$ and Z(F) is elementary abelian of order q. It follows from Lemma 5.9 in Chapter XI of [13] that $|C_F(g): Z(F)|=2$, for all $g\in F{\setminus } Z(F)$ and so $C_F(g)$ is abelian. Assume that $\{C_F(x_1), C_F(x_2),\ldots , C_F(x_n)\}$ is the set of all proper centralizers of elements in F. Then $F=\cup _{i=1}^nC_F(x_i)$ and $C_F(x_i)\cap C_F(x_j)=Z(F)$, for each $i\ne j$. Since $|F|=q^2, |Z(F)|=q$ and $|C_F(x_i)|=2q$, we have $n=q-1$. Also Z(F) has $q-1$ maximal subgroups, by Lemma 2.6 and the intersection of any pair of these maximal subgroups are non-trivial, by Lemma 2.1. If $Z_1, \ldots , Z_{q-1}$ are maximal subgroups of Z(F), then $\{Z_1, \ldots , Z_{q-1}, C_F(x_1), \ldots , C_F(x_{q-1})\}$ is a clique in $\Gamma (G)$. Since $q\ge 8$, we have $\omega (\Gamma (Sz(2^m)))\ge 2(q-1)\ge 14$. This completes the proof. $\square$

Now we are ready to prove the first main result:

Proof of Theorem 1.1

Suppose, on the contrary, that there exists a non-solvable finite group G of the least possible order with $\omega (\Gamma (G))<13$. If there exists a non-trivial proper normal subgroup N of G, then $\omega (\Gamma (N))<13$ and $\omega (\Gamma (\frac{G}{N}))<13$, by Lemma 2.5(i-ii). By minimality of |G|, we have $\frac{G}{N}$ and N are solvable, which implies that G is solvable, a contradiction. Thus G is simple and so by Theorem 1 of [4] and Lemma 2.5(i), G is a minimal simple group. By Thompson’s classification of minimal simple groups [24], G is isomorphic to one of the following simple groups: $A_5$, $PSL(2, 2^m)$, where m is an odd prime; $PSL(2, 3^m)$, where m is an odd prime; PSL(2, p), where $p > 3$ is a prime with $p^2 + 1$ divisible by 5; PSL(3, 3); or $Sz(2^m)$, where m is an odd prime. By Lemmas 3.1, 3.3, 3.4, 3.5, 3.6 and 3.7, we have $\omega (\Gamma (G))\ge 13$, which is impossible. $\square$

Proof of Corollary 1.2

If $G\cong A_5$, then $\omega (\Gamma (G))=13$, by Lemma 3.1. Conversely, assume that G is non-solvable with $\omega (\Gamma (G))=13$. If M is a maximal subgroup of G, then $\omega (\Gamma (M))<13$, by Lemma 2.5(i). So M is solvable by Theorem 1.1. Thus every maximal subgroup of G is solvable and so G is a minimal non-solvable group. Therefore, G is a minimal simple group. By the proof of Theorem 1.1 and Lemmas 3.1, 3.3, 3.4, 3.5, 3.6 and 3.7, we conclude that $G\cong A_5$, as desired. $\square$

4 Groups G with $2\le \omega (\Gamma (G))\le 4$

In this section, we prove Theorems 1.4, 1.5 and 1.6. First, we obtain $\omega (\Gamma (G))$, for some groups which are needed later.

Lemma 4.1

For any distinct primes p, q and r and positive integer n, we have

• (1) $\omega (\Gamma (C_{p^n}))=n-1$.

• (2) $\omega (\Gamma (C_p\times C_p\times C_p))=p^2+p+1$.

• (3) $\omega (\Gamma (C_{pqr}))=\omega (\Gamma (C_{p^2q}))=3$.

• (4) $\omega (\Gamma (C_{p^2}\times C_p))= \omega (\Gamma (C_{pq}\times C_p))=p+2$.

• (5) If G is a non-abelian group of order $p^3$, then $\omega (\Gamma (G))=p+2$.

Proof

• (1) If $G=C_{p^n}$, then G has a unique subgroup $H_i$ of order $p^i$, for each $0\le i\le n$ and so $H_i<H_{i+1}$, for every i. Therefore, $\{H_1, H_2,\ldots , H_{n-1}\}$ is the unique clique in $\Gamma (G)$ with maximum size, as required.

• (2) Suppose that $G=C_p\times C_p\times C_p$ and $\Omega$ is a clique in $\Gamma (G)$. If $H\in \Omega$, with $|H|=p$, then, by Lemma 2.5 (iii), $H<K$, for every $K\in \Omega {\setminus } \{H\}$ and so $|K|=p^2$. Since $\frac{G}{H}\cong C_p\times C_p$ and the number of subgroups of $C_p\times C_p$ of order p is $p+1$, by the proof of Lemma 2.5(ii),the number of proper subgroups of G containing H is $p+2$ and so $|\Omega |\le p+2$. Now suppose that $\Omega$ does not contain any subgroup of G of order p. Then $|K|=p^2$, for every $K\in \Omega$ and so K is a maximal subgroup of G. Since $\Phi (G)=1$, the number of maximal subgroups of G is $\frac{|\frac{G}{\Phi (G)}|-1}{p-1}=p^2+p+1$, by Lemma 2.6. Therefore $|\Omega |\le p^2+p+1$. It follows from Lemma 2.1 that the intersection of any two distinct maximal subgroups of G are non-trivial. This implies that all maximal subgroups of G forms a clique with maximum size in $\Gamma (G)$, as wanted.

• (3) The proof is clear.

• (4) Suppose that $G=C_{p^2}\times C_p$ and $\Omega$ is a clique in $\Gamma (G)$. If $H\in \Omega$ such that $|H|=p$, then $H<K$, for every $K\in \Omega \setminus \{H\}$, by Lemma 2.5 (iii) and so $|K|=p^2$. Since the number of proper subgroups of G containing H is at most $p+2$ and so $|\Omega |\le p+2$. On the other hand $|\Phi (G)|=p$ and so the number of maximal subgroups of G is $p+1$. It follows that these maximal subgroups of G together with $\Phi (G)$ forms a clique with maximum size in $\Gamma (G)$ and so $\omega (\Gamma (G))=p+2$, as desired.

Suppose that $G=C_{pq}\times C_p$ and $\Omega$ is a clique in $\Gamma (G)$. If $\Omega$ does not contain any subgroup of G of prime order, then $\Omega =\{T\}$ such that $|T|=p^2$. If there is a subgroup H of G such that $H\in \Omega$ and $|H|=p$, then $\frac{G}{H}\cong C_{pq}$ and so $|\Omega |\le 3$. Finally assume that $Q\in \Omega$ such that $|Q|=q$. Then $Q\le K$, for every $K\in \Omega$ by Lemma 2.5 (iii). On the other hand the number of proper subgroups of G containing Q is $p+2$ and so $|\Omega |\le p+2$. Hence $\omega (\Gamma (G))=p+2$, as required.

• (5) The proof is similar to the first case of (4).

$\square$

Lemma 4.2

Let $G=N\rtimes H$ be a Frobenius group such that N is a minimal normal subgroup of G and H is a Frobenius complement. Also assume that p, q and r are distinct primes.

• (1) If $N\cong C_p$ and $H\cong C_{q^2}$ or $C_{qr}$, then $\omega (\Gamma (G))=3$.

• (2) If $N\cong C_p\times C_p$ and $H\cong C_q$, then $\omega (\Gamma (G))=2$.

• (3) If $N\cong C_p\times C_p$ and $H\cong C_{q^2}$ such that $q \not \mid p-1$, then $\omega (\Gamma (G))=3$.

• (4) If $N\cong C_p\times C_p$ and $H\cong C_{qr}$ such that $q\not \mid p-1$ and $r\not \mid p-1$, then $\omega (\Gamma (G))=4$.

Proof

(1) Suppose that $N\cong C_p$ and $H\cong C_{q^2}$ and $1<H_1<H$. Since $G=N\rtimes H$ is a Frobenius group, $H\cap H^x=1$ and so $H_1\cap H_1^x=1$, for every $1\ne x\in N$. Therefore, G has p subgroups of order q and so all of them are contained in the non-abelian subgroups $K=NH_1$. It follows that $K=NH_1$ is the unique subgroup of G of order pq. It is clear that $K\cap T\ne 1$, for every non-trivial proper subgroup T of G. Thus K belongs to any clique with maximum size. Note that every clique contains at most one subgroup of order $q^2$ and also at most one subgroup of order q. If N belongs to a clique $\Omega$, then $H_1^x$ and $H^x$ do not belong to $\Omega$, for every $x\in N$. Thus $\{H_1^x, H^x, K\}$ is a clique with maximum size in $\Gamma (G)$, for every $x\in N$, as required.

Now suppose that $H\cong C_{qr}$. Then H contains (unique) subgroups Q and R of order q and r respectively. Since $G=N\rtimes H$ is a Frobenius group, we have $H\cap H^x=1$, $Q\cap Q^x=1$ and $R\cap R^x=1$, for every $1\ne x\in N$. Therefore $|Syl_q(G)|=|Syl_r(G)|=|G:N_G(H)|=|G:H|=p$. Since G is Frobenius, $Z(G)=1$ and so NQ and NR are non-abelian. Therefore NQ and NR are the only subgroups of G of orders pq and pr, respectively. Note that the only proper subgroups of G containing properly $Q^x$, for some $x\in N$ are $H^x$ and NQ, the only proper subgroups of G containing properly $R^x$, for some $x\in N$ are $H^x$ and NR and also the only proper subgroups of G containing properly N are NQ and NR. Now suppose that $\Omega$ is a clique in $\Gamma (G)$ with maximum size.

If $Q^x\in \Omega$, for some $x\in N$, then $\{Q^x, H^x, NQ\}= \Omega$. If $R^x\in \Omega$, for some $x\in N$, then $\{R^x, H^x, NR\}= \Omega$. If $N\in \Omega$, then $\{N, NQ, NR\}= \Omega$. If none of the three cases does not occur, for $\Omega$, then $\Omega =\{H^x, NQ, NR\}$, for some $x\in N$. So we conclude that $\Omega$ has 3 members, as wanted.

(2) Since N is a minimal normal abelian subgroup of G, we conclude that $H^x$ is a maximal subgroup of G, for all $x\in N$ by Proposition 2.3 and so G does not have any subgroup of order pq. Therefore,

$$\begin{aligned} \mathcal {S}(G)=\{1, G, N, N_1, \ldots , N_{p+1}, H^x:~~x\in N\}, \end{aligned}$$

where $|N_i|=p$, for each i. Since $G=N\rtimes H$ is Frobenius, $\{N_i, N\}$ is a clique with maximum size in $\Gamma (G)$, for each i, as wanted.

(3) Since $G=N\rtimes H\cong (C_p\times C_p)\rtimes C_{q^2}$ is Frobenius with complement H, the group G has $p+1$ subgroups of order p (contained in N), say $N_1,\ldots , N_{p+1}$ and $p^2$ subgroups $H_1^x$ of order q, for each $x\in N$, where $1<H_1<H$. Note that H is a maximal subgroup of G by Proposition 2.3. Therefore, G does have any subgroup of order $pq^2$. Clearly, $H_1^x\le NH_1$, for every $x\in N$ and so $NH_1$ is the unique non-abelian subgroup of G of order $p^2q$. If G has a subgroup K of order pq, then K is not abelian since $C_G(x)=N$, for $1\ne x\in N$ by Exercise 8.5 (5) of [18]. It follows that $q|p-1$, which is contrary to our assumption in this part. Hence the order of a non-trivial proper subgroup of G belongs to $\{p,p^2, q, p^2q, q^2\}$ and so we have

$$\begin{aligned} \mathcal {S}(G)=\{1, G, N, N_1, \ldots , N_{p+1}, H^x, H_1^x, NH_1:~~x\in N\}. \end{aligned}$$

Since $N\cap H^y=H\cap H^x=H_1\cap H_1^x=N_i\cap N_j=1$, for every $y\in N$, $x\in N{\setminus } \{1\}$ and $i\ne j$, we have $\{N_i, N, NH_1\}$ is a clique with maximum size in $\Gamma (G)$, for each i. Also $\{H_1^x, H^x, NH_1\}$ is a clique with maximum, for every $x\in N$. This completes the proof.

(4) The proof is similar to the part (3).

$\square$

Proof of Theorem 1.4:

Since $\omega (G)=2$, G contains two proper subgroups $H_1$ and $H_2$ such that $H_1\cap H_2\ne 1$ and so $\{H_1, H_2, H_1\cap H_2\}$ is a clique in $\Gamma (G)$, which implies that either $H_1<H_2$ or $H_2<H_1$. Without loss of generality, assume that $H_1<H_2$. Since $\omega (G)=2$, we have $|H_1|=p$ is prime, $H_1$ is a maximal subgroup of $H_2$ and $H_2$ is a maximal subgroup of G. Now we claim that $|H_2: H_1|$ and $|G: H_2|$ are primes.

If $H_1\lhd H_2$ and $H_2\lhd G$, then the claim is valid. If $H_1$ is not normal in $H_2$, then $N_{H_2}(H_1)=H_1$ and since $|H_1|$ is prime, we have $H_1\cap H_1^x=1$, for all $x\in H_2{\setminus } H_1$. It follows from Theorem 2.2 that $H_2$ is Frobenius and so there is a normal subgroup N such that $H_2=N\rtimes H_1$. If |N| is not prime, then N has a proper non-trivial subgroup $N_1$ and so $\{N_1, N, H_2\}$ is a clique in $\Gamma (G)$ of size 3, which is a contradiction. Therefore, $|N|=|H_2: H_1|$ is prime. Now if $H_2\lhd G$, then $|G: H_2|$ is prime by maximlity of $H_2$ in G. So assume that $H_2$ is not normal in G. Then, by a similar argument to $H_1\ntriangleleft H_2$, we conclude that G is Frobenius and $|G:H_2|$ is prime. Thus $|G|=|H_1||H_2: H_1||G: H_2|=pqr$, for some primes p, q and r.

First suppose that G is abelian. If p, q and r are distinct, then $G\cong C_{pqr}$ and so by Lemma 4.1(3) we have $\omega (\Gamma (G))=3$, a contradiction. If $p=r\ne q$, then $G\cong C_{p^2q}$ or $C_p\times C_p\times C_q$, which implies that $\omega (\Gamma (G))\ne 2$ by Lemma 4.1(3-4). If $p=q=r$, then $G\cong C_{p^3}, C_{p^2}\times C_p$ or $C_p\times C_p\times C_p$. Since $\omega (G)=2$, we have $G\cong C_{p^3}$ by Lemma 4.1.

Now suppose that G is not abelian. If $p=q=r$, then $|G|=p^3$ and we have a contradiction by Lemma 4.1(5). If p, q and r are distinct, then at least one of Sylow subgroups of G is normal, which implies that $\omega (\Gamma (G))\ge 3$, a contradiction. Finally suppose that $p=r\ne q$. If $Syl_q(G)=\{Q\}$ and $P\in Syl_p(G)$, then $\{P_1, P, P_1Q\}$ is a clique in $\Gamma (G)$, where $P_1$ is a proper non-trivial subgroup of P, again a contradiction. Hence we have $Syl_p(G)=\{P\}$. If $Q\in Syl_q(G)$, then $G=P\rtimes Q$. Since $\omega (\Gamma (G))=2$, we see that P must be a minimal normal subgroup of G and so $P\cong C_p\times C_p$, which implies that Q is a maximal subgroup of G Proposition 2.3. Since Q is not normal in G, we have $N_G(Q)=Q$. It follows $Q\cap Q^g=1$, for every $g\in G{\setminus } Q$ and so G is a Frobenius group. This completes the proof.

The converse follows from Lemmas 4.1(1) and 4.2(2). $\square$

Proposition 4.3

Let G be a finite abelian group. Then $\omega (\Gamma (G))=3$ if and only if G is isomorphic to one of the following groups:

$$\begin{aligned} C_{p^4},\quad C_{p^2q},\quad C_{pqr}, \end{aligned}$$

where p, q, r are distinct primes.

Proof

Assume that $\omega (\Gamma (G))=3$. We consider two cases:

• (i) Suppose that G is a p-group, for some prime p. Since $\omega (\Gamma (G))=3$, we have $|G|\ge p^3$. If $\Phi (G)=1$, then G is elementary abelian and so G has a subgroup isomorphic to $E=C_p\times C_p\times C_p$. It follows from Lemma 4.1(2) that $\omega (\Gamma (E))= p^2+p+1>3$, a contradiction. Hence $\Phi (G)\ne 1.$ Moreover, the number of maximal subgroups of G is $t=\frac{|\frac{G}{\Phi (G)}|-1}{p-1}$, by Lemma 2.6. Therefore, either $t=1$, which follows that $G\cong C_{p^4}$, by Lemma 4.1(1) or G has at least $p+1$ maximal subgroups, say $M_1, M_2,\ldots , M_{p+1}.$ By Lemma 2.1, $\{M_1, M_2,\ldots , M_{p+1}, \Phi (G)\}$ is a clique and so $\omega (\Gamma (G))\ge p+2$, which is impossible.

• (ii) Now suppose that |G| has at least two distinct prime divisors, p and q. Then G has two maximal subgroups $M_1$ and $M_2$ such that $|G:M_1|=p$ and $|G:M_2|=q$. Since $\omega (\Gamma (G))=3$, we have $M_1\cap M_2\ne 1$ and so $\{M_1, M_2, M_1\cap M_2\}$ is a clique in $\Gamma (G)$. Note that G has a maximal subgroup different from $M_1$ and $M_2$, say $M_3$ since $G\ne M_1\cup M_2$. We conclude that $\{M_1, M_2, M_3\}$ is a clique in $\Gamma (G)$. Since $\omega (\Gamma (G))=3$, we have $\cap _{i=1}^3M_i=1$, which follows that $G\hookrightarrow \frac{G}{M_1}\times \frac{G}{M_2}\times \frac{G}{M_3}$. Consequently $|G|=pqr$, where r is prime. By Lemma 4.1(3-4), we have $G\cong C_{pqr}$ or $C_{p^2q}$, as wanted.

The converse of the lemma follows from Lemma 4.1. $\square$

Proposition 4.4

Let G be a finite non-abelian group. Then $\omega (\Gamma (G))=3$ if and only if $G=N\rtimes H$ is Frobenius whose kernel N is the unique minimal normal subgroup of G and we have either

• (1) $N\cong C_p$ and $H\cong C_{q^2}$ or $C_{qr}$ or

• (2) $N\cong C_p\times C_p$, $H\cong C_{q^2}$ and G does not have any subgroup of order pq, where p, q, r are distinct primes.

Proof

Suppose that $\omega (\Gamma (G))=3$. Since G is not cyclic, G has at least three maximal subgroups $M_1, M_2$ and $M_3$. By hypothesis, $\cap _{i=1}^3M_i=1$. If $M_i\lhd G$, for each i, then $|G: M_i|$ is prime, for each i and so G is abelian, a contradiction. Without loss of generality, assume that $M:=M_1$ is not normal in G. Then $N_G(M)=M$ and $|G: M|\ge 3.$ Thus M has at least three conjugates $M, M^x, M^y$, for some $x, y\in G$. If $Core_G(M)\ne 1$, then $\omega (\Gamma (G))\ge 4$, which is a contradiction. So $Core_G(M)=1$, which implies that G is a primitive group. It follows from Theorem 1.1 that G is solvable and by Theorem 2.4, G has a unique minimal normal subgroup N such that $C_G(N)=N$ and $G=N\rtimes M.$ Since N is a principal factor of G, we have N is elementary abelian of order $p^n$, for some prime p, by 5.4.3 of [18]. Since $\omega (\Gamma (G))=3$, we have $n=1$ or 2, by Lemmas 4.1(2) and 2.5. Also note that if $M\cap M^g\ne 1$, for some $g\in G{\setminus } M$, then $\{M, M^g, M\cap M^g, N(M\cap M^g)\}$ is a clique in $\Gamma (G)$, a contradiction. Thus G is a Frobenius group.

Subcase 1. If $n=1$, then $G=N\rtimes M$, where $N\cong C_p$. Since $Aut(C_p)$ is cyclic of order $p-1$, we have M is cyclic of order divisor of $p-1$. It follows from Lemma 2.5(i) that $\omega (\Gamma (M))< \omega (\Gamma (G))=3$. If $\omega (M)=2$, then by Theorem 1.4, we have $M\cong C_{q^3}$, for some prime q. Therefore, M has two subgroups H and K of orders q and $q^2$ respectively and so $\{H, K, M, NH\}$ is a clique, which is impossible. Hence $\omega (\Gamma (M))=1$, which follows that $M\cong C_{qr}$ or $C_{q^2}$, by Remark 1.3, as required.

Subcase 2. If $n=2$, then $G=N\rtimes M$, where $N\cong C_p\times C_p$. Therefore, |M| is not prime, by hypothesis and Theorem 1.4. We conclude that $|\mathcal {S}(M)|\ge 3$. Since $\omega (\Gamma (G))=3$ and $\omega (\Gamma (N))=1$, we have $|\mathcal {S}(M)|\le 3$, by Lemma 2.5(ii). Therefore, $M\cong C_{q^2}$, as wanted. It remains to show that G does not have any (non-abelian) subgroup of order pq.

Suppose, for a contradiction, that G has a subgroup K of order pq. Since $C_G(x)=N$, for every $1\ne x\in N$, by Exercise 8.5 (5) of [18], we have K is non-abelian and so there are subgroups $1<N_1<N$ and $1<M_1<M$ such that $K=N_1\rtimes M_1$. It follows that $\{N_1, N, K, NM_1\}$ is a clique in $\Gamma (G)$ with four elements, which is impossible.

The converse follows from Lemmas 4.2(1) and 4.2(3). $\square$

Proof of Theorem 1.5

The proof follows from Propositions 4.3 and 4.4. $\square$

Proposition 4.5

Let G be a finite abelian group. Then $\omega (\Gamma (G))=4$ if and only if G is isomorphic to one of the follwing groups:

$$\begin{aligned} C_{p^5},~~~~~C_2\times C_2\times C_q,~~~~~C_2\times C_4, \end{aligned}$$

where p and q are primes and q is odd.

Proof

Assume that $\omega (\Gamma (G))=4$. Then, by Remark 1.3 and Lemma 4.1, |G| has at least three prime divisors (not necessarily distinct), say p, q and r. Note that the number of maximal subgroups of G is either one or at least three. So we consider three cases in terms of the number of maximal subgroups of G in the following:

Case 1. If G has at least four maximal subgroups, $M_i$, for $1\le i\le 4$, then $M_i\cap M_j\ne 1$ and since $\omega (\Gamma (G))=4$, we have $\cap _{i=1}^4M_i=1$ and so |G| has at most four prime divisors (not necessarily distinct). Therefore, |G| divides pqrs, for some prime s.

First suppose that $|G|=pqrs$. If all prime divisors of |G| are distinct, then G is cyclic of order pqrs and so $\omega (\Gamma (G))>4$, a contradiction. If $|G|=p^2qr$ such that p, q, r are distinct, then $\{H, P, HQ, HR, PQ, PR\}$ is a clique in $\Gamma (G)$, where $|H|=p$, $P\in Syl_p(G), Q\in Syl_q(G)$ and $R\in Syl_r(G)$, again a contradiction. By a similar argument, we see that $|G|\ne p^2q^2, p^3q, p^4$, where p, q are distinct. So such group G does not exist.

Now suppose that $|G|=pqr$. By the number of maximal subgroups of G, we have G is not cyclic. Also $G\ncong C_p\times C_p\times C_p$, by Lemma 4.1(2). Hence $G\cong C_{p^2}\times C_p$ or $C_p\times C_p\times C_q$. It follows from Lemma 4.1(4) that $p=2$ and q is odd. But the number of maximal subgroups $C_{4}\times C_2$ is 3, a contradiction. Thus $G\cong C_2\times C_2\times C_q$, as wanted.

Case 2. Suppose that G has exactly three maximal subgroups. If G is cyclic, then |G| has three distinct prime divisors and so $G\cong C_{pqr}$. So we have a contradiction, by Lemma 4.1(3) since $\omega (\Gamma (G))=4$. Thus G is not cyclic and then G has a Sylow t-subgroup, which is not cyclic, for some prime t. Without loss of generality, assume $t=p$ and $P\in Syl_p(G)$. Therefore, P (or equivalently G) has at least $p+1$ maximal subgroups. By hypothesis in this case, we have $p=2$ and G must be a 2-group. On the other hand, the number of maximal subgroups of G is $|\frac{G}{\Phi ((G)}|-1$, which implies that $\frac{G}{\Phi ((G)}\cong C_2\times C_2$. Since $|\mathcal {S}(C_2\times C_2)|=5$ and $\omega (\Gamma (G))=4$, we have $\omega (\Gamma (\Phi (G)))=0$, by Lemma 2.5(ii). Thus $|\Phi (G)|=2$ and so $|G|=8$. Hence $G\cong C_4\times C_2$, as desired.

Case 3.Suppose that G has exactly one maximal subgroup. Then G is cyclic of order the power of a prime p and so $G\cong C_{p^5}$, by Lemma 4.1(1). This completes the proof.

The converse is clear, by Lemma 4.1.

$\square$

Proposition 4.6

Let G be a finite non-abelian group. Then $\omega (\Gamma (G))=4$ if and only if G is one of the follwing groups:

• (i) $G\cong D_8,~Q_8.$ or

• (ii) $G=N\rtimes H$ is Frobenius whose kernel N is the (unique) minimal normal subgroup of G such that $N\cong C_p\times C_p$, $H\cong C_{qr}$ and G does not have subgroups of orders pr and pq

Proof

Assume that $\omega (\Gamma (G))=4$. Suppose first that every maximal subgroup is normal in G. Then G is nilpotent. Since G is non-abelian, there is a Sylow p-subgroup P of G such that P is non-abelian, for some prime p. Therefore, $\Phi (P)\ne 1$ and so $\omega (\Gamma (P))\ge m(P)+1\ge p+1+1$, where m(P) is the number of maximal subgroups of P. Thus, by Lemma 2.5(i), we see that $4=\omega (\Gamma (G))\ge \omega (\Gamma (P))\ge 4$, which implies that $G=P$ and then we have $p=2$ and $m(P)=p+1=3$. Now if $M_1, M_2$ and $M_3$ are maximal subgroups of G, then $\{\Phi (G), M_1, M_2, M_3\}$ is a clique with maximum size and so $|\Phi (G)|=2$ and $M_i\cap M_j=\Phi (G)$, for every $i\ne j\le 3$. Since $|G: M_i|=2$, for each i, we have $|G|=8$. Thus $G\cong D_8$ or $Q_8$, as wanted.

Now assume that G has a maximal subgroup M, which is not normal in G. Then $N_G(M)=M$ and $|G:M|\ge 3$. We claim that $Core_G(M)=1$.

Suppose, for a contradiction, that $M_G:=Core_G(M)\ne 1$. If M has at least four conjugates, say $M, M^x, M^y, M^z$, for some $x, y, z\in G$, then $\omega (\Gamma (G))\ge 5$, a contradiction. So we have $|G:M|=3$. It follows that $\frac{G}{M_G}\hookrightarrow S_3$. If $\frac{G}{M_G}\cong S_3$, then by Lemma 2.5(ii), $\omega (\Gamma (G))\ge |\mathcal {S}(S_3)|-1=5$, which is a contradiction. Since 3 divides $|G: M_G|$, we have $M_G=M$ and so $M\lhd G$, a contradiction. This implies that $M_G=1$, as claimed. Thus G is primitive. By Theorems 1.1, G is solvable and by Theorem 2.4, G has a unique minimal normal subgroup N such that $C_G(N)=N$ and $G=N\rtimes M$. It follows that N is elementary abelian p-group, for some prime p. If $|N|\ge p^3$, then N contains a subgroup $E\cong C_p\times C_p\times C_p$ and so $\omega (\Gamma (E))>4$, by Lemma 4.1(2), which is impossible, by Lemma 2.5(i). Thus $|N|=p$ or $p^2$.

If $|N|=p$, then, by Normalizer-Centralizer Theorem we have $\frac{G}{C_G(N)}=\frac{G}{N}\hookrightarrow Aut(C_p)\cong C_{p-1}$ and so M is cyclic. It follows from Lemma 2.5(i) that $\omega (\Gamma (M))<4$. If $\omega (\Gamma (M))=2$ or 3, then by Theorems 1.4 and 4.3, we have $M\cong C_{q^3},~C_{q^2r},~C_{q^4}$ or $C_{qrs}$. Thus M has at least two proper subgroups of different orders, which are divisible by q, say $M_1, M_2$ and so $\{M_1, M_2, NM_1, NM_2, M\}$ is a clique in $\Gamma (G)$, a contradiction. Also if $\omega (\Gamma (M))=1$, then $M\cong C_{q^2}$ or $C_{qr}$, where q, r are distinct primes. Since M is cyclic and maximal subgroup of G, we have $M\cap M^x\lhd \langle M, M^x\rangle =G$, for any $x\in G{\setminus } M$. Now since G has a unique minimal subgroup N, we see that $M\cap M^x=1$, for every $x\in G{\setminus } M$ and then G is Frobenius. Therefore, $G=N\rtimes M$, where $N\cong C_p$ and $M\cong C_{q^2}$ or $C_{qr}$, which follows $\omega (\Gamma (G))=3$ by Theorem 4.4, another contradiction. Finally if $\omega (\Gamma (M))= 0$, then $|M|=q$ is prime and so $G\cong C_p\rtimes C_q$. It follows that $\omega (\Gamma (G))=1$, by Remark 1.3, our final contradiction.

Now suppose that $N\cong C_p\times C_p$. Then $\omega (\Gamma (M))<\omega (\Gamma (G))=4$, by Lemma 2.5(i). Also by Remark 1.3 and Theorem 1.4, $\omega (\Gamma (M))\ne 0$. If $\omega (\Gamma (M))=1$, then $M\cong C_{q^2}, C_{qr}, C_q\times C_q$ or $C_q\rtimes C_r$, where q and r are distinct primes. In two last cases, M (or equivalently $\frac{G}{N}$) has $q+1$ non-trivial proper subgroups and so $\{H, N, K_1, K_2, \ldots , K_{q+1}\}$ is a clique in $\Gamma (G)$, where $1<H<N$ and $K_i$ is a proper subgroup of G containing N, for each i. It follows that $\omega (\Gamma (G))\ge q+3$, a contradiction. If $M\cong C_{q^2}$, then $M\cap M^x\lhd \langle M, M^x\rangle =G$, for any $1\ne x\in N$, we have $M\cap M^x=1$, for every $1\ne x\in N$ and then G is Frobenius. By Theorem 4.4, we have $\omega (\Gamma (G))=3$. Hence $M\cong C_{qr}$ and similarly G is Frobenius, as wanted.

If $\omega (\Gamma (M))=2$ and $\{H_1, H_2\}$ is a clique in $\Gamma (M)$ such that $H_1<H_2$, then $\{H_1, H_2, M, NH_1, NH_2\}$ is a clique in $\Gamma (G))$, which is impossible.

If $\omega (\Gamma (M))=3$ and $\{M_1, M_2, M_3\}$ is a clique in $\Gamma (M))$, then

$\{M_1, M_2, M_3, M, NM_1\}$ is a clique in $\Gamma (G))$, a contradiction. It remains to prove that G does not have subgroups of orders pq and pr.

Suppose, for a contradiction, that G has a subgroup K of order pq. Then there are subgroups $N_1<N$ and $Q\in Syl_q(G)$ such that $K=N_1\rtimes Q$. It follows that $\{N_1, N, K, NQ, NR\}$ is a clique in $\Gamma (G)$, where R is a Sylow r-subgroup of G. This is a contradiction with our assumption. Similarly G does not have any subgroup of order pr.

The converse of the lemma follows from Lemmas 4.1(5) and 4.2(4). $\square$

Proof of Theorem 1.6

The proof follows from Propositions 4.5 and 4.6. $\square$