MSC 2020: Primary 05C40; Secondary 05C75, 13A99, 05C69.

Keywords: comaximal graph, vertex connectivity, squarefree integer ring, Chinese remainder theorem, disjointness graph.

1 Introduction↩︎

Graphs built from algebraic objects frequently expose structural information that is hard to read directly from the original algebra. Among the best known examples are zero-divisor graphs, unit graphs, annihilating-ideal graphs, and comaximal graphs. In the present setting, the relevant object is the comaximal graph \(\Gamma(R)\) of a commutative ring \(R\) with identity, introduced by Sharma and Bhatwadekar [1]. Its vertices are the elements of \(R\), and two distinct elements are adjacent exactly when they generate the whole ring as an ideal. Even this basic definition already mixes algebra and graph theory in a natural way, ideal generation becomes adjacency, maximal ideals manifest themselves as obstruction sets, and ring decomposition often turns into graph decomposition. The finite residue ring \(\mathbb{Z}_n\) is especially attractive because it is simultaneously elementary, canonical, and rich enough to display nontrivial spectral and connectivity phenomena.

The graph \(\Gamma(\mathbb{Z}_n)\) has been investigated from several viewpoints. Structural aspects of comaximal graphs for general commutative rings were studied by Maimani, Salimi, Sattari, and Yassemi [2], by Moconja and Petrović [3], and by Samei [4]. These works clarified how algebraic decompositions of the ring govern graph-theoretic properties such as connectedness, domination, and local neighborhoods. On the graph-theoretic side, the study of connectivity and Laplacian invariants belongs to the broader program of understanding how robust a network is under vertex failures, for that background we refer to West [5]. The spectral language initiated by Fiedler [6] and surveyed by Merris [7], Mohar [8], Brouwer and Haemers [9], and de Abreu [10] is especially relevant because algebraic connectivity and vertex connectivity often interact in subtle ways. Other algebraic invariants are given in [11]–[15].

A decisive step for \(\Gamma(\mathbb{Z}_n)\) was made in [16], [17], they analyzed the Laplacian spectrum and several structural features of the graph. The induced subgraph on the nonzero nonunit elements, \[G_2=\Gamma(\mathbb{Z}_n)\big[\{x\in \mathbb{Z}_n:\;x\neq 0,\;\gcd(x,n)\neq 1\}\big],\] appears as the genuinely nontrivial core of the full comaximal graph. Indeed, units are universal vertices, while the zero element has a highly controlled neighborhood. An equitable partition of \(G_2\) can be obtained based on proper divisor \(d_{i}\). Its structure is described through divisor classes (see remark 4), several spectral statements are proved, and an upper bound if established for the vertex connectivity of \(G_2\) when \(n\) is squarefree [16], [17]. The paper [16] then ended with a natural open problem: determine the exact value of \(\kappa(G_2)\) for \[n=p_1p_2\cdots p_m,\qquad 2\leq p_1<p_2<\cdots<p_m,\] where the \(p_i\) are prime. This is Problem 7.2 in [16].

The importance of this question is both technical and conceptual. Technically, vertex connectivity measures the smallest number of vertices whose deletion disconnects the graph, and hence it is the most basic fault-tolerance parameter. In the arithmetic setting of \(\Gamma(\mathbb{Z}_n)\), a minimum vertex cut identifies the thinnest layer through which the nontrivial comaximal interactions must pass. Conceptually, an exact formula for \(\kappa(G_2)\) reveals which prime factors control the fragile directions of the graph. At first sight one might expect the answer to depend on the whole factorization of \(n\) in a complicated way, because the adjacency relation on \(G_2\) is defined globally through comaximality. One of the main messages of the present paper is that, after the right change of viewpoint, the answer becomes remarkably clean.

Our method is based on the Chinese remainder theorem. When \(n\) is squarefree, the ring \(\mathbb{Z}_n\) is isomorphic to the direct product \(\mathbb{F}_{p_1}\times\cdots\times \mathbb{F}_{p_m}\), and every residue class can be written as a coordinate vector. For vertices of \(G_2\), at least one coordinate is zero and at least one coordinate is nonzero. We therefore encode a vertex by its zero-set, namely the subset of coordinates on which the vector vanishes. This transforms the ring-theoretic adjacency relation into an elementary set-theoretic one: two vertices are adjacent if and only if their zero-sets are disjoint. In other words, \(G_2\) becomes a weighted blow-up of a disjointness graph on the nonempty proper subsets of \([m]=\{1,2,\dots,m\}\). Once this model is available, the exact connectivity problem can be attacked by purely combinatorial means.

