# On the minimum cut-sets of the power graph of a finite cyclic group

Sanjay Mukherjee  Kamal Lochan Patra  Binod Kumar Sahoo

###### Abstract

The power graph $\mathcal{P}(G)$ of a finite group $G$ is the simple graph
with vertex set $G$, in which two distinct vertices are adjacent if one of
them is a power of the other. For an integer $n\geq 2$, let $C_{n}$ denote the
cyclic group of order $n$ and let $r$ be the number of distinct prime divisors
of $n$. The minimum cut-sets of $\mathcal{P}(C_{n})$ are characterized in [4]
for $r\leq 3$. In this paper, for $r\geq 4$, we identify certain cut-sets of
$\mathcal{P}(C_{n})$ such that any minimum cut-set of $\mathcal{P}(C_{n})$
must be one of them.

Key words: Power graph, Cut-set, Cyclic group, Euler’s totient function
AMS subject classification. 05C25, 05C40

##  1 Introduction

Let $\Gamma$ be a simple graph with vertex set $V.$ A subset $X$ of $V$ is
called a cut-set of $\Gamma$ if the induced subgraph of $\Gamma$ with vertex
set $V\setminus X$ is disconnected. A cut-set $X$ of $\Gamma$ is called a
minimum cut-set if $|X|\leq|Y|$ for any cut-set $Y$ of $\Gamma$. If $V=A\cup
B$ for two nonempty disjoint subsets $A,B$ of $V$ such that there is no edge
of $\Gamma$ containing vertices from both $A$ and $B$, then we say that $A\cup
B$ is a separation of $\Gamma$. Note that $\Gamma$ is disconnected if and only
if there exists a separation of $\Gamma$.

###  1.1 Power graphs

There are various graphs associated with groups which have been studied in the
literature, e.g., Cayley graphs, commuting graphs. The notion of directed
power graph of a group was introduced by Kelarev and Quinn in [13]. The
underlying undirected graph, simply termed as the ‘power graph’ of that group,
was first considered by Chakrabarty et al. in [3]. Several researchers have
then studied both the directed and undirected power graphs of groups from
different viewpoints. We refer to the survey papers [1, 15] and the references
therein for more on these graphs.

The power graph of a finite group $G$, denoted by $\mathcal{P}(G)$, is the
simple graph with vertex set $G$, in which two distinct vertices are adjacent
if one of them is a power of the other. Since the identity element of $G$ is
adjacent to all other vertices, $\mathcal{P}(G)$ is a connected graph of
diameter at most two. Chakrabarty et al. proved that $\mathcal{P}(G)$ is a
complete graph if and only if $G$ is a cyclic group of prime power order [3,
Theorem 2.12] .

Cameron and Ghosh [2] and Mirzargar et. al [19, 20] have studied the
isomorphism problem associated with finite groups and their power graphs. Feng
et al. [12] described the full automorphism group of the power graph of a
finite group. Kirkland et al. [14] derived explicit formulas concerning the
complexity (that is, number of spanning trees) of power graphs of various
finite groups. Graph parameters such as chromatic number [16, 22], metric
dimension [11], strong metric dimension [17, 18] etc. of power graphs of
finite groups have also been studied in the literature. It was proved in [10,
Theorem 5] and [11, Corollary 2.5] that the power graph of a finite group is
perfect, in particular, the clique number and the chromatic number coincide.
Explicit formula for the clique number of the power graph of a finite cyclic
group was obtained in [19, Theorem 2] and [10, Theorem 7].

For a given finite group $G$, characterizing the minimum cut-sets of
$\mathcal{P}(G)$ is an interesting problem. It was proved in [8, Theorem 1.3]
and [9, Corollary 3.4] respectively that, among all finite groups of order
$n$, the power graph $\mathcal{P}(C_{n})$ of the cyclic group $C_{n}$ of order
$n$ has the maximum number of edges and has the largest clique. It is thus
expected that the size of a minimum cut-set of $\mathcal{P}(C_{n})$ would be
larger comparing to the size of the minimum cut-set of the power graph of a
noncyclic group of order $n$. A few cut-sets of $\mathcal{P}(C_{n})$ were
identified in [4, 6, 21] which appeared to be minimum cut-sets for some values
for $n$. In this paper, we identify certain cut-sets of $\mathcal{P}(C_{n})$
such that one of them must be a minimum cut-set for any given $n$.

###  1.2 Cut-sets of $\mathcal{P}(C_{n})$

Throughout the paper, $n\geq 2$ is an integer and $r$ denotes the number of
distinct prime divisors of $n$. We write the prime power factorization of $n$
as

$n=p_{1}^{n_{1}}p_{2}^{n_{2}}\cdots p_{r}^{n_{r}},$

where $n_{1},n_{2},\ldots,n_{r}$ are positive integers and
$p_{1},p_{2},\ldots,p_{r}$ are primes with $p_{1}<p_{2}<\cdots<p_{r}$. For a
positive integer $m$, we denote by $[m]$ the set $\\{1,2,\dots,m\\}$.

For every positive divisor $d$ of $n$, there is a unique (cyclic) subgroup of
$C_{n}$ of order $d$. It follows that two distinct elements $x,y$ of $C_{n}$
are adjacent in $\mathcal{P}(C_{n})$ if and only if $o(x)\mid o(y)$ or
$o(y)\mid o(x)$, where $o(z)$ denotes the order of an element $z\in C_{n}$.
The lattice of all subgroups of $C_{n}$ with respect to inclusion is
isomorphic to the lattice of all divisors of $n$ with respect to divisibility.
If $H_{1},H_{2},\ldots,H_{k}$ are subgroups of $C_{n}$, then the number of
elements in the intersection $H_{1}\cap H_{2}\cap\ldots\cap H_{k}$ is equal to
the greatest common divisor of the integers $|H_{1}|,|H_{2}|,\ldots,|H_{k}|$.

For every positive divisor $d$ of $n$, we denote by $E_{d}$ the set of all
elements of $C_{n}$ whose order is $d$ and by $S_{d}$ the set of all elements
of $C_{n}$ whose order divides $d$. Then $S_{d}$ is the unique (cyclic)
subgroup of $C_{n}$ of order $d$ and $E_{d}$ is precisely the set of
generators of $S_{d}$. Thus $\left|S_{d}\right|=d$ and
$\left|E_{d}\right|=\phi(d)$, where $\phi$ is the Euler’s totient function.
Any two distinct elements of $E_{d}$ are adjacent in $\mathcal{P}(C_{n})$. Any
cut-set of $\mathcal{P}(C_{n})$ must contain the sets $E_{n}$ and $E_{1}$, as
each element from these two sets is adjacent with all other vertices of
$\mathcal{P}(C_{n})$.

#### Cut-sets of the first type

Let $r\geq 2$, $a\in[r]$ and $s\in[n_{a}]$. We denote by $Q_{a}^{s}$ the union
of the subgroups $S_{\frac{n}{p_{i}p_{a}^{s}}}$ of $C_{n}$, where
$i\in[r]\setminus\\{a\\}$. Define the subset $Z_{a}^{s}$ of $C_{n}$ by

$Z_{a}^{s}:=E_{n}\cup E_{\frac{n}{p_{a}}}\cup
E_{\frac{n}{p_{a}^{2}}}\cup\ldots\cup E_{\frac{n}{p_{a}^{s-1}}}\cup
Q_{a}^{s}.$

In Section 3.1, we prove that $Z_{a}^{s}$ is a cut-set of
$\mathcal{P}(C_{n})$.

#### Cut-sets of the second type

Let $r\geq 3$, $a,b\in[r]$ with $a\neq b$, $s\in[n_{a}]$ and $t\in[n_{b}]$. We
denote by $K_{a,b}^{s,t}$ the set of all the nongenerators of the cyclic
subgroup $S_{\frac{n}{p_{a}^{s}p_{b}^{t}}}$ of $C_{n}$ and by $H_{a,b}^{s,t}$
the union of the mutually disjoint sets $E_{\frac{n}{p_{a}^{i}p_{b}^{j}}}$,
where $0\leq i\leq s$, $0\leq j\leq t$ and $(i,j)\neq(s,t)$. Define the subset
$X_{a,b}^{s,t}$ of $C_{n}$ by

$X_{a,b}^{s,t}:=H_{a,b}^{s,t}\bigcup K_{a,b}^{s,t}.$

In Section 3.2, we prove that $X_{a,b}^{s,t}$ is a cut-set of
$\mathcal{P}(C_{n})$.

###  1.3 Main result

If $r=1$, then $n$ is a prime power and so $\mathcal{P}(C_{n})$ is a complete
graph. In this case, there is no cut-set of $\mathcal{P}(C_{n})$.

Suppose that $r=2$. Then $n=p_{1}^{n_{1}}p_{2}^{n_{2}}$. If $p_{1}\geq 3$,
then $2\phi(p_{1})>p_{1}$ and so $Z_{2}^{1}$ is the only minimum cut-set of
$\mathcal{P}(C_{n})$ by [4, Proposition 4.4]. If $p_{1}=2$, then it follows
from the proof of [4, Theorem 1.3(iii)] that the number of distinct minimum
cut-sets of $\mathcal{P}(C_{n})$ is $n_{2}$, namely the cut-sets $Z_{2}^{s}$
for $s\in[n_{2}]$.

Suppose that $r=3$. Then $n=p_{1}^{n_{1}}p_{2}^{n_{2}}p_{3}^{n_{3}}$. If
$p_{1}\geq 3$, then $2\phi(p_{1}p_{2})>p_{1}p_{2}$ and so $Z_{3}^{1}$ is the
only minimum cut-set of $\mathcal{P}(C_{n})$ by [4, Proposition 4.4]. If
$p_{1}=2$, then it follows from the proof of [4, Theorem 1.5] that
$Z_{3}^{n_{3}}$ is the only minimum cut-set of $\mathcal{P}(C_{n})$.

For $r\geq 4$, we study the possible minimum cut-sets of $\mathcal{P}(C_{n})$
and prove the following theorem in Section 5.

######  Theorem 1.1.

Let $r\geq 4$ and $X$ be a minimum cut-set of $\mathcal{P}(C_{n})$. Then
$X=Z_{r}^{1}$; or $X=Z_{a}^{n_{a}}$ for some $a\in[r]$ with $n_{a}\geq 2$; or
$X=X_{a,b}^{s,t}$ for some $a,b\in[r]$ with $a\neq b$, $s\in[n_{a}]$ and
$t\in[n_{b}]$.

##  2 Euler’s totient function

We continue with the notation introduced in the previous section. We have
$\phi\left(p^{k}\right)=p^{k-1}(p-1)=p^{k-1}\phi(p)$ for any prime $p$ and
positive integer $k$. Since $\phi$ is a multiplicative function, we have
$\phi(n)=\phi\left(p_{1}^{n_{1}}\right)\phi\left(p_{2}^{n_{2}}\right)\cdots\left(p_{r}^{n_{r}}\right)$.
For $i,k\in[r]$ with $i\leq k$, we have

$\left|E_{\frac{n}{p_{i}}}\right|=\phi\left(\frac{n}{p_{i}}\right)\geq\phi\left(\frac{n}{p_{k}}\right)=\left|E_{\frac{n}{p_{k}}}\right|.$
(1)

Let $I$ be a nonempty subset of $[r]$ with $|I|=t$. Then by [5, Lemma 3.1], we
have

$(t+1)\phi\left(\underset{i\in I}{\prod}p_{i}\right)\geq\underset{i\in
I}{\prod}p_{i},$ (2)

where equality holds if and only if $(t,I)=(1,\\{1\\})$ with $p_{1}=2$ or
$(t,I)=(2,\\{1,2\\})$ with $p_{1}=2$, $p_{2}=3$. By expanding
$\phi\left(\underset{i\in I}{\prod}p_{i}\right)=\underset{i\in
I}{\prod}(p_{i}-1)$, it follows that

$\underset{i\in I}{\prod}p_{i}-\phi\left(\underset{i\in
I}{\prod}p_{i}\right)=\underset{i=I}{\sum}\frac{\eta}{p_{i}}-\underset{i<j}{\underset{i,j\in
I}{\sum}}\frac{\eta}{p_{i}p_{j}}+\underset{i<j<k}{\underset{i,j,k\in
I}{\sum}}\frac{\eta}{p_{i}p_{j}p_{k}}-\cdots+(-1)^{t-1},$ (3)

where $\eta=\underset{i\in I}{\prod}p_{i}$. We next calculate the cardinality
of certain subsets of $C_{n}$ which are needed in the subsequent sections.

######  Lemma 2.1.

Let $a\in[r]$ and $0\leq k\leq s\leq n_{a}$. Then

$\underset{l=k}{\overset{s}{\sum}}\left|E_{\frac{n}{p_{a}^{l}}}\right|=\underset{l=k}{\overset{s}{\sum}}\phi\left(\frac{n}{p_{a}^{l}}\right)=\begin{cases}\frac{n}{p_{1}\cdots
p_{r}}\times\frac{1}{p_{a}^{k-1}}\times\phi\left(\frac{p_{1}\cdots
p_{r}}{p_{a}}\right),&\text{if $s=n_{a}$}\\\ \frac{n}{p_{1}\cdots
p_{r}}\times\frac{1}{p_{a}^{k-1}}\times\phi\left(\frac{p_{1}\cdots
p_{r}}{p_{a}}\right)\left(1-\frac{1}{p_{a}^{s-k+1}}\right),&\text{if
$s<n_{a}$}\end{cases}.$

###### Proof.