The first outcome of this approach is a transparent decomposition of the vertex set into layers \(X_S\), indexed by the nonempty proper subsets \(S\subsetneq [m]\). Each layer \(X_S\) consists of all vertices whose zero-set is \(S\), and its cardinality is given explicitly by \(|X_S|=\prod_{i\notin S}(p_i-1).\) The second outcome is an exact degree formula. For a vertex in \(X_S\), the degree depends only on \(S\), and the minimum degree occurs precisely on the layer whose zero-set omits the largest prime index. The third and decisive step is to show that the layer \(X_{{m}}\) is a separator of size \(\prod_{i=1}^{m-1}(p_i-1)\) and that removing fewer vertices can never disconnect the graph. This proves the exact formula \[\kappa(G_2)=\prod_{i=1}^{m-1}(p_i-1)=\frac{\phi(n)}{p_m-1}.\] Thus the upper bound from [16] is sharp, and the graph \(G_2\) turns out to be maximally connected in the classical sense that \(\kappa(G_2)=\delta(G_2)\).

Beyond the open problem itself, the support-set model yields several additional consequences. We obtain a complete distance formula between two vertices in terms of their zero-sets, and this leads to a short proof that the diameter is \(3\) whenever \(m\geq 3\). We also identify the central layers of the graph and provide a simple algorithm for computing \(\kappa(G_2)\) once the distinct prime factors of \(n\) are known. The algorithmic viewpoint is useful, as it separates two stages of the computation, prime factorization, which is external to the graph problem, and the graph-theoretic evaluation of the connectivity, which is linear in the number of prime factors. In this way the paper not only answers the open problem but also clarifies the mechanism behind the answer.

From a literature perspective, the main novelty of the present work lies in replacing the divisor-based description of [16], [17] by a support-set geometry tailored to the squarefree case. That reformulation seems to be absent from the existing comaximal-graph literature. It reveals that \(G_2\) behaves like a nonuniform Kneser-type disjointness graph, with weights inherited from the residue sizes of the coordinate fields. This change of model simplifies the proofs, isolates the extremal cut, and naturally suggests further questions for nonsquarefree moduli, edge connectivity, and the classification of all minimum separators.

The article is organized as: Section 2 fixes notation, records the known results that we use repeatedly, and explains the precise gap left open by previous work (in particular Problem 7.2 in [16]). Section 3 introduces the support-set representation and proves that \(G_2\) is a weighted blow-up of a disjointness graph. Section 4 derives the neighborhood and degree formulas, identifies the unique minimum-degree layer, and prepares the connectivity argument. Section 5 contains the exact solution to Problem 7.2 o f[16], proves that the bound is sharp, and deduces maximal connectivity. Section 6 studies metric consequences of the model, including an exact distance formula, the diameter, and short routing statements. Section 7 gives an explicit algorithm, establishes its correctness and complexity, and collects numerical comparisons and computation tables. Finally, Section 8 summarizes the contribution, discusses limitations, and records directions for further research.

2 Preliminaries and notation↩︎

Throughout the paper, all graphs are finite, simple, and undirected. For a graph \(G\), the vertex set is denoted by \(V(G)\), the neighborhood of a vertex \(v\) by \(N_G(v)\), the degree of \(v\) by \(\deg_G(v)\), the minimum degree by \(\delta(G)\), the vertex connectivity by \(\kappa(G)\), and the edge connectivity by \(\lambda(G)\). Two vertices \(u\neq v\) are called false twins, if they have exactly the same open neighborhood and are not adjacent, that is, \(N(u) = N(v)\) and \(uv \notin E(G).\) We fix a squarefree modulus \(n=p_1p_2\cdots p_m,\) with \(2\leq p_1<p_2<\cdots<p_m,\) where \(m\geq 2\) and the \(p_i\) are distinct primes. We write \([m]=\{1,2,\dots,m\}\). Let \(\Gamma(\mathbb{Z}_n)\) be the comaximal graph of \(\mathbb{Z}_n\), and let \(G_2\) be the induced subgraph on the nonzero nonunit elements. For a subset \(S\subseteq [m]\), we write \(d_S=\prod_{i\in S}p_i,\) with the convention that the empty product equals \(1\). For a vertex \(x\in G_2\), its zero-set will later be denoted by \(Z(x)\subseteq [m]\). For a squarefree modulus \(n\), the support classes in \(G_2\) will be indexed by nonempty proper subsets of \([m]\).

The following known facts form the background of our arguments. The next theorem is the arithmetic form of the Chinese remainder theorem used to encode vertices by coordinate zero patterns.

The following criterion translates comaximality in \(\mathbb{Z}_n\) into a gcd condition, (Banerjee, eq. (2) [16], see also [17]). For \(x,y\in \mathbb{Z}_n\), the vertices \(x\) and \(y\) are adjacent in \(\Gamma(\mathbb{Z}_n)\) if and only if \[\label{prop:gcdcriterion} \gcd\big(\gcd(x,n),\gcd(y,n)\big)=1 \qquad\text{or}\qquad \gcd(x,y,n)=1.\tag{1}\]

The next inequality is the standard connectivity chain that will allow us to identify edge connectivity once vertex connectivity is known.

The following statement records the best available bound from the earlier literature and is the starting point of the present paper.

The next observation connects the ring-theoretic notation from [16], [17] with the graph studied here.

The existing literature gives a strong structural and spectral description of \(\Gamma(\mathbb{Z}_n)\) and, in particular, an upper bound for \(\kappa(G_2)\) in the squarefree case [16]. What was missing is an exact formula for \(\kappa(G_2)\), a proof of sharpness of the bound \(\kappa(G_2)\leq \phi(p_1p_2\cdots p_{m-1})\), and a combinatorial explanation of why the extremal separator is tied to the largest prime factor. Likewise, no explicit distance formula for \(G_2\) seems to have been isolated in the squarefree setting. The remainder of the paper fills these gaps.

3 A weighted disjointness model for \(G_2\)↩︎

The results of this section recast \(G_2\) as a weighted disjointness graph. This viewpoint is not explicit in [16] and is the combinatorial engine behind all later connectivity and distance proofs.

Using Theorem 1, we identify \(\mathbb{Z}_n\) with \(\mathbb{F}_{p_1}\times\cdots\times\mathbb{F}_{p_m}\). For \(x=(x_1,\dots,x_m)\in \mathbb{Z}_n\), define the zero-set \[Z(x)=\{i\in [m]: x_i=0\}.\] For every nonempty proper subset \(S\subsetneq [m]\), define \[X_S=\{x\in V(G_2): Z(x)=S\}.\]

The next proposition identifies exactly which zero-sets occur in the graph \(G_2\).

A vertex of \(G_2\) is by definition nonzero and nonunit. In the product ring \(\mathbb{F}_{p_1}\times\cdots\times\mathbb{F}_{p_m}\), an element is a unit exactly when all coordinates are nonzero, and it is zero exactly when all coordinates are zero. Therefore, \(x\) is nonzero and nonunit if and only if at least one coordinate vanishes and at least one coordinate is nonzero, which is equivalent to saying that \(Z(x)\) is nonempty and proper. 0◻

The next proposition gives the exact size of each support class.

A vector lies in \(X_S\) exactly when its coordinates indexed by \(S\) are zero and its coordinates indexed by \([m]\setminus S\) are nonzero. The coordinates in \(S\) are forced, while for every \(i\notin S\) there are exactly \(p_i-1\) nonzero choices in \(\mathbb{F}_{p_i}\). Multiplying the independent choices, we obtain \[|X_S|=\prod_{i\notin S}(p_i-1).\] 0◻

The next theorem converts ring-theoretic adjacency into set-theoretic disjointness.