We have
$\underset{l=k}{\overset{s}{\sum}}\phi\left(\frac{n}{p_{a}^{l}}\right)=\phi\left(\frac{n}{p_{a}^{n_{a}}}\right)\left[\underset{l=k}{\overset{s}{\sum}}\phi\left(p_{a}^{n_{a}-l}\right)\right]$.
Since $\phi\left(\frac{n}{p_{a}^{n_{a}}}\right)=\frac{n}{p_{1}p_{2}\cdots
p_{r}}\times\frac{1}{p_{a}^{n_{a}-1}}\times\phi\left(\frac{p_{1}p_{2}\cdots
p_{r}}{p_{a}}\right)$ and

$\underset{l=k}{\overset{s}{\sum}}\phi\left(p_{a}^{n_{a}-l}\right)=\underset{i=n_{a}-s}{\overset{n_{a}-k}{\sum}}\phi(p_{a}^{i})=\left\\{\begin{array}[]{ll}p_{a}^{n_{a}-k},&\text{if
}s=n_{a}\\\ p_{a}^{n_{a}-k}\left(1-\frac{1}{p_{a}^{s-k+1}}\right),&\text{if
}s<n_{a},\\\ \end{array}\right.$

the lemma follows. ∎

######  Lemma 2.2.

Let $a,b\in[r]$ with $a\neq b$, $0\leq s\leq n_{a}$ and $0\leq t\leq n_{b}$.
Then

$\underset{k=s}{\overset{n_{a}}{\sum}}\;\underset{l=t}{\overset{n_{b}}{\sum}}\left|E_{\frac{n}{p_{a}^{k}p_{b}^{l}}}\right|=\phi\left(\frac{n}{p_{a}^{n_{a}}p_{b}^{n_{b}}}\right)p_{a}^{n_{a}-s}p_{b}^{n_{b}-t}.$

###### Proof.

We have
$\underset{k=s}{\overset{n_{a}}{\sum}}\;\underset{l=t}{\overset{n_{b}}{\sum}}\left|E_{\frac{n}{p_{a}^{k}p_{b}^{l}}}\right|=\underset{k=s}{\overset{n_{a}}{\sum}}\;\underset{l=t}{\overset{n_{b}}{\sum}}\phi\left(\frac{n}{p_{a}^{k}p_{b}^{l}}\right)=\phi\left(\frac{n}{p_{a}^{n_{a}}p_{b}^{n_{b}}}\right)\left[\underset{k=s}{\overset{n_{a}}{\sum}}\phi\left(p_{a}^{n_{a}-k}\right)\right]\left[\underset{l=t}{\overset{n_{b}}{\sum}}\phi\left(p_{b}^{n_{b}-l}\right)\right]$.
Then the lemma follows as
$\underset{k=s}{\overset{n_{a}}{\sum}}\phi\left(p_{a}^{n_{a}-k}\right)=p_{a}^{n_{a}-s}$
and
$\underset{l=t}{\overset{n_{b}}{\sum}}\phi\left(p_{b}^{n_{b}-l}\right)=p_{b}^{n_{b}-t}$.
∎

######  Lemma 2.3.

For $a\in[r]$ and $s\in[n_{a}]$, let $Q_{a}^{s}$ be the union of the subgroups
$S_{\frac{n}{p_{i}p_{a}^{s}}}$ of $C_{n}$, where $i\in[r]\setminus\\{a\\}$.
Then

$\left|Q_{a}^{s}\right|=\frac{n}{p_{1}p_{2}\cdots
p_{r}}\times\frac{1}{p_{a}^{s-1}}\times\left[\frac{p_{1}p_{2}\cdots
p_{r}}{p_{a}}-\phi\left(\frac{p_{1}p_{2}\cdots p_{r}}{p_{a}}\right)\right].$

###### Proof.

Consider the subgroup $S_{\frac{n}{p_{a}^{s}}}$ of $C_{n}$ containing
$Q_{a}^{s}$. Let $\widetilde{Q_{a}^{s}}$ denote the complement of $Q_{a}^{s}$
in $S_{\frac{n}{p_{a}^{s}}}$. If $x\in S_{\frac{n}{p_{a}^{s}}}$ and
$o(x)=\frac{n}{p_{a}^{k}}$ for some $k$ with $s\leq k\leq n_{a}$, then
$x\in\widetilde{Q_{a}^{s}}$. Conversely, if $y\in\widetilde{Q_{a}^{s}}$, then
$o(y)$ must be divisible by $p_{i}^{n_{i}}$ for every
$i\in[r]\setminus\\{a\\}$ and so $o(y)$ is of the form $\frac{n}{p_{a}^{k}}$,
where $s\leq k\leq n_{a}$.

Thus $\widetilde{Q_{a}^{s}}=E_{\frac{n}{p_{a}^{s}}}\cup
E_{\frac{n}{p_{a}^{s+1}}}\cup\cdots\cup E_{\frac{n}{p_{a}^{n_{a}}}}$, which is
a disjoint union. Using Lemma 2.1, we have
$|\widetilde{Q_{a}^{s}}|=\underset{l=s}{\overset{n_{a}}{\sum}}\phi\left(\frac{n}{p_{a}^{l}}\right)=\frac{n}{p_{1}p_{2}\cdots
p_{r}}\times\frac{1}{p_{a}^{s-1}}\times\phi\left(\frac{p_{1}p_{2}\cdots
p_{r}}{p_{a}}\right)$. Hence
$|Q_{a}^{s}|=\left|S_{\frac{n}{p_{a}^{s}}}\right|-|\widetilde{Q_{a}^{s}}|=\frac{n}{p_{1}p_{2}\cdots
p_{r}}\times\frac{1}{p_{a}^{s-1}}\times\left[\frac{p_{1}p_{2}\cdots
p_{r}}{p_{a}}-\phi\left(\frac{p_{1}p_{2}\cdots p_{r}}{p_{a}}\right)\right].$ ∎

######  Lemma 2.4.

Let $r\geq 3$. If $a,b\in[r]$ with $a<b$, then
$\left|Q_{a}^{1}\right|>\left|Q_{b}^{1}\right|$. As a consequence,
$\left|Z_{a}^{1}\right|>\left|Z_{b}^{1}\right|$.

###### Proof.

Using Lemma 2.3, we get
$\left|Q_{a}^{1}\right|-\left|Q_{b}^{1}\right|=\frac{n}{p_{1}p_{2}\cdots
p_{r}}\times(p_{b}-p_{a})\left[\frac{p_{1}p_{2}\cdots
p_{r}}{p_{a}p_{b}}-\phi\left(\frac{p_{1}p_{2}\cdots
p_{r}}{p_{a}p_{b}}\right)\right]$. Since $a<b$, we have $p_{a}<p_{b}$. As
$r\geq 3$, it follows that $\left|Q_{a}^{1}\right|>\left|Q_{b}^{1}\right|$.
Then
$\left|Z_{a}^{1}\right|=|E_{n}|+\left|Q_{a}^{1}\right|>|E_{n}|+\left|Q_{b}^{1}\right|=\left|Z_{b}^{1}\right|$.
∎

######  Lemma 2.5.

Let $r\geq 3$ and $a,b\in[r]$ such that $a\neq b$ and $p_{b}>2$. If $T$ is the
union of the $r-2$ subgroups $S_{\frac{n}{p_{b}p_{j}}}$ of $C_{n}$ with
$j\in[r]\setminus\\{a,b\\}$, then
$\left|E_{\frac{n}{p_{a}}}\right|+|T|>\left|Q_{r}^{1}\right|$.

###### Proof.

Note that the union of $T$ and $S_{\frac{n}{p_{a}p_{b}}}$ is $Q_{b}^{1}$. Let
$\widetilde{T}$ be the complement of $T$ in $Q_{b}^{1}$. Then $\widetilde{T}$
is a subset of $S_{\frac{n}{p_{a}p_{b}}}$. Further, $\widetilde{T}$ is
precisely union of the mutually disjoint sets
$E_{\frac{n}{p_{a}^{k}p_{b}^{l}}}$, where $1\leq k\leq n_{a}$, $1\leq l\leq
n_{b}$. By Lemma 2.2, we get
$|\widetilde{T}|=\phi\left(\frac{n}{p_{a}^{n_{a}}p_{b}^{n_{b}}}\right)p_{a}^{n_{a}-1}p_{b}^{n_{b}-1}=\frac{n}{p_{1}p_{2}\cdots
p_{r}}\times\phi\left(\frac{p_{1}p_{2}\cdots p_{r}}{p_{a}p_{b}}\right)$. We
have

$\left|E_{\frac{n}{p_{a}}}\right|=\phi\left(\frac{n}{p_{a}}\right)\geq\frac{n}{p_{1}p_{2}\cdots
p_{r}}\times\frac{\phi(p_{1}p_{2}\cdots
p_{r})}{p_{a}}=|\widetilde{T}|\times\frac{\phi(p_{a}p_{b})}{p_{a}}.$

If $b=r$, then $p_{b}\geq 5$ as $r\geq 3$. In this case,
$|\widetilde{T}|\times\frac{\phi(p_{a}p_{b})}{p_{a}}>|\widetilde{T}|$ and so
$\left|E_{\frac{n}{p_{a}}}\right|+|T|>|\widetilde{T}|+|T|=|Q_{r}^{1}|$. If
$b<r$, then
$|\widetilde{T}|\times\frac{\phi(p_{a}p_{b})}{p_{a}}\geq|\widetilde{T}|$ as
$p_{b}>2$ and so
$\left|E_{\frac{n}{p_{a}}}\right|+|T|\geq|\widetilde{T}|+|T|=|Q_{b}^{1}|>\left|Q_{r}^{1}\right|$
by Lemma 2.4. ∎

######  Lemma 2.6.

Let $a,b\in[r]$ with $a\neq b$, $s\in[n_{a}]$ and let $Q_{a,b}^{s}$ be the
union of the subgroups $S_{\frac{n}{p_{i}p_{a}^{s}}}$ of $C_{n}$, where
$i\in[r]\setminus\\{a,b\\}$. Then

$\left|Q_{a,b}^{s}\right|=\frac{n}{p_{1}p_{2}\cdots
p_{r}}\times\frac{p_{b}}{p_{a}^{s-1}}\times\left[\frac{p_{1}p_{2}\cdots
p_{r}}{p_{a}p_{b}}-\phi\left(\frac{p_{1}p_{2}\cdots
p_{r}}{p_{a}p_{b}}\right)\right].$

###### Proof.

Consider the subgroup $S_{\frac{n}{p_{a}^{s}}}$ of $C_{n}$ containing
$Q_{a,b}^{s}$. Let $\widetilde{Q_{a,b}^{s}}$ denote the complement of
$Q_{a,b}^{s}$ in $S_{\frac{n}{p_{a}^{s}}}$. Then $\widetilde{Q_{a,b}^{s}}$ is
a disjoint union of the sets $E_{\frac{n}{p_{a}^{k}p_{b}^{l}}}$, where $s\leq
k\leq n_{a}$ and $0\leq l\leq n_{b}$. Using Lemma 2.2, we get

$\displaystyle|\widetilde{Q_{a,b}^{s}}|=\phi\left(\frac{n}{p_{a}^{n_{a}}p_{b}^{n_{b}}}\right)p_{a}^{n_{a}-s}p_{b}^{n_{b}}=\frac{n}{p_{1}p_{2}\cdots
p_{r}}\times\frac{p_{b}}{p_{a}^{s-1}}\times\phi\left(\frac{p_{1}p_{2}\cdots
p_{r}}{p_{a}p_{b}}\right).$

Hence
$|Q_{a,b}^{s}|=\left|S_{\frac{n}{p_{a}^{s}}}\right|-|\widetilde{Q_{a,b}^{s}}|=\frac{n}{p_{1}p_{2}\cdots
p_{r}}\times\frac{p_{b}}{p_{a}^{s-1}}\times\left[\frac{p_{1}p_{2}\cdots
p_{r}}{p_{a}p_{b}}-\phi\left(\frac{p_{1}p_{2}\cdots
p_{r}}{p_{a}p_{b}}\right)\right].$ ∎

######  Lemma 2.7.

$\phi\left(\frac{n}{p_{j}}\right)>\frac{n}{p_{j}p_{r}}-\phi\left(\frac{n}{p_{j}p_{r}}\right)$
for $j\in[r-1]$.

###### Proof.

Let
$\mu:=\phi\left(\frac{n}{p_{j}}\right)+\phi\left(\frac{n}{p_{j}p_{r}}\right)=\phi\left(\frac{n}{p_{j}^{n_{j}}p_{r}^{n_{r}}}\right)\phi\left(p_{j}^{n_{j}-1}\right)\left[\phi\left(p_{r}^{n_{r}}\right)+\phi\left(p_{r}^{n_{r}-1}\right)\right]$.
We show that $\mu>\frac{n}{p_{j}p_{r}}$. Since
$\phi\left(\frac{n}{p_{j}^{n_{j}}p_{r}^{n_{r}}}\right)=\frac{n}{p_{1}p_{2}\cdots
p_{r}}\times\frac{1}{p_{j}^{n_{j}-1}p_{r}^{n_{r}-1}}\times\phi\left(\frac{p_{1}p_{2}\cdots
p_{r}}{p_{j}p_{r}}\right)$ and

$\displaystyle\phi\left(p_{j}^{n_{j}-1}\right)\left[\phi\left(p_{r}^{n_{r}}\right)+\phi\left(p_{r}^{n_{r}-1}\right)\right]$
$\displaystyle=\begin{cases}p_{j}^{n_{j}-2}p_{r}^{n_{r}-2}(p_{r}+1)\phi(p_{j}p_{r}),&\text{if
$n_{j}\geq 2$, $n_{r}\geq 2$}\\\ p_{j}^{n_{j}-2}p_{r}\phi(p_{j}),&\text{if
$n_{j}\geq 2$, $n_{r}=1$}\\\ p_{r}^{n_{r}-2}(p_{r}+1)\phi(p_{r}),&\text{if
$n_{j}=1$, $n_{r}\geq 2$}\\\ p_{r},&\text{if $n_{j}=1=n_{r}$},\end{cases}$

we get

$\displaystyle\mu$ $\displaystyle=\begin{cases}\frac{n}{p_{1}p_{2}\cdots
p_{r}}\times(p_{r}+1)\times\frac{\phi\left(p_{1}p_{2}\cdots
p_{r}\right)}{p_{j}p_{r}},&\text{if $n_{j}\geq 2$, $n_{r}\geq 2$}\\\
\frac{n}{p_{1}p_{2}\cdots
p_{r}}\times\frac{p_{r}}{p_{j}}\times\phi\left(\frac{p_{1}p_{2}\cdots
p_{r}}{p_{r}}\right),&\text{if $n_{j}\geq 2$, $n_{r}=1$}\\\
\frac{n}{p_{1}p_{2}\cdots
p_{r}}\times\frac{p_{r}+1}{p_{r}}\times\phi\left(\frac{p_{1}p_{2}\cdots
p_{r}}{p_{j}}\right),&\text{if $n_{j}=1$, $n_{r}\geq 2$}\\\
\frac{n}{p_{1}p_{2}\cdots p_{r}}\times
p_{r}\times\phi\left(\frac{p_{1}p_{2}\cdots
p_{r}}{p_{j}p_{r}}\right),&\text{if $n_{j}=1=n_{r}$}\end{cases}$
$\displaystyle>\frac{n}{p_{1}p_{2}\cdots p_{r}}\times\frac{p_{1}p_{2}\cdots
p_{r}}{p_{j}p_{r}}=\frac{n}{p_{j}p_{r}}.$

The strict inequality in the above follows from (2) using the fact that
$p_{r}\geq r+1$. ∎

######  Lemma 2.8.

Let $I_{1}$ be a nonempty proper subset of $[r]$, $a\in[r]\setminus I_{1}$ and
$I_{2}=[r]\setminus(I_{1}\cup\\{a\\})$. If $K$ is the union of the subgroups
$S_{\frac{n}{p_{i}p_{a}}}$ of $C_{n}$ for $i\in I_{1}$, then

$|K|=\frac{n}{p_{1}p_{2}\cdots p_{r}}\times\underset{j\in
I_{2}}{\prod}p_{j}\times\left[\underset{i\in
I_{1}}{\prod}p_{i}-\phi\left(\underset{i\in I_{1}}{\prod}p_{i}\right)\right],$

where $\underset{j\in I_{2}}{\prod}p_{j}=1$ if $I_{2}$ is the empty set.

###### Proof.

Let $|I_{1}|=t$, $\alpha:=\underset{i\in I_{1}}{\prod}p_{i}$ and
$\beta:=\underset{k\in I_{2}}{\prod}p_{k}$. Since $K=\underset{i\in
I_{1}}{\bigcup}S_{\frac{n}{p_{i}p_{a}}}$, we get

$\displaystyle\left|K\right|$ $\displaystyle=\underset{i\in
I_{1}}{\sum}\left|S_{\frac{n}{p_{i}p_{a}}}\right|-\underset{i<j}{\underset{i,j\in
I_{1}}{\sum}}\left|S_{\frac{n}{p_{i}p_{a}}}\bigcap
S_{\frac{n}{p_{j}p_{a}}}\right|+\cdots+(-1)^{t-1}\left|\underset{i\in
I_{1}}{\bigcap}S_{\frac{n}{p_{i}p_{a}}}\right|$ $\displaystyle=\underset{i\in
I_{1}}{\sum}\frac{n}{p_{i}p_{a}}-\underset{i<j}{\underset{i,j\in
I_{1}}{\sum}}\frac{n}{p_{i}p_{j}p_{a}}+\cdots+(-1)^{t-1}\frac{n}{\alpha
p_{a}}$ $\displaystyle=\frac{n}{p_{1}p_{2}\cdots
p_{r}}\times\beta\times\left[\underset{i\in
I_{1}}{\sum}\frac{\alpha}{p_{i}}-\underset{i<j}{\underset{i,j\in
I_{1}}{\sum}}\frac{\alpha}{p_{i}p_{j}}+\cdots+(-1)^{t-1}\right]$
$\displaystyle=\frac{n}{p_{1}p_{2}\cdots
p_{r}}\times\beta\times[\alpha-\phi(\alpha)],$

where the last equality holds using (3). ∎

##  3 The cut-sets $Z_{a}^{s}$ and $X_{a,b}^{s,t}$

For a nonempty proper subset $X$ of $C_{n}$, we denote by $\overline{X}$ the
complement of $X$ in $C_{n}$ and by $\mathcal{P}(\overline{X})$ the induced
subgraph of $\mathcal{P}(C_{n})$ with vertex set $\overline{X}$.

###  3.1 The cut-sets $Z_{a}^{s}$

Let $r\geq 2$, $a\in[r]$ and $s\in[n_{a}]$. Recall that $Z_{a}^{s}=E_{n}\cup
E_{\frac{n}{p_{a}}}\cup E_{\frac{n}{p_{a}^{2}}}\cup\ldots\cup
E_{\frac{n}{p_{a}^{s-1}}}\cup Q_{a}^{s}$, where $Q_{a}^{s}$ is the union of
the subgroups $S_{\frac{n}{p_{i}p_{a}^{s}}}$ of $C_{n}$ for
$i\in[r]\setminus\\{a\\}$.

######  Proposition 3.1.

For $r\geq 2$, $Z_{a}^{s}$ is a cut-set of $\mathcal{P}(C_{n})$.

###### Proof.

Take $A=E_{\frac{n}{p_{a}^{s}}}\cup E_{\frac{n}{p_{a}^{s+1}}}\cup\ldots\cup
E_{\frac{n}{p_{a}^{n_{a}}}}$ and $B=C_{n}\setminus(Z_{a}^{s}\cup A)$. Then
$A,B$ are nonempty disjoint subsets of $\overline{Z_{a}^{s}}$ and $A\cup
B=\overline{Z_{a}^{s}}$.

For $x\in\overline{Z_{a}^{s}}$, the order of $x$ is of the form
$p_{1}^{l_{1}}\cdots p_{a}^{l_{a}}\cdots p_{r}^{l_{r}}$, where $0\leq
l_{i}\leq n_{i}$ for $i\in[r]$. Note that $x\in A$ if and only if
$l_{i}=n_{i}$ for every $i\in[r]\setminus\\{a\\}$ and
$l_{a}\in\\{0,1,\dots,n_{a}-s\\}$. On the other hand, $x\in B$ if and only if
$l_{i}\neq n_{i}$ for at least one $i\in[r]\setminus\\{a\\}$ and
$l_{a}\in\\{n_{a}-s+1,\ldots,n_{a}\\}$. It follows that the order of an
element of $A$ does not divide the order of any element of $B$ and vice versa.
So there is no edge of $\mathcal{P}(C_{n})$ containing vertices from both $A$
and $B$. Thus $A\cup B$ is a separation of $\mathcal{P}(\overline{Z_{a}^{s}})$
and hence $Z_{a}^{s}$ is a cut-set of $\mathcal{P}(C_{n})$. ∎

The following is a consequence of Proposition 3.1.

######  Corollary 3.2.

If $r\geq 2$ and $X$ is a minimum cut-set of $\mathcal{P}(C_{n})$, then
$|X|\leq|Z_{a}^{s}|$ for every $a\in[r]$ and $s\in[n_{a}]$.

######  Proposition 3.3.

$|Z_{a}^{s}|=\phi(n)+\frac{n}{p_{1}p_{2}\cdots
p_{r}}\times\frac{1}{p_{a}^{s-1}}\times\left[\frac{p_{1}p_{2}\cdots
p_{r}}{p_{a}}+\phi\left(\frac{p_{1}p_{2}\cdots
p_{r}}{p_{a}}\right)\left(p_{a}^{s-1}-2\right)\right]$.

###### Proof.

Note that $Z_{a}^{s}$ is a disjoint union of the sets
$E_{n},E_{\frac{n}{p_{a}}},E_{\frac{n}{p_{a}^{2}}},\ldots,E_{\frac{n}{p_{a}^{s-1}}}$
and $Q_{a}^{s}$. We have $|E_{n}|=\phi(n)$. By Lemmas 2.1 and 2.3, we get

$\underset{l=1}{\overset{s-1}{\sum}}\left|E_{\frac{n}{p_{a}^{l}}}\right|=\frac{n}{p_{1}p_{2}\cdots
p_{r}}\times\frac{1}{p_{a}^{s-1}}\times\phi\left(\frac{p_{1}\cdots
p_{r}}{p_{a}}\right)\left(p_{a}^{s-1}-1\right)$

and

$|Q_{a}^{s}|=\frac{n}{p_{1}p_{2}\cdots
p_{r}}\times\frac{1}{p_{a}^{s-1}}\times\left[\frac{p_{1}\cdots
p_{r}}{p_{a}}-\phi\left(\frac{p_{1}\cdots p_{r}}{p_{a}}\right)\right].$

It then follows that $|Z_{a}^{s}|=\phi(n)+\frac{n}{p_{1}p_{2}\cdots
p_{r}}\times\frac{1}{p_{a}^{s-1}}\times\left[\frac{p_{1}p_{2}\cdots
p_{r}}{p_{a}}+\phi\left(\frac{p_{1}p_{2}\cdots
p_{r}}{p_{a}}\right)\left(p_{a}^{s-1}-2\right)\right]$. ∎

######  Proposition 3.4.

Let $r\geq 3$, $a\in[r]$ and $n_{a}\geq 2$. Then the following hold:

  1. (i)

If $2\phi\left(\frac{p_{1}p_{2}\cdots
p_{r}}{p_{a}}\right)>\frac{p_{1}p_{2}\cdots p_{r}}{p_{a}}$, then
$\left|Z_{a}^{1}\right|<\left|Z_{a}^{2}\right|<\cdots<\left|Z_{a}^{n_{a}}\right|$.

  2. (ii)

If $2\phi\left(\frac{p_{1}p_{2}\cdots
p_{r}}{p_{a}}\right)<\frac{p_{1}p_{2}\cdots p_{r}}{p_{a}}$, then
$\left|Z_{a}^{1}\right|>\left|Z_{a}^{2}\right|>\cdots>\left|Z_{a}^{n_{a}}\right|$.

###### Proof.

Since $n_{a}\geq 2$, we have $n_{a}-1\geq 1$. For
$s\in\\{1,2,\ldots,n_{a}-1\\}$, it can be calculated using Proposition 3.3
that

$\displaystyle\left|Z_{a}^{s}\right|-\left|Z_{a}^{s+1}\right|$
$\displaystyle=\frac{n}{p_{1}\cdots
p_{r}}\times\left(\frac{1}{p_{a}^{s-1}}-\frac{1}{p_{a}^{s}}\right)\left[\frac{p_{1}p_{2}\cdots
p_{r}}{p_{a}}-2\phi\left(\frac{p_{1}p_{2}\cdots p_{r}}{p_{a}}\right)\right].$

Since $r\geq 3$, we have $2\phi\left(\frac{p_{1}p_{2}\cdots
p_{r}}{p_{a}}\right)\neq\frac{p_{1}p_{2}\cdots p_{r}}{p_{a}}$ and so the
proposition follows. ∎

###  3.2 The cut-sets $X_{a,b}^{s,t}$

Let $r\geq 3$, $a,b\in[r]$ with $a\neq b$, $s\in[n_{a}]$ and $t\in[n_{b}]$.
Recall that $X_{a,b}^{s,t}=H_{a,b}^{s,t}\bigcup K_{a,b}^{s,t}$, where
$K_{a,b}^{s,t}$ is the set of all the nongenerators of the cyclic subgroup
$S_{\frac{n}{p_{a}^{s}p_{b}^{t}}}$ of $C_{n}$ and $H_{a,b}^{s,t}$ is the union
of the mutually disjoint sets $E_{\frac{n}{p_{a}^{i}p_{b}^{j}}}$ with $0\leq
i\leq s$, $0\leq j\leq t$ and $(i,j)\neq(s,t)$. The set $E_{n}$ corresponds to
$(i,j)=(0,0)$.

######  Proposition 3.5.

For $r\geq 3$, $X_{a,b}^{s,t}$ is a cut-set of $\mathcal{P}(C_{n})$.

###### Proof.

Note that for $x\in C_{n}$, we have $x\in H_{a,b}^{s,t}$ if and only if
$o(x)\neq\frac{n}{p_{a}^{s}p_{b}^{t}}$ and $o(x)$ is divisible by
$\frac{n}{p_{a}^{s}p_{b}^{t}}$. Further, $x\in K_{a,b}^{s,t}$ if and only if
$o(x)\neq\frac{n}{p_{a}^{s}p_{b}^{t}}$ and $o(x)$ divides
$\frac{n}{p_{a}^{s}p_{b}^{t}}$. Thus $H_{a,b}^{s,t}$ and $K_{a,b}^{s,t}$ are
disjoint sets and $X_{a,b}^{s,t}$ is the set of all elements of
$C_{n}\setminus E_{\frac{n}{p_{a}^{s}p_{b}^{t}}}$ which are adjacent with some
(and hence all) elements of $E_{\frac{n}{p_{a}^{s}p_{b}^{t}}}$. Taking
$A=E_{\frac{n}{p_{a}^{s}p_{b}^{t}}}$ and $B=C_{n}\setminus\left(A\cup
X_{a,b}^{s,t}\right)$, it then follows that $X_{a,b}^{s,t}$ is a cut-set of
$\mathcal{P}(C_{n})$ with $A\cup B$ a separation of
$\mathcal{P}\left(\overline{X_{a,b}^{s,t}}\right)$. ∎

The following is a consequence of Proposition 3.5.

######  Corollary 3.6.

If $r\geq 3$ and $X$ is a minimum cut-set of $\mathcal{P}(C_{n})$, then
$|X|\leq\left|X_{a,b}^{s,t}\right|$ for every $a,b\in[r]$ with $a\neq b$,
$s\in[n_{a}]$ and $t\in[n_{b}]$.

##  4 Distribution of the sets $E_{\frac{n}{p_{i}}},$ $i\in[r]$

We start with two results (Propositions 4.2 and 4.1) which will be used
frequently in the rest of this paper mostly without mention. The first one was
proved in [4, Lemma 2.3].

######  Proposition 4.1 ([4]).

Let $Y$ be a minimum cut-set of $\mathcal{P}(C_{n})$. If $d$ is a positive
divisor of $n$, then either $E_{d}$ is a subset of $Y$ or $E_{d}$ is disjoint
from $Y$.

Recall that two distinct elements $x,y$ of $C_{n}$ are adjacent in
$\mathcal{P}(C_{n})$ if and only if $o(x)\mid o(y)$ or $o(y)\mid o(x)$. As a
consequence, we have the following:

######  Proposition 4.2.

Suppose that $Y$ is a cut-set of $\mathcal{P}(C_{n})$ and $A\cup B$ is a
separation of $\mathcal{P}(\overline{Y})$ such that $A$ contains an element of
order $a$ and $B$ contains an element of order $b$. If $d$ is the greatest
common divisor of $a$ and $b$, then $Y$ contains the unique subgroup $S_{d}$
of $C_{n}$.

Now let $X$ be a minimum cut-set of $\mathcal{P}(C_{n})$ and $A\cup B$ be a
separation of $\mathcal{P}(\overline{X})$. Then for every positive divisor $d$
of $n$, there are three possibilities for the set $E_{d}$: either
$E_{d}\subseteq X$, $E_{d}\subseteq A$ or $E_{d}\subseteq B$. This follows as
a consequence of Proposition 4.1. We study the distribution of the sets
$E_{\frac{n}{p_{i}}}$, $i\in[r]$, among $A,B$ and $X$. Define three subsets
$U,V,W$ of $[r]$ associated with $A,B,X$ respectively by

$U:=\left\\{i\in[r]:E_{\frac{n}{p_{i}}}\subseteq
A\right\\},\;V:=\left\\{i\in[r]:E_{\frac{n}{p_{i}}}\subseteq
B\right\\},\;W:=\left\\{i\in[r]:E_{\frac{n}{p_{i}}}\subseteq X\right\\}.$

Then $U$, $V$ and $W$ are pairwise disjoint and $|U|+|V|+|W|=r$. We prove the
following result using the cut-set $X_{a,b}^{1,1}$ of $\mathcal{P}(C_{n})$ for
suitable $a,b\in[r]$.

######  Proposition 4.3.

$|W|\in\\{0,1,2\\}$.

###### Proof.

Suppose that $|W|\geq 3$. Then $X$ contains
$E_{\frac{n}{p_{j}}},E_{\frac{n}{p_{k}}}$ and $E_{\frac{n}{p_{l}}}$ for some
$j,k,l\in[r]$ with $j<k<l$. Since $X$ contains the set $E_{n}$ also, we get

$\displaystyle|X|$
$\displaystyle\geq|E_{n}|+\left|E_{\frac{n}{p_{j}}}\right|+\left|E_{\frac{n}{p_{k}}}\right|+\left|E_{\frac{n}{p_{l}}}\right|\geq|E_{n}|+\left|E_{\frac{n}{p_{k}}}\right|+\left|E_{\frac{n}{p_{k}}}\right|+\left|E_{\frac{n}{p_{r}}}\right|$

using (1). The cut-set $X_{k,r}^{1,1}$ of $\mathcal{P}(C_{n})$ is a disjoint
union of $E_{n}$, $E_{\frac{n}{p_{k}}}$, $E_{\frac{n}{p_{r}}}$ and
$K_{k,r}^{1,1}$. We have
$\left|K_{k,r}^{1,1}\right|=\frac{n}{p_{k}p_{r}}-\phi\left(\frac{n}{p_{k}p_{r}}\right)$,
as $K_{k,r}^{1,1}$ is the set of all the nongenerators of the cyclic subgroup
$S_{\frac{n}{p_{k}p_{r}}}$ of $C_{n}$. By Lemma 2.7,
$\left|E_{\frac{n}{p_{k}}}\right|=\phi\left(\frac{n}{p_{k}}\right)>\frac{n}{p_{k}p_{r}}-\phi\left(\frac{n}{p_{k}p_{r}}\right)=\left|K_{k,r}^{1,1}\right|$.
It then follows that
$|X|>|E_{n}|+\left|E_{\frac{n}{p_{k}}}\right|+\left|E_{\frac{n}{p_{r}}}\right|+\left|K_{k,r}^{1,1}\right|=\left|X_{k,r}^{1,1}\right|$,
a contradiction to Corollary 3.6. ∎

We note that Proposition 4.3 was also obtained in [6, Proposition 3.10] using
a different cut-set of $\mathcal{P}(C_{n})$. The following proposition is
proved by implicitly borrowing some of the arguments used in the proofs of [6,
Propositions 4.2, 4.3].

######  Proposition 4.4.

If both $U$ and $V$ are nonempty, then $W$ is the empty set and one of $U,V$
must be the singleton set $\\{r\\}$.

###### Proof.

Fix $s\in U$ and $t\in V$. Without loss of generality, we may assume that
$p_{s}>p_{t}$. Then $p_{s}>2$. We show that $s=r$, $U=\\{r\\}$ and
$W=\emptyset$.

Let $D$ be the union of the subgroups $S_{\frac{n}{p_{s}p_{l}}}$ of $C_{n}$,
where $l\in V$. Since $A\cup B$ is a separation of
$\mathcal{P}(\overline{X})$, the subgroups involved in $D$ must be contained
in $X$ and so $D$ is a subset of $X$. By Proposition 4.3, we have $|W|\leq 2$.
We complete the proof in four steps.

(I): We claim that $|W|\neq 2$. Suppose $W=\\{a,b\\}$ for some
$a,b\in[r]\setminus\\{s,t\\}$ with $a<b$. Then $a\leq r-1$ and $b\leq r$. So
$\left|E_{\frac{n}{p_{a}}}\right|\geq\left|E_{\frac{n}{p_{r-1}}}\right|$ and
$\left|E_{\frac{n}{p_{b}}}\right|\geq\left|E_{\frac{n}{p_{r}}}\right|$ by (1).
As $D$ contains $S_{\frac{n}{p_{s}p_{t}}}$, we have
$|D|\geq\left|S_{\frac{n}{p_{s}p_{t}}}\right|=\frac{n}{p_{s}p_{t}}\geq\frac{n}{p_{r-1}p_{r}}=\left|S_{\frac{n}{p_{r-1}p_{r}}}\right|>\left|K_{r-1,r}^{1,1}\right|.$
Since $X$ contains the mutually disjoint sets $E_{n}$, $E_{\frac{n}{p_{a}}}$,
$E_{\frac{n}{p_{b}}}$ and $D$, we get

$\displaystyle|X|$
$\displaystyle\geq|E_{n}|+\left|E_{\frac{n}{p_{a}}}\right|+\left|E_{\frac{n}{p_{b}}}\right|+|D|>|E_{n}|+\left|E_{\frac{n}{p_{r-1}}}\right|+\left|E_{\frac{n}{p_{r}}}\right|+\left|K_{r-1,r}^{1,1}\right|.$

The cut-set $X_{r-1,r}^{1,1}$ of $\mathcal{P}(C_{n})$ is the union of mutually
disjoint sets $E_{n}$, $E_{\frac{n}{p_{r-1}}}$, $E_{\frac{n}{p_{r}}}$ and
$K_{r-1,r}^{1,1}$. It then follows that $|X|>\left|X_{r-1,r}^{1,1}\right|$, a
contradiction to Corollary 3.6.

(II): We claim that $(|U|,|W|)\neq(1,1)$. Otherwise, $U=\\{s\\}$ and
$W=\\{a\\}$ for some $a\in[r]\setminus\\{s,t\\}$. Then
$V=[r]\setminus\\{s,a\\}$ and so $D$ is the union of the $r-2$ subgroups
$S_{\frac{n}{p_{s}p_{j}}}$, $j\in[r]\setminus\\{s,a\\}$, of $C_{n}$. Since
$p_{s}>2$, we have
$\left|E_{\frac{n}{p_{a}}}\right|+|D|>\left|Q_{r}^{1}\right|$ by Lemma 2.5.
Since $X$ contains the mutually disjoint sets $E_{n}$, $E_{\frac{n}{p_{a}}}$
and $D$, we get
$|X|\geq|E_{n}|+\left|E_{\frac{n}{p_{a}}}\right|+|D|>|E_{n}|+|Q_{r}^{1}|=\left|Z_{r}^{1}\right|$,
a contradiction to Corollary 3.2.

(III): We claim that $|U|=1$. Suppose this is not the case. Then $|U|\geq 2$.
Define the sets $D_{1}$ and $D_{2}$ by

$D_{1}=\underset{k\in
U\setminus\\{s\\}}{\bigcup}S_{\frac{n}{p_{k}p_{t}}},\;\;D_{2}=\underset{k\in
U\setminus\\{s\\}}{\bigcup}S_{\frac{n}{p_{s}p_{k}}}.$

Note that $D_{1}$ and $D_{2}$ are nonempty sets as $|U|\geq 2$. Since $A\cup
B$ is a separation of $\mathcal{P}(\overline{X})$, the subgroups involved in
$D_{1}$ must be contained in $X$. Thus $D\cup D_{1}$ is a subset of $X$. We
assert that $|D\cup D_{1}|>|D\cup D_{2}|$.

If $x\in D\cap D_{1}$, then $x\in S_{\frac{n}{p_{s}p_{l}}}\bigcap
S_{\frac{n}{p_{k}p_{t}}}$ for some $l\in V$ and $k\in U\setminus\\{s\\}$.
Since $S_{\frac{n}{p_{s}p_{l}}}\bigcap S_{\frac{n}{p_{k}p_{t}}}$ is a subgroup
of $S_{\frac{n}{p_{s}p_{k}p_{t}}}=S_{\frac{n}{p_{s}p_{t}}}\bigcap
S_{\frac{n}{p_{s}p_{k}}}$, we get $x\in D\cap D_{2}$. Thus $D\cap D_{1}$ is a
subset of $D\cap D_{2}$ and hence $|D\cap D_{1}|\leq|D\cap D_{2}|$.

Put $R_{1}=[r]\setminus((U\setminus\\{s\\})\cup\\{t\\})$ and
$R_{2}=[r]\setminus U=[r]\setminus((U\setminus\\{s\\})\cup\\{s\\})$. Observe
that $t\notin R_{1}$, $t\in R_{2}$, $s\in R_{1}$, $s\notin R_{2}$ and
$R_{1}\setminus\\{s\\}=R_{2}\setminus\\{t\\}$. Since $p_{s}>p_{t}$ by our
assumption, we have $\underset{j\in R_{1}}{\prod}p_{j}>\underset{j\in
R_{2}}{\prod}p_{j}$. Then using Lemma 2.8, we get

$\displaystyle|D_{1}|$ $\displaystyle=\frac{n}{p_{1}p_{2}\cdots
p_{r}}\times\underset{j\in R_{1}}{\prod}p_{j}\times\left[\underset{k\in
U\setminus\\{s\\}}{\prod}p_{k}-\phi\left(\underset{k\in
U\setminus\\{s\\}}{\prod}p_{k}\right)\right]$
$\displaystyle>\frac{n}{p_{1}p_{2}\cdots p_{r}}\times\underset{j\in
R_{2}}{\prod}p_{j}\times\left[\underset{k\in
U\setminus\\{s\\}}{\prod}p_{k}-\phi\left(\underset{k\in
U\setminus\\{s\\}}{\prod}p_{k}\right)\right]=|D_{2}|.$

Therefore, $|D\cup D_{1}|=|D|+|D_{1}|-|D\cap D_{1}|>|D|+|D_{2}|-|D\cap
D_{2}|=|D\cup D_{2}|$.

If $W=\emptyset$, then $U\cup V=[r]$ and so $D\cup D_{2}=Q_{s}^{1}$. Since $X$
contains $E_{n}$ and $D\cup D_{1}$, we get $|X|\geq|E_{n}|+|D\cup
D_{1}|>|E_{n}|+|D\cup D_{2}|=|E_{n}|+|Q_{s}^{1}|=\left|Z_{s}^{1}\right|$, a
contradiction to Corollary 3.2.

If $|W|=1$, then $W=\\{a\\}$ for some $a\in[r]\setminus\\{s,t\\}$. In this
case, $U\cup V=[r]\setminus\\{a\\}$ and so $D\cup D_{2}$ is the union of the
$r-2$ subgroups $S_{\frac{n}{p_{s}p_{j}}}$, $j\in[r]\setminus\\{s,a\\}$, of
$C_{n}$. As $p_{s}>2$, we have $\left|E_{\frac{n}{p_{a}}}\right|+|D\cup
D_{2}|>\left|Q_{r}^{1}\right|$ by Lemma 2.5. Since $X$ contains the mutually
disjoint sets $E_{n}$, $E_{\frac{n}{p_{a}}}$ and $D\cup D_{1}$, we get
$|X|\geq|E_{n}|+\left|E_{\frac{n}{p_{a}}}\right|+|D\cup
D_{1}|>|E_{n}|+\left|E_{\frac{n}{p_{a}}}\right|+|D\cup
D_{2}|>|E_{n}|+|Q_{r}^{1}|=\left|Z_{r}^{1}\right|$, a contradiction to
Corollary 3.2.

(IV): We claim that $s=r$. By the previous three steps, we get $U=\\{s\\}$ and
$W=\emptyset$. So $V=[r]\setminus\\{s\\}$ and hence $D=Q_{s}^{1}$. If $s\neq
r$, then using Lemma 2.4, we get
$|X|\geq|E_{n}|+|D|=|E_{n}|+|Q_{s}^{1}|=\left|Z_{s}^{1}\right|>\left|Z_{r}^{1}\right|$,
a contradiction to Corollary 3.2. ∎

It follows from the proof of [6, Proposition 4.6] that if $n_{r}\geq 2$ and
$|W|=2$, then $|X|>|Z_{r}^{n_{r}}|$, contradicting Corollary 3.2. We thus have
the following:

######  Proposition 4.5.

If $|W|=2$, then $n_{r}=1$.

##  5 Proof of the Main Theorem

Let $r\geq 4$ and $X$ be a minimum cut-set of $\mathcal{P}(C_{n})$. Fix a
separation $A\cup B$ of $\mathcal{P}(\overline{X})$. We continue with the sets
$U,V$ and $W$ as defined in Section 4 which are associated with $A,B$ and $X$
respectively. By Proposition 4.3, we have $|W|\leq 2$.

###  5.1 The case $|W|=0$

Suppose that $W=\emptyset$. Then $U\neq\emptyset$ and $V\neq\emptyset$, as
both $A$ and $B$ are nonempty subsets of $\overline{X}$ and $E_{n}$ is
contained in $X$. So $\\{U,V\\}=\\{\\{r\\},[r-1]\\}$ by Proposition 4.4. It
then follows that $X$ contains the subgroups $S_{\frac{n}{p_{i}p_{r}}}$ for
$i\in[r-1]$ and hence contains the cut-set $Z_{r}^{1}$ of
$\mathcal{P}(C_{n})$. Since $X$ is a minimum cut-set of $\mathcal{P}(C_{n})$,
we must have $X=Z_{r}^{1}$. Thus we have the following:

######  Proposition 5.1.

If $W=\emptyset$, then $X=Z_{r}^{1}$.

###  5.2 The case $|W|=1$

######  Proposition 5.2.

If $W=\\{a\\}$ for some $a\in[r]$, then $n_{a}\geq 2$,
$2\phi\left(\frac{p_{1}p_{2}\cdots p_{r}}{p_{a}}\right)<\frac{p_{1}p_{2}\cdots
p_{r}}{p_{a}}$ and $X=Z_{a}^{n_{a}}$.

###### Proof.

Without loss of generality, we may assume by Proposition 4.4 that
$U=\emptyset$. Then $V=[r]\setminus\\{a\\}$. Since $B$ contains the sets
$E_{\frac{n}{p_{i}}}$ for $i\in[r]\setminus\\{a\\}$ and there is no edge of
$\mathcal{P}(C_{n})$ containing vertices from both $A$ and $B$, the order of
an element in $A$ must be divisible by $p_{i}^{n_{i}}$ for every
$i\in[r]\setminus\\{a\\}$ and hence must be of the form $\frac{n}{p_{a}^{k}}$,
where $0\leq k\leq n_{a}$. The elements of $C_{n}$ of order $n$ and
$\frac{n}{p_{a}}$ correspond to the elements contained in $E_{n}$ and
$E_{\frac{n}{p_{a}}}$ respectively. Since $E_{n}$ and $E_{\frac{n}{p_{a}}}$
are contained in $X$ and $A$ is nonempty, it follows that $k\geq 2$ and hence
$n_{a}\geq 2$.

Let $s\in\\{2,3,\ldots,n_{a}\\}$ be the smallest integer such that $A$ has an
element of order $\frac{n}{p_{a}^{s}}$. Then the sets
$E_{\frac{n}{p_{a}^{2}}},\dots,E_{\frac{n}{p_{a}^{s-1}}}$ and the subgroups
$S_{\frac{n}{p_{i}p_{a}^{s}}}$, $i\in[r]\setminus\\{a\\}$, must be contained
in $X$. It follows that $X$ contains the cut-set $Z_{a}^{s}$ of
$\mathcal{P}(C_{n})$. Since $X$ is a minimum cut-set of $\mathcal{P}(C_{n})$,
we must have $X=Z_{a}^{s}$.

Since $r\geq 4$, we have $2\phi\left(\frac{p_{1}p_{2}\cdots
p_{r}}{p_{a}}\right)\neq\frac{p_{1}p_{2}\cdots p_{r}}{p_{a}}$. If
$2\phi\left(\frac{p_{1}p_{2}\cdots p_{r}}{p_{a}}\right)>\frac{p_{1}p_{2}\cdots
p_{r}}{p_{a}}$, then $s\geq 2$ implies
$\left|Z_{a}^{s}\right|>\left|Z_{a}^{1}\right|$ by Proposition 3.4. This gives
$|X|>\left|Z_{a}^{1}\right|$, contradicting Corollary 3.2.

Thus $2\phi\left(\frac{p_{1}p_{2}\cdots
p_{r}}{p_{a}}\right)<\frac{p_{1}p_{2}\cdots p_{r}}{p_{a}}$. In this case, by
Proposition 3.4, $\left|Z_{a}^{s}\right|\geq\left|Z_{a}^{n_{a}}\right|$ and
equality holds if and only if $s=n_{a}$. Since $X=Z_{a}^{s}$ is a minimum cut-
set of $\mathcal{P}(C_{n})$, it follows that $s=n_{a}$ and $X=Z_{a}^{n_{a}}$.
∎

###  5.3 The case $|W|=2$

In the rest of this section, we consider that $W=\\{a,b\\}$ for some
$a,b\in[r]$ with $a\neq b$. Without loss of generality, we may assume by
Proposition 4.4 that $U=\emptyset$. Then $V=[r]\setminus\\{a,b\\}$ and so $B$
contains the sets $E_{\frac{n}{p_{i}}}$ for $i\in[r]\setminus\\{a,b\\}$.

######  Proposition 5.3.

If $x\in A$, then $o(x)$ cannot be of the form $\frac{n}{p_{c}^{k}}$, where
$c\in\\{a,b\\}$ and $k\in[n_{c}]$.

###### Proof.

Suppose that $A$ contains an element of order of the form
$\frac{n}{p_{c}^{k}}$ for some $c\in\\{a,b\\}$ and $k\in[n_{c}]$. Without loss
of generality, we may assume that $c=a$. Then $k\geq 2$ as
$E_{\frac{n}{p_{a}}}$ is contained in $X$.

Let $s\in\\{2,3,\ldots,n_{a}\\}$ be the smallest integer such that $A$
contains an element of order $\frac{n}{p_{a}^{s}}$. Then the sets
$E_{\frac{n}{p_{a}}},\ldots,E_{\frac{n}{p_{a}^{s-1}}}$ and the subgroups
$S_{\frac{n}{p_{i}p_{a}^{s}}}$, $i\in[r]\setminus\\{a,b\\}$, must be contained
in $X$. Let $Q_{a,b}^{s}$ denote the union of the $r-2$ subgroups
$S_{\frac{n}{p_{i}p_{a}^{s}}}$, $i\in[r]\setminus\\{a,b\\}$. Since
$Q_{a,b}^{s}$ is a subset of $Q_{a}^{s}$, we get

$\left|Q_{a}^{s}\setminus
Q_{a,b}^{s}\right|=\left|Q_{a}^{s}\right|-\left|Q_{a,b}^{s}\right|=\frac{n}{p_{1}p_{2}\cdots
p_{r}}\times\frac{1}{p_{a}^{s-1}}\times\phi\left(\frac{p_{1}p_{2}\cdots
p_{r}}{p_{a}p_{b}}\right)$

using Lemmas 2.3 and 2.6. As $s\geq 2$, we have
$\frac{\phi(p_{a}p_{b})}{p_{b}}>\frac{1}{p_{a}^{s-1}}$ and so

$\left|E_{\frac{n}{p_{b}}}\right|=\phi\left(\frac{n}{p_{b}}\right)\geq\frac{n}{p_{1}\cdots
p_{r}}\times\frac{\phi(p_{1}\cdots p_{r})}{p_{b}}>\frac{n}{p_{1}\cdots
p_{r}}\times\frac{1}{p_{a}^{s-1}}\times\phi\left(\frac{p_{1}\cdots
p_{r}}{p_{a}p_{b}}\right)=\left|Q_{a}^{s}\right|-\left|Q_{a,b}^{s}\right|.$

This gives
$\left|E_{\frac{n}{p_{b}}}\right|+\left|Q_{a,b}^{s}\right|>\left|Q_{a}^{s}\right|.$
The sets $E_{n}$, $E_{\frac{n}{p_{a}}},\ldots,E_{\frac{n}{p_{a}^{s-1}}}$,
$E_{\frac{n}{p_{b}}}$ and $Q_{a,b}^{s}$ are mutually disjoint and contained in
$X$. So

$\displaystyle|X|$
$\displaystyle\geq|E_{n}|+\left|E_{\frac{n}{p_{a}}}\right|+\cdots+\left|E_{\frac{n}{p_{a}^{s-1}}}\right|+\left|E_{\frac{n}{p_{b}}}\right|+\left|Q_{a,b}^{s}\right|$
$\displaystyle>|E_{n}|+\left|E_{\frac{n}{p_{a}}}\right|+\cdots+\left|E_{\frac{n}{p_{a}^{s-1}}}\right|+\left|Q_{a}^{s}\right|.$

Since the cut-set $Z_{a}^{s}$ of $\mathcal{P}(C_{n})$ is the union of mutually
disjoint sets $E_{n}$, $E_{\frac{n}{p_{a}}}$,
$E_{\frac{n}{p_{a}^{2}}},\ldots,E_{\frac{n}{p_{a}^{s-1}}}$ and $Q_{a}^{s}$, it
follows that $|X|>\left|Z_{a}^{s}\right|$, a contradiction to Corollary 3.2. ∎

######  Corollary 5.4.

If $x\in A$, then $o(x)$ is of the form $\frac{n}{p_{a}^{u}p_{b}^{v}}$ for
some $u,v$ with $1\leq u\leq n_{a}$ and $1\leq v\leq n_{b}$.

###### Proof.

By Proposition 5.3, $A$ has no element whose order is of the form
$\frac{n}{p_{c}^{k}}$, where $c\in\\{a,b\\}$ and $k\in[n_{c}]$. Since $B$
contains the sets $E_{\frac{n}{p_{i}}}$ for $i\in[r]\setminus\\{a,b\\}$ and
there is no edge of $\mathcal{P}(C_{n})$ containing vertices from both $A$ and
$B$, $o(x)$ must be divisible by $p_{i}^{n_{i}}$ for every
$i\in[r]\setminus\\{a,b\\}$. It then follows that $o(x)$ is of the form
$\frac{n}{p_{a}^{u}p_{b}^{v}}$ with $1\leq u\leq n_{a}$ and $1\leq v\leq
n_{b}$. ∎

Now on we assume that $a<b$. Then $p_{a}<p_{b}$ and so $p_{b}\geq 3$. By
Corollary 5.4, let $t\in[n_{b}]$ be the smallest integer such that $A$
contains $E_{\frac{n}{p_{a}^{u}p_{b}^{t}}}$ for some $u\in[n_{a}]$. For such
$t$, let $s\in[n_{a}]$ be the smallest integer for which
$E_{\frac{n}{p_{a}^{s}p_{b}^{t}}}$ is contained in $A$. The rest of this
section is devoted to prove that $X=X_{a,b}^{s,t}$.

Since the sets $E_{\frac{n}{p_{i}}}$, $i\in[r]\setminus\\{a,b\\}$, are
contained in $B$ and there is no edge of $\mathcal{P}(C_{n})$ containing
vertices from both $A$ and $B$, it follows that the sets
$E_{\frac{n}{p_{a}^{i}p_{b}^{j}}}$, where $0\leq i\leq s$, $0\leq j\leq t$
with $(i,j)\neq(s,t)$, and the subgroups
$S_{\frac{n}{p_{i}p_{a}^{s}p_{b}^{t}}}$ of $\mathcal{P}(C_{n})$, where
$i\in[r]\setminus\\{a,b\\}$, must be contained in $X$. Thus we have the
following:

######  Proposition 5.5.

$X$ contains $H_{a,b}^{s,t}$ and the subgroups
$S_{\frac{n}{p_{i}p_{a}^{s}p_{b}^{t}}}$ of $C_{n}$, where
$i\in[r]\setminus\\{a,b\\}$.

######  Corollary 5.6.

If $(s,t)=(n_{a},n_{b})$, then $X=X_{a,b}^{s,t}=X_{a,b}^{n_{a},n_{b}}$.

###### Proof.

Since $(s,t)=(n_{a},n_{b})$, Proposition 5.5 implies that $X$ contains the set
$K_{a,b}^{n_{a},n_{b}}$ and hence the cut-set $X_{a,b}^{n_{a},n_{b}}$ of
$\mathcal{P}(C_{n})$. Then the corollary follows by the minimality of $X$. ∎

By Corollary 5.6, we shall assume that $(s,t)\neq(n_{a},n_{b})$. Our aim is to
show that $X$ contains the subgroup $S_{\frac{n}{p_{a}^{s+1}p_{b}^{t}}}$ if
$s<n_{a}$ and the subgroup $S_{\frac{n}{p_{a}^{s}p_{b}^{t+1}}}$ if $t<n_{b}$.
For this, it is enough to show that $B$ contains the set
$E_{\frac{n}{p_{a}^{s+1}}}$ if $s<n_{a}$ and the set
$E_{\frac{n}{p_{b}^{t+1}}}$ if $t<n_{b}$.

######  Proposition 5.7.

If $t<n_{b}$, then $(p_{a},n_{a})\neq(2,1)$.

###### Proof.

Suppose that $(p_{a},n_{a})=(2,1)$. Then $a=1$ and $s=n_{1}=1$. We have
$n_{r}=1$ by Proposition 4.5. So $1<b<r$ (as $n_{b}>t\geq 1$) and hence
$2<p_{b}<p_{r}$. We show that $|X|>\left|X_{r,b}^{1,t}\right|$, which would
contradict Corollary 3.6.

The cut-set $X_{r,b}^{1,t}$ of $\mathcal{P}(C_{n})$ is a disjoint union of
$H_{r,b}^{1,t}$ and $K_{r,b}^{1,t}$. By Proposition 5.5, $X$ contains
$H_{1,b}^{1,t}$ and the subgroups $S_{\frac{n}{2p_{b}^{t}p_{i}}}$ of $C_{n}$,
where $i\in[r]\setminus\\{1,b\\}$. We know that $H_{r,b}^{1,t}$ is a disjoint
union of the sets $E_{\frac{n}{p_{r}^{i}p_{b}^{j}}}$ and $H_{1,b}^{1,t}$ is a
disjoint union of the sets $E_{\frac{n}{2^{i}p_{b}^{j}}}$, where $0\leq i\leq
1$, $0\leq j\leq t$ and $(i,j)\neq(1,t)$. For such $i$ and $j$, $p_{r}>2$
implies that
$\left|E_{\frac{n}{2^{i}p_{b}^{j}}}\right|=\phi\left(\frac{n}{2^{i}p_{b}^{j}}\right)\geq\phi\left(\frac{n}{p_{r}^{i}p_{b}^{j}}\right)=\left|E_{\frac{n}{p_{r}^{i}p_{b}^{j}}}\right|$.
It then follows that
$\left|H_{1,b}^{1,t}\right|\geq\left|H_{r,b}^{1,t}\right|$.

Let $G$ be union of the subgroups $S_{\frac{n}{2p_{b}^{t}p_{i}}}$ of $C_{n}$,
where $i\in[r]\setminus\\{1,b\\}$. Since each of these subgroups is disjoint
from $H_{1,b}^{1,t}$ and $K_{r,b}^{1,t}$ is disjoint from $H_{r,b}^{1,t}$, it
is enough to show that $|G|>\left|K_{r,b}^{1,t}\right|$. Since the set
$K_{r,b}^{1,t}$ is the set of nongenerators of the cyclic subgroup
$S_{\frac{n}{p_{r}p_{b}^{t}}}$ of $C_{n}$, we have

$\left|K_{r,b}^{1,t}\right|=\frac{n}{p_{r}p_{b}^{t}}-\phi\left(\frac{n}{p_{r}p_{b}^{t}}\right)=\frac{n}{2p_{2}\cdots
p_{r}}\times\frac{1}{p_{b}^{t}}\times\left[2p_{2}\cdots
p_{r-1}-\phi\left(2p_{2}\cdots p_{r-1}\right)\right].$

Consider the subgroup $S_{\frac{n}{2p_{b}^{t}}}$ of $C_{n}$ containing $G$.
Let $\widetilde{G}$ denote the complement of $G$ in
$S_{\frac{n}{2p_{b}^{t}}}$. Then $\widetilde{G}=E_{\frac{n}{2p_{b}^{t}}}\cup
E_{\frac{n}{2p_{b}^{t+1}}}\cup\cdots\cup E_{\frac{n}{2p_{b}^{n_{b}}}}$, a
disjoint union. So

$|\widetilde{G}|=\underset{l=t}{\overset{n_{b}}{\sum}}\left|E_{\frac{n}{2p_{b}^{l}}}\right|=\underset{l=t}{\overset{n_{b}}{\sum}}\phi\left(\frac{n}{2p_{b}^{l}}\right)=\phi\left(\frac{n}{2p_{b}^{n_{b}}}\right)\times
p_{b}^{n_{b}-t}=\frac{n}{2p_{2}\cdots
p_{r}}\times\frac{1}{p_{b}^{t-1}}\times\phi\left(\frac{p_{2}p_{3}\cdots
p_{r}}{p_{b}}\right).$

and hence

$|G|=\left|S_{\frac{n}{2p_{b}^{t}}}\right|-|\widetilde{G}|=\frac{n}{2p_{2}\cdots
p_{r}}\times\frac{1}{p_{b}^{t-1}}\times\left[\frac{p_{2}p_{3}\cdots
p_{r}}{p_{b}}-\phi\left(\frac{p_{2}p_{3}\cdots p_{r}}{p_{b}}\right)\right].$

Writing $\mu=\frac{n}{2p_{2}\cdots p_{r}}\times\frac{1}{p_{b}^{t-1}}$, we get

$\displaystyle|G|-\left|K_{r,b}^{1,t}\right|$
$\displaystyle=\mu\times\left[\frac{p_{2}p_{3}\cdots
p_{r}}{p_{b}}-\frac{2p_{2}\cdots
p_{r-1}}{p_{b}}-\phi\left(\frac{p_{2}p_{3}\cdots
p_{r}}{p_{b}}\right)+\frac{1}{p_{b}}\phi\left(2p_{2}\cdots
p_{r-1}\right)\right]$ $\displaystyle=\mu\times\left[\frac{p_{2}p_{3}\cdots
p_{r-1}}{p_{b}}\times(p_{r}-2)-\phi\left(\frac{p_{2}p_{3}\cdots
p_{r-1}}{p_{b}}\right)\left(\phi(p_{r})-\frac{\phi(p_{b})}{p_{b}}\right)\right]$
$\displaystyle>\mu\times\left[\frac{p_{2}p_{3}\cdots
p_{r-1}}{p_{b}}\times(p_{r}-2)-\phi\left(\frac{p_{2}p_{3}\cdots
p_{r-1}}{p_{b}}\right)(p_{r}-1)\right].$

Let $k\in[r]\setminus\\{1,b,r\\}$. Such a $k$ exists as $r\geq 4$. Then
$p_{r}-p_{k}\geq 2$ (both being odd primes) and so
$p_{k}(p_{r}-2)-\phi(p_{k})(p_{r}-1)=p_{r}-p_{k}-1>0$. Hence it follows that

$\left[\frac{p_{2}p_{3}\cdots
p_{r-1}}{p_{b}}\times(p_{r}-2)-\phi\left(\frac{p_{2}p_{3}\cdots
p_{r-1}}{p_{b}}\right)(p_{r}-1)\right]>0$

and therefore, $|G|>\left|K_{r,b}^{1,t}\right|$. This completes the proof. ∎

Recall that the cut-set $X_{a,b}^{s,t}$ of $\mathcal{P}(C_{n})$ is a disjoint
union of $H_{a,b}^{s,t}$ and $K_{a,b}^{s,t}$. Let $x\in X_{a,b}^{s,t}$. Then
$x\in H_{a,b}^{s,t}$ if and only if $o(x)$ is divisible by
$\frac{n}{p_{a}^{s}p_{b}^{t}}$ with $o(x)\neq\frac{n}{p_{a}^{s}p_{b}^{t}}$.
Further, $x\in K_{a,b}^{s,t}$ if and only if $o(x)$ divides
$\frac{n}{p_{a}^{s}p_{b}^{t}}$ with $o(x)\neq\frac{n}{p_{a}^{s}p_{b}^{t}}$ if
and only if $x\in S_{\frac{n}{p_{i}p_{a}^{s}p_{b}^{t}}}$ for some $i\in J$,
where

$J:=\begin{cases}[r]\setminus\\{a\\},&\text{if }s=n_{a},\;t<n_{b}\\\
[r]\setminus\\{b\\},&\text{if }s<n_{a},\;t=n_{b}\\\ [r],&\text{if
}s<n_{a},\;t<n_{b}\end{cases}$

as $(s,t)\neq(n_{a},n_{b})$. Thus $K_{a,b}^{s,t}$ is the union of the
subgroups $S_{\frac{n}{p_{i}p_{a}^{s}p_{b}^{t}}}$ with $i\in J$.

Let $L_{a,b}^{s,t}$ denote the set of all elements of $K_{a,b}^{s,t}$ which do
not belong to any of the subgroups $S_{\frac{n}{p_{i}p_{a}^{s}p_{b}^{t}}}$,
where $i\in J\setminus\\{a,b\\}=[r]\setminus\\{a,b\\}$. Since
$(s,t)\neq(n_{a},n_{b})$, we have $L_{a,b}^{s,t}\neq\emptyset$. Further,
$L_{a,b}^{s,t}$ is precisely union of the mutually disjoint sets
$E_{\frac{n}{p_{a}^{k}p_{b}^{l}}}$, where $s\leq k\leq n_{a}$, $t\leq l\leq
n_{b}$ with $(k,l)\neq(s,t)$.

######  Proposition 5.8.

$\left|L_{a,b}^{s,t}\right|=\phi\left(\frac{n}{p_{a}^{n_{a}}p_{b}^{n_{b}}}\right)\left[p_{a}^{n_{a}-s}p_{b}^{n_{b}-t}-\phi\left(p_{a}^{n_{a}-s}p_{b}^{n_{b}-t}\right)\right]$.

###### Proof.

We have
$\left|L_{a,b}^{s,t}\right|=\sum\left|E_{\frac{n}{p_{a}^{k}p_{b}^{l}}}\right|$,
where the sum runs over all $k,l$ satisfying $s\leq k\leq n_{a}$, $t\leq l\leq
n_{b}$ and $(k,l)\neq(s,t)$. Since
$\underset{k=s}{\overset{n_{a}}{\sum}}\;\underset{l=t}{\overset{n_{b}}{\sum}}\left|E_{\frac{n}{p_{a}^{k}p_{b}^{l}}}\right|=\phi\left(\frac{n}{p_{a}^{n_{a}}p_{b}^{n_{b}}}\right)p_{a}^{n_{a}-s}p_{b}^{n_{b}-t}$
by Lemma 2.2, and
$\left|E_{\frac{n}{p_{a}^{s}p_{b}^{t}}}\right|=\phi\left(\frac{n}{p_{a}^{s}p_{b}^{t}}\right)=\phi\left(\frac{n}{p_{a}^{n_{a}}p_{b}^{n_{b}}}\right)\phi\left(p_{a}^{n_{a}-s}p_{b}^{n_{b}-t}\right)$,
the proposition follows. ∎

######  Proposition 5.9.

The number of elements of $X$ which do not belong to $H_{a,b}^{s,t}$ or
$K_{a,b}^{s,t}\setminus L_{a,b}^{s,t}$ is at most
$\left|L_{a,b}^{s,t}\right|$.

###### Proof.

The cut-set $X_{a,b}^{s,t}$ of $\mathcal{P}(C_{n})$ is a disjoint union of
$H_{a,b}^{s,t}$, $L_{a,b}^{s,t}$ and $K_{a,b}^{s,t}\setminus L_{a,b}^{s,t}$.
By Proposition 5.5, $X$ contains the sets $H_{a,b}^{s,t}$ and
$K_{a,b}^{s,t}\setminus L_{a,b}^{s,t}$. Then the proposition follows as $X$ is
a minimum cut-set of $\mathcal{P}(C_{n})$. ∎

######  Proposition 5.10.

If $s<n_{a}$ and $t<n_{b}$, then at least one of the sets
$E_{\frac{n}{p_{a}^{s+1}}}$ and $E_{\frac{n}{p_{b}^{t+1}}}$ is contained in
$B$.

###### Proof.

By Proposition 5.3, each of $E_{\frac{n}{p_{a}^{s+1}}}$ and
$E_{\frac{n}{p_{b}^{t+1}}}$ is contained in either $B$ or $X$. If possible,
suppose that both $E_{\frac{n}{p_{a}^{s+1}}}$ and $E_{\frac{n}{p_{b}^{t+1}}}$
are contained in $X$. Note that $E_{\frac{n}{p_{a}^{s+1}}}$ and
$E_{\frac{n}{p_{b}^{t+1}}}$ are disjoint and each of them is disjoint from the
cut-set $X_{a,b}^{s,t}$ of $\mathcal{P}(C_{n})$. By proposition 5.9, we have
$\left|E_{\frac{n}{p_{a}^{s+1}}}\right|+\left|E_{\frac{n}{p_{b}^{t+1}}}\right|\leq\left|L_{a,b}^{s,t}\right|$,
that is,

$\xi:=\left|E_{\frac{n}{p_{a}^{s+1}}}\right|+\left|E_{\frac{n}{p_{b}^{t+1}}}\right|-\left|L_{a,b}^{s,t}\right|\leq
0.$ (4)

By Proposition 5.8, we have
$\left|L_{a,b}^{s,t}\right|=\phi\left(\frac{n}{p_{a}^{n_{a}}p_{b}^{n_{b}}}\right)\left[p_{a}^{n_{a}-s}p_{b}^{n_{b}-t}-\phi\left(p_{a}^{n_{a}-s}p_{b}^{n_{b}-t}\right)\right].$
Further,

$\left|E_{\frac{n}{p_{a}^{s+1}}}\right|=\phi\left(\frac{n}{p_{a}^{s+1}}\right)=\phi\left(\frac{n}{p_{a}^{n_{a}}p_{b}^{n_{b}}}\right)\phi\left(p_{a}^{n_{a}-s-1}p_{b}^{n_{b}}\right)$

and

$\left|E_{\frac{n}{p_{b}^{t+1}}}\right|=\phi\left(\frac{n}{p_{b}^{t+1}}\right)=\phi\left(\frac{n}{p_{a}^{n_{a}}p_{b}^{n_{b}}}\right)\phi\left(p_{a}^{n_{a}}p_{b}^{n_{b}-t-1}\right).$

So

$\xi=\phi\left(\frac{n}{p_{a}^{n_{a}}p_{b}^{n_{b}}}\right)\left[\phi\left(p_{a}^{n_{a}-s-1}p_{b}^{n_{b}}\right)+\phi\left(p_{a}^{n_{a}}p_{b}^{n_{b}-t-1}\right)+\phi\left(p_{a}^{n_{a}-s}p_{b}^{n_{b}-t}\right)-p_{a}^{n_{a}-s}p_{b}^{n_{b}-t}\right].$

We show that $\xi>0$, thus getting a contradiction to (4). We consider four
different cases depending on $s$ and $t$.

(i) If $s+1<n_{a}$ and $t+1<n_{b}$, then

$\displaystyle\xi$
$\displaystyle=\phi\left(\frac{n}{p_{a}^{n_{a}}p_{b}^{n_{b}}}\right)\times\frac{p_{a}^{n_{a}}p_{b}^{n_{b}}}{p_{a}^{s+1}p_{b}^{t+1}}\times\left[\phi(p_{a}p_{b})\left(\frac{p_{b}^{t}}{p_{a}}+\frac{p_{a}^{s}}{p_{b}}+1\right)-p_{a}p_{b}\right].$

Since
$\frac{p_{b}^{t}}{p_{a}}+\frac{p_{a}^{s}}{p_{b}}=\frac{p_{b}^{t+1}+p_{a}^{s+1}}{p_{a}p_{b}}\geq\frac{p_{b}^{2}+p_{a}^{2}}{p_{a}p_{b}}>2$,
it follows that $\xi>0$.

(ii) If $s+1=n_{a}$ and $t+1<n_{b}$, then

$\displaystyle\xi$
$\displaystyle=\phi\left(\frac{n}{p_{a}^{n_{a}}p_{b}^{n_{b}}}\right)\left[\phi\left(p_{b}^{n_{b}}\right)+\phi\left(p_{a}^{n_{a}}p_{b}^{n_{b}-t-1}\right)+\phi\left(p_{a}p_{b}^{n_{b}-t}\right)-p_{a}p_{b}^{n_{b}-t}\right]$
$\displaystyle=\phi\left(\frac{n}{p_{a}^{n_{a}}p_{b}^{n_{b}}}\right)\times\frac{p_{b}^{n_{b}}}{p_{b}^{t+1}}\times\left[\phi(p_{a}p_{b})\left(\frac{p_{b}^{t}}{\phi(p_{a})}+\frac{p_{a}^{n_{a}-1}}{p_{b}}+1\right)-p_{a}p_{b}\right].$

Since
$\frac{p_{b}^{t}}{\phi(p_{a})}+\frac{p_{a}^{n_{a}-1}}{p_{b}}>\frac{p_{b}^{t}}{p_{a}}+\frac{p_{a}^{n_{a}-1}}{p_{b}}=\frac{p_{b}^{t+1}+p_{a}^{n_{a}}}{p_{a}p_{b}}\geq\frac{p_{b}^{2}+p_{a}^{2}}{p_{a}p_{b}}>2$,
it follows that $\xi>0$.

(iii) If $s+1<n_{a}$ and $t+1=n_{b}$, then

$\displaystyle\xi$
$\displaystyle=\phi\left(\frac{n}{p_{a}^{n_{a}}p_{b}^{n_{b}}}\right)\left[\phi\left(p_{a}^{n_{a}-s-1}p_{b}^{n_{b}}\right)+\phi\left(p_{a}^{n_{a}}\right)+\phi\left(p_{a}^{n_{a}-s}p_{b}\right)-p_{a}^{n_{a}-s}p_{b}\right]$
$\displaystyle=\phi\left(\frac{n}{p_{a}^{n_{a}}p_{b}^{n_{b}}}\right)\times\frac{p_{a}^{n_{a}}}{p_{a}^{s+1}}\times\left[\phi(p_{a}p_{b})\left(\frac{p_{b}^{n_{b}-1}}{p_{a}}+\frac{p_{a}^{s}}{\phi(p_{b})}+1\right)-p_{a}p_{b}\right].$

Since
$\frac{p_{b}^{n_{b}-1}}{p_{a}}+\frac{p_{a}^{s}}{\phi(p_{b})}>\frac{p_{b}^{n_{b}-1}}{p_{a}}+\frac{p_{a}^{s}}{p_{b}}=\frac{p_{b}^{n_{b}}+p_{a}^{s+1}}{p_{a}p_{b}}\geq\frac{p_{b}^{2}+p_{a}^{2}}{p_{a}p_{b}}>2$,
it follows that $\xi>0$.

(iv) If $s+1=n_{a}$ and $t+1=n_{b}$, then

$\displaystyle\xi$
$\displaystyle=\phi\left(\frac{n}{p_{a}^{n_{a}}p_{b}^{n_{b}}}\right)\left[\phi\left(p_{b}^{n_{b}}\right)+\phi\left(p_{a}^{n_{a}}\right)+\phi\left(p_{a}p_{b}\right)-p_{a}p_{b}\right]$
$\displaystyle=\phi\left(\frac{n}{p_{a}^{n_{a}}p_{b}^{n_{b}}}\right)\left[\phi(p_{a}p_{b})\left(\frac{p_{b}^{n_{b}-1}}{\phi(p_{a})}+\frac{p_{a}^{n_{a}-1}}{\phi(p_{b})}+1\right)-p_{a}p_{b}\right].$

Since
$\frac{p_{b}^{n_{b}-1}}{\phi(p_{a})}+\frac{p_{a}^{n_{a}-1}}{\phi(p_{b})}>\frac{p_{b}^{n_{b}-1}}{p_{a}}+\frac{p_{a}^{n_{a}-1}}{p_{b}}=\frac{p_{b}^{n_{b}}+p_{a}^{n_{a}}}{p_{a}p_{b}}\geq\frac{p_{b}^{2}+p_{a}^{2}}{p_{a}p_{b}}>2$,
it follows that $\xi>0$. ∎

Let $M_{a,b}^{s,t}$ denote the set of elements of $K_{a,b}^{s,t}$ which do not
belong to any of the subgroups $S_{\frac{n}{p_{i}p_{a}^{s}p_{b}^{t}}}$, where
$i\in J\setminus\\{a\\}$. We have $M_{a,b}^{s,t}=\emptyset$ if and only if
$s=n_{a}$. If $s<n_{a}$, then $M_{a,b}^{s,t}$ is a subset of
$S_{\frac{n}{p_{a}^{s+1}p_{b}^{t}}}$ and is precisely union of the mutually
disjoint sets $E_{\frac{n}{p_{a}^{k}p_{b}^{t}}}$, where $s+1\leq k\leq n_{a}$.

Similarly, let $N_{a,b}^{s,t}$ denote the set of elements of $K_{a,b}^{s,t}$
which do not belong to any of the subgroups
$S_{\frac{n}{p_{i}p_{a}^{s}p_{b}^{t}}}$, where $i\in J\setminus\\{b\\}$. We
have $N_{a,b}^{s,t}=\emptyset$ if and only if $t=n_{b}$. If $t<n_{b}$, then
$N_{a,b}^{s,t}$ is a subset of $S_{\frac{n}{p_{a}^{s}p_{b}^{t+1}}}$ and is
precisely union of the mutually disjoint sets
$E_{\frac{n}{p_{a}^{s}p_{b}^{l}}}$, where $t+1\leq l\leq n_{b}$.

The proof of the following proposition is straightforward.

######  Proposition 5.11.

The following hold:

  1. (i)

If $s<n_{a}$, then
$\left|M_{a,b}^{s,t}\right|=\phi\left(\frac{n}{p_{a}^{n_{a}}p_{b}^{t}}\right)p_{a}^{n_{a}-s-1}$.

  2. (ii)

If $t<n_{b}$, then
$\left|N_{a,b}^{s,t}\right|=\phi\left(\frac{n}{p_{a}^{s}p_{b}^{n_{b}}}\right)p_{b}^{n_{b}-t-1}$.

######  Proposition 5.12.

If $s<n_{a}$, then the set $E_{\frac{n}{p_{a}^{s+1}}}$ is contained in $B$.

###### Proof.

We have $p_{a}<p_{b}$ as $a<b$ by our assumption. By Proposition 5.3, the set
$E_{\frac{n}{p_{a}^{s+1}}}$ is contained in either $B$ or $X$. If possible,
suppose that $E_{\frac{n}{p_{a}^{s+1}}}$ is contained in $X$.

If $t=n_{b}$, then $J=[r]\setminus\\{b\\}$ and so
$J\setminus\\{a\\}=[r]\setminus\\{a,b\\}$. In this case, the subgroups
$S_{\frac{n}{p_{i}p_{a}^{s}p_{b}^{t}}}$, $i\in J\setminus\\{a\\}$, are
contained in $X$ by Proposition 5.5. If $t<n_{b}$, then the set
$E_{\frac{n}{p_{b}^{t+1}}}$ is contained in $B$ by Proposition 5.10. Since
$E_{\frac{n}{p_{a}^{s}p_{b}^{t}}}$ is contained in $A$, the subgroup
$S_{\frac{n}{p_{a}^{s}p_{b}^{t+1}}}$ must be contained in $X$. In this case
also, the subgroups $S_{\frac{n}{p_{i}p_{a}^{s}p_{b}^{t}}}$, $i\in
J\setminus\\{a\\}$, are contained in $X$. Thus $X$ contains
$K_{a,b}^{s,t}\setminus M_{a,b}^{s,t}$ in both cases.

The cut-set $X_{a,b}^{s,t}$ of $\mathcal{P}(C_{n})$ is a disjoint union of
$H_{a,b}^{s,t}$, $M_{a,b}^{s,t}$ and $K_{a,b}^{s,t}\setminus M_{a,b}^{s,t}$.
Since $X$ is a minimum cut-set of $\mathcal{P}(C_{n})$ containing
$H_{a,b}^{s,t}$ and $K_{a,b}^{s,t}\setminus M_{a,b}^{s,t}$, it follows that
the number of elements of $X$ which do not belong to $H_{a,b}^{s,t}$ or
$K_{a,b}^{s,t}\setminus M_{a,b}^{s,t}$ is at most
$\left|M_{a,b}^{s,t}\right|$. In particular, as $E_{\frac{n}{p_{a}^{s+1}}}$ is
disjoint from the cut-set $X_{a,b}^{s,t}$, we must have
$\left|E_{\frac{n}{p_{a}^{s+1}}}\right|\leq\left|M_{a,b}^{s,t}\right|$, that
is,

$\xi_{1}:=\left|E_{\frac{n}{p_{a}^{s+1}}}\right|-\left|M_{a,b}^{s,t}\right|\leq
0.$ (5)

We have
$\left|M_{a,b}^{s,t}\right|=\phi\left(\frac{n}{p_{a}^{n_{a}}p_{b}^{t}}\right)p_{a}^{n_{a}-s-1}$
by Proposition 5.11(i) and
$\left|E_{\frac{n}{p_{a}^{s+1}}}\right|=\phi\left(\frac{n}{p_{a}^{s+1}}\right)=\phi\left(\frac{n}{p_{a}^{n_{a}}p_{b}^{n_{b}}}\right)\phi\left(p_{a}^{n_{a}-s-1}p_{b}^{n_{b}}\right)$.
So

$\xi_{1}=\phi\left(\frac{n}{p_{a}^{n_{a}}p_{b}^{n_{b}}}\right)\left[\phi\left(p_{a}^{n_{a}-s-1}p_{b}^{n_{b}}\right)-p_{a}^{n_{a}-s-1}\phi\left(p_{b}^{n_{b}-t}\right)\right].$

We consider four different cases depending on $s+1=n_{a}$ or $s+1<n_{a}$, and
$t=n_{b}$ or $t<n_{b}$. If $s+1<n_{a}$ and $t<n_{b}$, then
$\xi_{1}=\phi\left(\frac{n}{p_{a}^{n_{a}}p_{b}^{n_{b}}}\right)\times
p_{a}^{n_{a}-s-2}p_{b}^{n_{b}-t-1}\times\phi(p_{b})\left[p_{b}^{t}\phi(p_{a})-p_{a}\right]>0$.
If $s+1=n_{a}$ and $t<n_{b}$, then
$\xi_{1}=\phi\left(\frac{n}{p_{a}^{n_{a}}p_{b}^{n_{b}}}\right)\left[\phi\left(p_{b}^{n_{b}}\right)-\phi\left(p_{b}^{n_{b}-t}\right)\right]>0$.
If $s+1=n_{a}$ and $t=n_{b}$, then $p_{b}\geq 3$ gives
$\xi_{1}=\phi\left(\frac{n}{p_{a}^{n_{a}}p_{b}^{n_{b}}}\right)\left[\phi\left(p_{b}^{n_{b}}\right)-1\right]>0$.
In these three cases, we get a contradiction to (5).

Now consider $s+1<n_{a}$ and $t=n_{b}$. Then
$\xi_{1}=\phi\left(\frac{n}{p_{a}^{n_{a}}p_{b}^{n_{b}}}\right)\left[\phi\left(p_{a}^{n_{a}-s-1}p_{b}^{n_{b}}\right)-p_{a}^{n_{a}-s-1}\right]\geq
0$, with equality if and only if
$(p_{a},p_{b},t)=(p_{a},p_{b},n_{b})=(2,3,1)$. Thus we get a contradiction to
(5) if $(p_{a},p_{b},n_{b})\neq(2,3,1)$. Assume that
$(p_{a},p_{b},n_{b})=(2,3,1)$. Then $\xi_{1}=0$, giving
$\left|E_{\frac{n}{p_{a}^{s+1}}}\right|=\left|M_{a,b}^{s,t}\right|$. So

$\displaystyle|X|$
$\displaystyle\geq\left|H_{a,b}^{s,t}\right|+\left|K_{a,b}^{s,t}\setminus
M_{a,b}^{s,t}\right|+\left|E_{\frac{n}{p_{a}^{s+1}}}\right|=\left|H_{a,b}^{s,t}\right|+\left|K_{a,b}^{s,t}\setminus
M_{a,b}^{s,t}\right|+\left|M_{a,b}^{s,t}\right|=\left|X_{a,b}^{s,t}\right|.$

By the minimality of $|X|$, we must have
$X=H_{a,b}^{s,t}\bigcup\left(K_{a,b}^{s,t}\setminus
M_{a,b}^{s,t}\right)\bigcup E_{\frac{n}{p_{a}^{s+1}}}$.

On the other hand, as $s+2\leq n_{a}$, the set $E_{\frac{n}{p_{a}^{s+2}}}$ is
contained in either $X$ or $B$ by Proposition 5.3. If the latter holds, then
the subgroup $S_{\frac{n}{p_{a}^{s+2}p_{b}}}$ would be contained in $X$. In
both cases, we find that $X$ contains additional elements of order
$\frac{n}{p_{a}^{s+2}}$ or $\frac{n}{p_{a}^{s+2}p_{b}}$ not belonging to any
of the sets $H_{a,b}^{s,t}$, $K_{a,b}^{s,t}\setminus M_{a,b}^{s,t}$ and
$E_{\frac{n}{p_{a}^{s+1}}}$, a final contradiction. ∎

######  Proposition 5.13.

If $t<n_{b}$, then the set $E_{\frac{n}{p_{b}^{t+1}}}$ is contained in $B$.

###### Proof.

We shall apply a similar argument as used in the proof of Proposition 5.12. By
Proposition 5.3, the set $E_{\frac{n}{p_{b}^{t+1}}}$ is contained in either
$B$ or $X$. If possible, suppose that $E_{\frac{n}{p_{b}^{t+1}}}$ is contained
in $X$.

If $s=n_{a}$, then $J=[r]\setminus\\{a\\}$ and so
$J\setminus\\{b\\}=[r]\setminus\\{a,b\\}$. In this case, the subgroups
$S_{\frac{n}{p_{i}p_{a}^{s}p_{b}^{t}}}$, $i\in J\setminus\\{b\\}$, are
contained in $X$ by Proposition 5.5. If $s<n_{a}$, then the set
$E_{\frac{n}{p_{a}^{s+1}}}$ is contained in $B$ by Proposition 5.12 and so the
subgroup $S_{\frac{n}{p_{a}^{s+1}p_{b}^{t}}}$ must be contained in $X$. In
this case also, the subgroups $S_{\frac{n}{p_{i}p_{a}^{s}p_{b}^{t}}}$, $i\in
J\setminus\\{b\\}$, are contained in $X$. Thus $X$ contains
$K_{a,b}^{s,t}\setminus N_{a,b}^{s,t}$ in both cases.

The cut-set $X_{a,b}^{s,t}$ of $\mathcal{P}(C_{n})$ is a disjoint union of
$H_{a,b}^{s,t}$, $N_{a,b}^{s,t}$ and $K_{a,b}^{s,t}\setminus N_{a,b}^{s,t}$.
Since $X$ is a minimum cut-set of $\mathcal{P}(C_{n})$ containing
$H_{a,b}^{s,t}$ and $K_{a,b}^{s,t}\setminus N_{a,b}^{s,t}$, it follows that
the number of elements of $X$ which do not belong to $H_{a,b}^{s,t}$ or
$K_{a,b}^{s,t}\setminus N_{a,b}^{s,t}$ is at most
$\left|N_{a,b}^{s,t}\right|$. In particular, as $E_{\frac{n}{p_{b}^{t+1}}}$ is
disjoint from the cut-set $X_{a,b}^{s,t}$, we must have
$\left|E_{\frac{n}{p_{b}^{t+1}}}\right|\leq\left|N_{a,b}^{s,t}\right|$, that
is,

$\xi_{2}:=\left|E_{\frac{n}{p_{b}^{t+1}}}\right|-\left|N_{a,b}^{s,t}\right|\leq
0.$ (6)

We have
$\left|N_{a,b}^{s,t}\right|=\phi\left(\frac{n}{p_{a}^{s}p_{b}^{n_{b}}}\right)p_{b}^{n_{b}-t-1}$
by Proposition 5.11(ii) and
$\left|E_{\frac{n}{p_{b}^{t+1}}}\right|=\phi\left(\frac{n}{p_{b}^{t+1}}\right)=\phi\left(\frac{n}{p_{a}^{n_{a}}p_{b}^{n_{b}}}\right)\phi\left(p_{a}^{n_{a}}p_{b}^{n_{b}-t-1}\right)$.
So

$\xi_{2}=\phi\left(\frac{n}{p_{a}^{n_{a}}p_{b}^{n_{b}}}\right)\left[\phi\left(p_{a}^{n_{a}}p_{b}^{n_{b}-t-1}\right)-\phi\left(p_{a}^{n_{a}-s}\right)p_{b}^{n_{b}-t-1}\right].$

We show that $\xi_{2}>0$, thus getting a contradiction to (6).

Since $t<n_{b}$, we have $(p_{a},n_{a})\neq(2,1)$ by Proposition 5.7. We
consider four different cases depending on $s=n_{a}$ or $s<n_{a}$, and
$t+1=n_{b}$ or $t+1<n_{b}$.

If $s<n_{a}$ and $t+1<n_{b}$, then
$\xi_{2}=\phi\left(\frac{n}{p_{a}^{n_{a}}p_{b}^{n_{b}}}\right)\times
p_{a}^{n_{a}-s-1}p_{b}^{n_{b}-t-2}\times\phi(p_{a})\left[p_{a}^{s}\phi(p_{b})-p_{b}\right]>0$.
If $s<n_{a}$ and $t+1=n_{b}$, then
$\xi_{2}=\phi\left(\frac{n}{p_{a}^{n_{a}}p_{b}^{n_{b}}}\right)\left[\phi\left(p_{a}^{n_{a}}\right)-\phi\left(p_{a}^{n_{a}-s}\right)\right]>0$.
If $s=n_{a}$ and $t+1=n_{b}$, then
$\xi_{2}=\phi\left(\frac{n}{p_{a}^{n_{a}}p_{b}^{n_{b}}}\right)\left[\phi\left(p_{a}^{n_{a}}\right)-1\right]>0$
as $(p_{a},n_{a})\neq(2,1)$. If $s=n_{a}$ and $t+1<n_{b}$, then
$\xi_{2}=\phi\left(\frac{n}{p_{a}^{n_{a}}p_{b}^{n_{b}}}\right)\left[\phi\left(p_{a}^{n_{a}}p_{b}^{n_{b}-t-1}\right)-p_{b}^{n_{b}-t-1}\right]>0$
as $(p_{a},n_{a})\neq(2,1)$. ∎

######  Proposition 5.14.

$X=X_{a,b}^{s,t}$.

###### Proof.

The set $E_{\frac{n}{p_{a}^{s}p_{b}^{t}}}$ is contained in $A$ and the sets
$E_{\frac{n}{p_{i}}}$, $i\in[r]\setminus\\{a,b\\}$, are contained in $B$. By
Corollary 5.6, we may assume that $(s,t)\neq(n_{a},n_{b})$. If $s<n_{a}$, then
$E_{\frac{n}{p_{a}^{s+1}}}$ is contained in $B$ by Proposition 5.12. If
$t<n_{b}$, then $E_{\frac{n}{p_{b}^{t+1}}}$ is contained in $B$ by Proposition
5.13. It then follows that the subgroups
$S_{\frac{n}{p_{i}p_{a}^{s}p_{b}^{t}}}$ for $i\in J$ and hence the set
$K_{a,b}^{s,t}$ must be contained in $X$. By Proposition 5.5, $H_{a,b}^{s,t}$
is contained in $X$. Thus the cut-set $X_{a,b}^{s,t}$ of $\mathcal{P}(C_{n})$
is contained in $X$. Since $X$ is a minimum cut-set of $\mathcal{P}(C_{n})$,
we must have $X=X_{a,b}^{s,t}$. ∎

Acknowledgement:

The first author was supported by the Council of Scientific and Industrial
Research grant no. 09/1248(0004)/2019-EMR-I, Ministry of Human Resource
Development, Government of India.

## References

  * [1] J. Abawajy, A. Kelarev and M. Chowdhury, Power graphs: a survey, Electron. J. Graph Theory Appl. 1 (2013), no. 2, 125–147.
  * [2] P. J. Cameron and S. Ghosh, The power graph of a finite group, Discrete Math. 311 (2011), no. 13, 1220–1222.
  * [3] I. Chakrabarty, S. Ghosh and M. K. Sen, Undirected power graphs of semigroups, Semigroup Forum 78 (2009), no. 3, 410–426.
  * [4] S. Chattopadhyay, K. L. Patra and B. K. Sahoo, Vertex connectivity of the power graph of a finite cyclic group, Discrete Appl. Math. 266 (2019), 259–271.
  * [5] S. Chattopadhyay, K. L. Patra and B. K. Sahoo, Minimal cut-sets in the power graph of certain finite non-cyclic groups, Comm. Algebra 49 (2021), no. 3, 1195–1211.
  * [6] S. Chattopadhyay, K. L. Patra and B. K. Sahoo, Vertex connectivity of the power graph of a finite cyclic group II, J. Algebra Appl. 19 (2020), no. 2, 2050040, 25 pp.
  * [7] S. Chattopadhyay, K. L. Patra and B. K. Sahoo, Erratum: Vertex connectivity of the power graph of a finite cyclic group II, J. Algebra Appl. 19 (2020), no. 2, 2092001, 2 pp.
  * [8] B. Curtin and G. R. Pourgholi, Edge-maximality of power graphs of finite cyclic groups, J. Algebraic Combin. 40 (2014), no. 2, 313–330.
  * [9] B. Curtin and G. R. Pourgholi, An Euler totient sum inequality, J. Number Theory 163 (2016), 101–113.
  * [10] A. Doostabadi, A. Erfanian and A. Jafarzadeh, Some results on the power graphs of finite groups, ScienceAsia 41 (2015), 73–78.
  * [11] M. Feng, X. Ma and K. Wang, The structure and metric dimension of the power graph of a finite group, European J. Combin. 43 (2015), 82–97.
  * [12] M. Feng, X. Ma and K. Wang, The full automorphism group of the power (di)graph of a finite group, European J. Combin. 52 (2016), part A, 197–206.
  * [13] A. V. Kelarev and S. J. Quinn, A combinatorial property and power graphs of groups, in Contributions to General Algebra, Vol. 12 (Vienna, 1999), 229–235, Heyn, Klagenfurt, 2000.
  * [14] S. Kirkland, A. R. Moghaddamfar, S. Navid Salehy, S. Nima Salehy and M. Zohourattar, The complexity of power graphs associated with finite groups, Contrib. Discrete Math. 13 (2018), no. 2, 124–136.
  * [15] A. Kumar, L. Selvaganesh, P. J. Cameron and T. Tamizh Chelvam, Recent developments on the power graph of finite groups - a survey, AKCE Int. J. Graphs Comb. 18 (2021), no. 2, 65–94.
  * [16] X. Ma and M. Feng, On the chromatic number of the power graph of a finite group, Indag. Math. (N.S.) 26 (2015), no. 4, 626–633.
  * [17] X. Ma, M. Feng and K. Wang, The strong metric dimension of the power graph of a finite group, Discrete Appl. Math. 239 (2018), 159–164.
  * [18] X. Ma and L. Zhai, Strong metric dimensions for power graphs of finite groups, Comm. Algebra 49 (2021), no. 11, 4577–4587.
  * [19] M. Mirzargar, A. R. Ashrafi and M. J. Nadjafi-Arani, On the power graph of a finite group, Filomat 26 (2012), no. 6, 1201–1208.
  * [20] M. Mirzargar, R. Scapellato, Finite groups with the same power graph, Comm. Algebra 50 (2022), no. 4, 1400–1406.
  * [21] R. P. Panda and K. V. Krishna, On connectedness of power graphs of finite groups, J. Algebra Appl. 17 (2018), no. 10, 1850184, 20 pp.
  * [22] Y. Shitov, Coloring the power graph of a semigroup, Graphs Combin. 33 (2017), no. 2, 485–487.

Addresses: Sanjay Mukherjee, Kamal Lochan Patra, Binod Kumar Sahoo

  1. 1)

School of Mathematical Sciences
National Institute of Science Education and Research (NISER), Bhubaneswar
P.O.- Jatni, District- Khurda, Odisha–752050, India

  2. 2)

Homi Bhabha National Institute (HBNI)
Training School Complex, Anushakti Nagar, Mumbai–400094, India

E-mails<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>