By Equation 1 , \(x\) and \(y\) are adjacent in \(\Gamma(\mathbb{Z}_n)\) if and only if \[\gcd\big(\gcd(x,n),\gcd(y,n)\big)=1.\] Since \(n\) is squarefree and \(x\in X_S\), we have \(\gcd(x,n)=d_S=\prod_{i\in S}p_i\). Likewise, \(\gcd(y,n)=d_T=\prod_{i\in T}p_i\). Thus, we have \[\gcd\big(\gcd(x,n),\gcd(y,n)\big)=\gcd(d_S,d_T)=\prod_{i\in S\cap T}p_i.\] This equals \(1\) precisely when \(S\cap T=\emptyset\). Since \(G_2\) is an induced subgraph of \(\Gamma(\mathbb{Z}_n)\), and the same criterion describes adjacency inside \(G_2\). 0◻

The following corollary identifies the global structure of \(G_2\) as a weighted blow-up.

By Proposition 5, the vertex set of \(G_2\) is the disjoint union of the classes \(X_S\) over all nonempty proper \(S\subsetneq [m]\). By Theorem 7, there are no edges inside a class \(X_S\), and between two distinct classes \(X_S\) and \(X_T\) either all possible edges appear or none appear, according as \(S\cap T=\emptyset\) or not. This is exactly the definition of the stated blow-up of \(\mathcal{D}_m\). 0◻

The next corollary records the order of the graph and serves as a consistency check for the partition.

A vertex of \(G_2\) is precisely a residue class modulo \(n\) that is neither zero nor a unit. There are \(n\) residue classes in total, exactly one of them is zero, and exactly \(\phi(n)\) of them are units. Hence, we obtain \[|V(G_2)|=n-1-\phi(n).\] 0◻

The partition in terms of the gcd classes \(A_d\) is already sufficient for spectral calculations [16], [17], but the support-set indexing used here is sharper for the squarefree case. It turns the arithmetic of gcd values into the combinatorics of disjoint subsets and makes the location of the extremal cut visible before any calculation begins.

4 Degree profile and local structure↩︎

This section derives explicit local formulas that are missing in the existing literature. In particular, we identify the unique minimum-degree layer and isolate the exact neighborhood that later becomes a minimum vertex cut.

For \(S\subseteq [m]\), we write \(S^c=[m]\setminus S\). The next proposition identifies the entire neighborhood of a vertex from its zero-set alone.

By Theorem 7, a vertex \(y\in X_T\) is adjacent to \(x\in X_S\) if and only if \(T\cap S=\emptyset\). Since every \(T\) indexing a vertex of \(G_2\) is nonempty and proper, the condition \(T\cap S=\emptyset\) is equivalent to \(\emptyset\neq T\subseteq S^c\). The union is disjoint, since the classes \(X_T\) are disjoint. 0◻

The next theorem gives an exact degree formula in terms of the support set.

The first identity follows immediately from Proposition 8 and Proposition 6, since the degree is the sum of the sizes of all neighboring classes. For the second identity, we count the neighbors directly in the coordinate model. Since \(x\in X_S\), a vector \(y=(y_1,\dots,y_m)\) is adjacent to \(x\) if and only if the following two conditions hold: (i) for every \(i\in S\), the coordinate \(y_i\) is nonzero, and (ii) on the complementary set \(S^c\), the vector \((y_j)_{j\in S^c}\) is not entirely nonzero, as \(y\) must remain a nonunit. There are \(\prod_{i\in S}(p_i-1)\) ways to choose the coordinates indexed by \(S\). On the coordinates indexed by \(S^c\), there are \(\prod_{j\in S^c}p_j\) arbitrary choices and \(\prod_{j\in S^c}(p_j-1)\) forbidden choices in which all coordinates are nonzero. Multiplying these independent choices, we obtain \[\deg(x)=\prod_{i\in S}(p_i-1)\left(\prod_{j\in S^c}p_j-\prod_{j\in S^c}(p_j-1)\right).\] 0◻

Figure 2 shows the block diagram for the counting argument in Theorem 9, where it represents the two independent parts of the neighbor count, forced nonzero coordinates on \(S\) and partially constrained coordinates on \(S^c\).

The following corollary shows that each layer consists of pairwise nonadjacent vertices with identical open neighborhoods.

Since \(S\cap S=S\neq\emptyset\), Theorem 7 shows that \(x\) and \(y\) are not adjacent. The equality of neighborhoods is exactly the second statement in Proposition 8. 0◻

The next theorem locates the minimum degree exactly.

Let \(x\in X_S\), and and let \(J=S^c\). Then by Proposition 8, we have \[N(x)=\bigsqcup_{\emptyset\neq T\subseteq J}X_T.\] Hence, \(N(x)\) contains each singleton class \(X_{\{j\}}\) with \(j\in J\). Therefore, we obtain \[\deg(x)\geq \sum_{j\in J}|X_{{j}}|.\] Now, \(|X_{\{j\}}|=\prod_{i\neq j}(p_i-1).\) As \(p_1<\cdots<p_m\), the smallest among these singleton-class sizes is \[|X_{\{m\}}|=\prod_{i=1}^{m-1}(p_i-1).\] If \(|J|\geq 2\), then \(\deg(x)\) contains at least two disjoint singleton layers in its neighborhood, so we have \[\deg(x)\geq |X_{\{j_1\}}|+|X_{\{j_2\}}|>|X_{\{m\}}|\] for any distinct \(j_1,j_2\in J\). Thus, no such vertex has minimum degree. If \(|J|=1\), say \(J=\{j\}\), then \(S=[m]\setminus\{j\}\). In this case, the only nonempty subset of \(J\) is \(\{j\}\) itself, so Proposition 8 implies that \(N(x)=X_{\{j\}},\) and therefore, we have \[\deg(x)=|X_{\{j\}}|=\prod_{i\neq j}(p_i-1).\] This is minimized exactly when \(j=m\), and hence \[\delta(G_2)=|X_{\{m\}}|=\prod_{i=1}^{m-1}(p_i-1),\] with equality holds precisely on the class \(X_{[m]\setminus\{m\}}\). 0◻

The next corollary identifies the common neighborhood of every minimum-degree vertex.

This is the special case \(S=[m]\setminus\{m\}\) of Proposition 8, since then \(S^c=\{m\}\) and the only nonempty subset of \(S^c\) is \(\{m\}\). 0◻

In [16], [17], the authors isolates a separator of cardinality \(\phi(p_1\cdots p_{m-1})\), but the local reason for its extremality is not transparent there. Theorem 10 and Corollary 4 show that this separator is exactly the common neighborhood of the unique minimum-degree layer. This perspective is the key to the exact connectivity proof of Problem 7.2 in [16].

5 Exact solution of Problem 7.2↩︎

This section contains the main contribution of the paper, the exact value of \(\kappa(G_2)\). Theorem 11 sharpens Proposition 3 from an upper bound to an equality and proves, in addition, that \(G_2\) is maximally connected.

The next lemma recovers Banerjee’s separator in the support-set language and shows that it really disconnects the graph.

For any vertex \(x\in X_{[m]\setminus\{m\}}\), Corollary 4, gives \(N(x)=X_{\{m\}}.\) Therefore, after deleting the entire class \(X_{\{m\}}\), every vertex of \(X_{[m]\setminus\{m\}}\) becomes isolated. Hence, \(G_2-X_{\{m\}}\) is disconnected, so \(X_{\{m\}}\) is a vertex cut. The cardinality formula follows from Proposition 6. 0◻

The next lemma shows that any smaller deletion leaves at least one vertex in the critical class \(X_{\{m\}}\).

By Proposition 6, we have \[|X_{\{m\}}|=\prod_{i=1}^{m-1}(p_i-1).\] Since \(|W|<|X_{\{m\}}|\), the set \(W\) cannot contain all vertices of \(X_{\{m\}}\). Hence some \(u\in X_{\{m\}}\setminus W\) survives. 0◻

The next lemma shows that every surviving vertex whose zero-set avoids \(m\) is directly linked to the surviving anchor \(u\).

Since \(m\notin S\), we have \(S\cap \{m\}=\emptyset\). Theorem 7 now implies that \(v\) is adjacent to every vertex of \(X_{\{m\}}\), in particular to \(u\). 0◻

The next lemma is the key robustness step, every surviving vertex whose zero-set contains \(m\) still reaches the anchor through one surviving neighbor.

Since \(v\) survives, it belongs to some class \(X_S\) with \(m\in S\). So, by Theorem 10, we have \[\deg(v)\geq \delta(G_2)=\prod_{i=1}^{m-1}(p_i-1).\] As \(|W|\) is strictly smaller than this number, the deleted set \(W\) cannot contain all neighbors of \(v\). Hence, there exists a neighbor \(w\in N(v)\setminus W.\) Since \(v\) and \(w\) are adjacent, Theorem 7 gives \(Z(v)\cap Z(w)=\emptyset.\) As \(m\in Z(v)\), it follows that \(m\notin Z(w)\). Therefore, Lemma 3 implies that \(w\) is adjacent to \(u\). Hence, \(v-w-u\) is a path in \(G_2-W\), and \(v\) lies in the same component as \(u\). 0◻

The next theorem solves Problem 7.2 of [16] completely.

Lemma 1 gives the upper bound \[\kappa(G_2)\leq \prod_{i=1}^{m-1}(p_i-1).\] For the reverse inequality, let \(W\subseteq V(G_2)\) satisfy \[|W|<\prod_{i=1}^{m-1}(p_i-1).\] By Lemma 2, there exists a surviving vertex \(u\in X_{{m}}\setminus W\). Now take any surviving vertex \(v\in V(G_2)\setminus W\). If \(m\notin Z(v)\), then by Lemma 3, \(v\) is adjacent to \(u\). If \(m\in Z(v)\), then by Lemma 4, \(v\) is connected to \(u\) in \(G_2-W\). Thus, every surviving vertex lies in the same connected component as \(u\), so \(G_2-W\) is connected. Therefore, no deletion of fewer than \(\prod_{i=1}^{m-1}(p_i-1)\) vertices disconnects \(G_2\). Combining the upper and lower bounds gives \(\kappa(G_2)=\prod_{i=1}^{m-1}(p_i-1).\) Since \(\phi(n)=\prod_{i=1}^m(p_i-1)\), the equivalent form \(\kappa(G_2)=\frac{\phi(n)}{p_m-1}\) follows immediately. 0◻

The next corollary shows that the graph is maximally connected.

Theorem 11 gives the value of \(\kappa(G_2)\), and Theorem 10 gives the same value for \(\delta(G_2)\). 0◻

The next corollary identifies the edge connectivity as well.

By Proposition 2, we have \[\kappa(G_2)\leq \lambda(G_2)\leq \delta(G_2).\] Corollary 5 shows that the leftmost and rightmost terms are equal. Hence the middle term must equal them as well. 0◻

Proposition 3 is exactly the estimate left open in [16]. Theorem 11 proves that this estimate is always sharp in the squarefree case and further reveals a stronger property, namely maximal connectivity.

Recall the case \(n=30=2\cdot 3\cdot 5,\) (see Figure 4). The class \(X_{\{3\}}\) is a minimum cut. After deleting it, the class \(X_{\{1,2\}}\) becomes isolated. Dashed edges are removed together with the cut class.

6 Metric consequences and short routing↩︎

The support-set model also yields precise metric information. To the best of our knowledge, the exact distance formula below has not been stated for \(G_2\) in the squarefree case. From now on, unless explicitly stated otherwise, we assume \(m\geq 3\) whenever metric statements involving diameter \(3\) or the center of the graph are discussed.

The next theorem determines the distance between two vertices entirely from their zero-sets.

If \(S\cap T=\emptyset\), then \(x\) and \(y\) are adjacent by Theorem 7, so the distance is \(1\). Assume now that \(S\cap T\neq\emptyset\). Then \(x\) and \(y\) are not adjacent. If \(S\cup T\neq [m]\), choose \(k\in [m]\setminus (S\cup T)\). Since \(m\geq 3\) is not needed in this case, by Proposition 6, the singleton class \(X_{{k}}\) is nonempty. Any vertex \(z\in X_{{k}}\) satisfies \({k}\cap S=\emptyset\) and \({k}\cap T=\emptyset\), so by Theorem 7, \(x\sim z\) and \(z\sim y\). Hence \(d(x,y)\leq 2\). As \(x\) and \(y\) are not adjacent, so \(d(x,y)=2\).

Finally, assume that \(S\cap T\neq\emptyset\) and \(S\cup T=[m]\). We first show that \(d(x,y)\neq 2\). If there were a common neighbor \(z\in X_U\), then \(U\) would have to be disjoint from both \(S\) and \(T\). Hence \(U\subseteq [m]\setminus (S\cup T)=\emptyset,\) contradicting the fact that \(U\) is nonempty. Thus \(d(x,y)\geq 3\).

To show that \(d(x,y)\leq 3\), note that \(S\) and \(T\) are proper subsets whose union is all of \([m]\). Therefore, both differences \(T\setminus S\) and \(S\setminus T\) are nonempty. Choose \(a\in T\setminus S\) and \(b\in S\setminus T\). Take any \(u\in X_{{a}}\) and \(v\in X_{{b}}\). Then \({a}\cap S=\emptyset\), so \(x\sim u\). Also \({a}\cap{b}=\emptyset\), so \(u\sim v\), and finally \({b}\cap T=\emptyset\), so \(v\sim y\). Thus \(x-u-v-y\) is a path of length \(3\), and therefore \(d(x,y)=3\). 0◻

The next corollary gives the diameter of the graph.

When \(m=2\), the only nonempty proper subsets of \([2]\) are \({1}\) and \({2}\), so \(G_2\) is the complete bipartite graph with bipartition \(X_{{1}}\cup X_{{2}}\), and its diameter is \(2\).

For \(m\geq 3\), Theorem 12 shows that every pair of vertices is at distance at most \(3\), so \(\operatorname{diam}(G_2)\leq 3\). To see that the value \(3\) occurs, choose \(S=[m]\setminus\{1\},\) and \(T=[m]\setminus\{m\}.\) Then \(S\) and \(T\) are nonempty proper subsets, \(S\cap T\neq\emptyset\), and \(S\cup T=[m]\). By Theorem 12, any \(x\in X_S\) and \(y\in X_T\) satisfy \(d(x,y)=3\). Hence, \(\operatorname{diam}(G_2)=3\). 0◻

The next theorem identifies the center of the graph for \(m\geq 3\).

Let \(x\in X_{{i}}\) for some \(i\in [m]\). For any vertex \(y\in X_T\), if \(i\notin T\), then \({i}\cap T=\emptyset\), so \(x\) and \(y\) are adjacent by Theorem 7. If \(i\in T\), then \({i}\cap T\neq\emptyset\). As \(T\) is proper and \(m\geq 3\), we cannot have \({i}\cup T=[m]\), indeed, that would force \(T=[m]\). Therefore the second case of Theorem 12 applies, and \(d(x,y)=2\). Hence every vertex in a singleton class has eccentricity at most \(2\).

Such a vertex is not adjacent to another vertex in the same class by Corollary 3, so its eccentricity is exactly \(2\). Thus every vertex in \(\mathcal{C}\) is central and the radius is at most \(2\). Since the graph is not complete, the radius cannot be \(1\), so the radius is exactly \(2\).

Now let \(x\in X_S\) with \(|S|\geq 2\). Choose \(a\in S\) and define \[T=[m]\setminus\{a\}.\] Because \(|S|\geq 2\), the set \(S\cap T=S\setminus\{a\}\) is nonempty, and clearly \(S\cup T=[m]\). By Theorem 12, every \(y\in X_T\) satisfies \(d(x,y)=3\). Hence the eccentricity of \(x\) is at least \(3\), so \(x\) is not central. Therefore the center is exactly \(\mathcal{C}\). 0◻

The next corollary gives a uniform routing bound after arbitrary deletions below the connectivity threshold.

Connectivity follows from Theorem 11. By Lemma 2, there exists a surviving vertex \(u\in X_{{m}}\setminus W\). The proof of Theorem 11, through Lemmas 3 and 4, shows that every surviving vertex lies at distance at most \(2\) from \(u\) in \(G_2-W\). Therefore, any two surviving vertices are at distance at most \(4\) from one another. 0◻

Neither the exact distance formula nor the resulting diameter and center descriptions are explicit in the existing literature. They emerge naturally from the support-set description and further demonstrate that the open problem on connectivity is part of a broader metric simplification available only in the squarefree model.

Figure 5 shows the shortest-path patterns from Theorem 12. The support-set relation alone determines whether the geodesic length is \(1\), \(2\), or \(3\).

7 Computational realization, algorithm, and comparative data↩︎

The exact formula for \(\kappa(G_2)\) immediately leads to an efficient computation procedure and reveals an unexpected arithmetic asymmetry, once the prime factors are ordered, the size of the minimum cut depends only on the first \(m-1\) primes.

The next proposition rewrites the exact formula of \(\kappa(G_2)\) in Euler form.

The next corollary shows that changing only the largest prime does not change the connectivity value.

Apply Theorem 11 to \(n'\). As the ordered prime list for \(n'\) is exactly \(p_1,\dots,p_{m-1},q\), the product defining \(\kappa\big(G_2(n')\big)\) involves only the first \(m-1\) primes. 0◻

The following algorithm computes \(\kappa(G_2)\) directly from the ordered prime factors.

The following theorem validates Algorithm 6.

If \(m=1\), then \(n\) is prime, every nonzero element is a unit, and \(G_2\) is empty. So, returning \(0\) is correct. If \(m=2\), Theorem 11 implies \(\kappa(G_2)=p_1-1,\) so the second branch is correct. If \(m\geq 3\), Theorem 11 yields \[\kappa(G_2)=\prod_{i=1}^{m-1}(p_i-1),\] which is exactly the value accumulated in the loop. Hence, every branch returns the correct value. 0◻

The next proposition records the computational cost of the algorithm after factorization is known.

For \(m\geq 3\), the loop executes exactly once for each of the first \(m-1\) prime factors, and each iteration performs one multiplication. The cases \(m=1\) and \(m=2\) are constant-time branches. Therefore, the arithmetic cost is linear in the number of prime factors. 0◻

The next corollary describes how the connectivity changes when a new largest prime factor is appended.

Applying Theorem 11 to \(nq\) gives the required identity \[\kappa\big(G_2(nq)\big)=\prod_{i=1}^{m}(p_i-1)=(p_m-1)\prod_{i=1}^{m-1}(p_i-1)=(p_m-1)\kappa\big(G_2(n)\big).\] 0◻

The earlier literature provides structural and spectral decompositions of \(\Gamma(\mathbb{Z}_n)\), but not a direct computation rule for \(\kappa(G_2)\). Theorem 15 shows that once the squarefree factorization is available, the exact connectivity can be read off with linear complexity and no graph construction at all.

Figure 7 shows the flowchart of Algorithm 6. The graph-theoretic computation is reduced to a short arithmetic product once the squarefree prime factorization is available.

8 Conclusion and future work↩︎

We have given a complete solution to Problem 7.2 of Banerjee [16]. For the squarefree modulus \(n=p_1p_2\cdots p_m,\) with \(2\leq p_1<\cdots<p_m,\) the induced subgraph \(G_2\) of the comaximal graph \(\Gamma(\mathbb{Z}_n)\) on the nonzero nonunits satisfies \[\kappa(G_2)=\prod_{i=1}^{m-1}(p_i-1)=\frac{\phi(n)}{p_m-1}.\] The proof is based on a support-set model obtained from the Chinese remainder theorem. In this model, vertices are indexed by nonempty proper subsets of \([m]\), adjacency becomes set disjointness, and \(G_2\) is a weighted blow-up of a disjointness graph. This viewpoint also yields explicit class sizes, degree formulas, the unique minimum-degree layer, a transparent minimum separator, maximal connectivity, the exact edge connectivity, and a metric description including the diameter and center.

The main limitation of the paper is that the argument is tailored to the squarefree case. Once repeated prime powers are allowed, coordinates no longer reduce to simple zero versus nonzero choices, and the disjointness model must be replaced by a more delicate multilevel description. That nonsquarefree situation seems genuinely harder and cannot be treated by a superficial modification of the present proof details of results. A second limitation is that we determined the exact value of the connectivity but did not classify all minimum vertex cuts. SO, we leave the following two problems

Declarations↩︎

Data Availability: There is no data associated with this article.

Funding: The authors did not receive support from any organization for the submitted work.

Conflict of interest: The authors have no competing interests to declare that are relevant to the content of this article.

Note: I welcome any comments and suggestions regarding this article; please feel free to contact me at bilalahmadrr@gmail.com.

References↩︎