Let \(G\) be a loopless connected graph. A graph \(G\) is reduced if it contains no collapsible subgraph. Catlin (posted by Chen and Lai [9]) conjectured that every connected reduced graph is either 2-colorable or 3-colorable. A weaker conjecture states that the independence number of a connected reduced graph \(G\) is at least one-third of its number of vertices. In this paper, we establish a lower bound on the independence number in reduced graphs. As an application, we examine the independence number conjecture for reduced graphs with a given upper bound on the number of vertices. Also, we investigate the chromatic number of reduced planar graphs under given conditions.
In this paper, all graphs are assumed to be finite and loopless. Undefined terms and notations follow [1]. Let \(O(G)\) be the set of all odd-degree vertices in a graph \(G\). A graph \(G\) is called collapsible if, for any vertex subset \(R\) of even cardinality, there exists a spanning subgraph \(S_R\) such that \(O(S_R)=R\). For an edge subset \(T\), the contraction \(G/T\) is the graph obtained by removing each edge in \(T\), merging its two incident vertices into a single vertex and deleting the resulting loops. In [3], Catlin introduced the reduction method and showed that every graph \(G\) has a unique collection of maximal collapsible subgraphs, denoted as \(H_1, …, H_c\). Then the reduction of graph \(G\) is the graph \(G/(E(H_1)\cup … \cup E(H_c))\). A graph \(G\) is reduced if \(G\) does not have nontrivial collapsible subgraphs, meaning no further reduction can be made.
The concept of collapsible is closely related to several well-known topics, such as Hamiltonian graph, spanning trail, Supereulerian graph, and more. Over the past few decades, extensive research has been conducted on this subject (see [2, 3, 4, 5, 6, 7, 8, 10, 12, 15]). We denote the edge-connectivity of a graph \(G\) by \(\kappa'(G)\). Catlin ([3]) proved the following theorem which is an improvement of Jaeger’s theorem ([13]).
Theorem 1.1 (P.A. Catlin, Theorem 2 of [3]). Let \(G\) be a connected graph. Each condition below can imply the one that follows. That is, (i) implies (ii), (ii) implies (iii), and (iii) implies (iv).
(i) \(\kappa'(G)\ge 4\).
(ii) \(G\) has two edge-disjoint spanning trees.
(iii) \(G\) is collapsible.
(iv) \(G\) is supereulerian.
This result motivates an analysis of the collapsible property in graphs with lower edge-connectivity or in graphs that do not contain two edge-disjoint spanning trees. Let \(F(G)\) be the minimum number of extra edges that need to be added to graph \(G\) in order to have two edge-disjoint spanning trees in the resulting graph. We denote the minimum degree of a graph \(G\) by \(\delta(G)\), the complete graph with \(n\) vertices by \(K_n\), and the complete bipartite graph with one side consisting of 2 vertices and the other side consisting of \(t\) vertices (\(t\ge 1\)) by \(K_{2,t}\). If \(G\) does not contain \(H\) as a subgraph, then we say \(G\) is \(H\)-free. The following theorems related to reduced graphs have been proved.
Theorem 1.2. Let \(G\) be a connected reduced graph with \(n\) vertices and \(m\) edges.
(i) (P. A. Catlin, Theorem 7 of [2]) \(F(G)=2n-m-2\).
(ii) (P. A. Catlin, Theorem 8 of [3]) \(G\) is a simple \(K_3\)-free graph with \(\delta(G)\le 3\).
(iii) (P. A. Catlin, Corollary of [3]) For any subgraph \(H\) of \(G\), \(H\) is reduced.
(iv) (P. A. Catlin, Z. Han, H.-J. Lai, Theorem 1.3 of [5]) Either \(G\in \{K_1, K_2, K_{2,t}~|~t\ge 1\}\) or \(F(G)\ge 3\).
The chromatic number of a graph \(G\) is the smallest number of colors needed to color the vertices so that no two adjacent vertices share the same color. An independent set is a vertex subset such that no two vertices in the set are adjacent. And the independence number of a graph \(G\) is the maximum size of an independent set in \(G\). Let \(\chi (G)\) and \(\alpha(G)\) be the chromatic number and independence number of a graph \(G\), respectively. Catlin proposed a conjecture concerning the coloring of reduced graphs (posted by Chen and Lai in [9]).
Conjecture 1.3 (Chen and Lai, Conjecture 8.10 of [9]). Let \(G\) be a connected reduced graph. Then \(\chi (G)=2\) or \(3\).
By Conjecture 1.3, there are at least \(|V(G)|/3\) vertices that share the same color in a connected reduced graph \(G\). By definitions, the set of vertices with the same color is an independent set, so a related conjecture of the independence number can be announced at the same time, which is a weaker version of Conjecture 1.3.
Conjecture 1.4. Let \(G\) be a connected reduced graph with \(n\) vertices. Then \(\alpha (G)\ge \frac{n}{3}\).
Both conjectures remain open in the general case. Chen ([8]) proved the following.
Theorem 1.5 (Chen, Theorem 1 of [8]). Let \(G\) be a connected reduced graph with \(n\) vertices. Then \[\frac{\delta(G)\alpha(G)+4}{2}\le n\le\left\{ \begin{array}{ll} 5, & \mbox{if $\alpha(G)=2$},\\ 8, & \mbox{if $\alpha(G)=3$},\\ 4\alpha(G)-5, & \mbox{if $\alpha(G)\ge 4$}. \end{array} \right.\]
In this paper, we improve the lower bound of \(\alpha(G)\) presented in Theorem 1.5 and establish a new lower bound of \(\alpha(G)\) in the general reduced graph. Additionally, we partially prove Conjecture 1.4 under the assumption of an upper bound on the number of vertices. We also explore the chromatic number of reduced planar graphs with a given \(F(G)\).
First, we aim to establish a lower bound for \(\alpha(G)\). In [17], Shearer introduced a function \(f(d)=(d\ln d -d+1)/(d-1)^2\) with \(f(0)=1\) and \(f(1)=1/2\), where \(d\) is the average degree of a graph \(G\), and proved the following result for \(K_3\)-free graphs.
Theorem 2.1 (Shearer, Theorem 1 of [17]). Let \(G\) be a \(K_3\)-free graph with \(n\) vertices and average degree \(d\). Then \(\alpha(G)\ge n*f(d)\).
Our first goal is to extend Theorem 2.1 to general reduced graphs. To achieve this, we first analyze the properties of \(f(x)\).
Lemma 2.2. \(f(x)\) is decreasing when \(x>1\).
Proof. Since \(f(x)=(x\ln x -x+1)/(x-1)^2\), we can get \[\begin{aligned} f'(x) &= \frac{(\ln x+1-1)(x-1)^2-(x\ln x-x+1)2(x-1)}{(x-1)^4}\\ &= \frac{-x\ln x-\ln x+2x-2}{(x-1)^3}. \end{aligned}\]
Let \(g(x)=-x\ln x-\ln x+2x-2\). Then \(g'(x)=1-\ln x-\frac{1}{x}\) and \(g''(x)=-\frac{1}{x}+\frac{1}{x^2}\). Since \(g''(x)<0\) when \(x>1\), \(g'(x)\) is decreasing, which means \(g'(x)<g'(1)=0\). And then we can get \(g(x)\) is decreasing, which means \(g(x)<g(1)=0\). It is known \(f'(x)=\frac{g(x)}{(x-1)^3}\), so \(f'(x)<\frac{g(1)}{(x-1)^3}=0\), for any \(x>1\). Therefore, we prove that \(f(x)\) is decreasing when \(x>1\). ◻
Theorem 2.3. Let \(G\) be a connected reduced graph with \(n\) vertices. Then \(\alpha(G)\ge n*f(4-\frac{10}{n})\) when \(n\ge 3\).
Proof. Since \(n\ge 3\), by Theorem 1.2(iv), \(G\cong K_{2,t}\) \((t\ge 1)\) or \(F(G)\ge 3\).
Case 1. \(G\cong K_{2,t}\).
If \(n=3\), then \(\alpha(G)=2>3f(4-\frac{10}{3})\). If \(n\ge 4\), then \(\alpha(G)=t\ge n/2>n*f(\frac{3}{2})\). By Lemma 2.2, \(\alpha(G)>n*f(\frac{3}{2})\ge n*f(4-\frac{10}{n})\). The case is proved.
Case 2. \(F(G)\ge 3\).
By Theorem 1.2(i), \(2n-m-2\ge 3\), which means \(2m\le 4n-10\). Suppose \(d\) is the average degree of graph \(G\). Then \(d\le 4-\frac{10}{n}\). By Theorem 2.1 and Lemma 2.2, we have \(\alpha(G)\ge n*f(d)\ge n*f(4-\frac{10}{n})\). The case is proved. ◻
We can immediately get the following corollaries because \(\alpha(G)\) should be an integer.
Corollary 2.4. Let \(G\) be a connected reduced graph with \(n\) vertices and \(n\ge 3\). Then \[\alpha(G)\ge \left\lceil\frac{(4n-10)\ln(4-\frac{10}{n})-3n+10}{(3-\frac{10}{n})^2}\right\rceil.\]
Corollary 2.5. Let \(G\) be a connected reduced graph with \(n\) vertices. Then \(\alpha(G)>\frac{4\ln 4-3}{9}n\). Moreover, for any \(c>0\), there exists an integer \(N(c)\) such that for any reduced graph \(G\) with order \(n\ge N(c)\), \(\alpha (G)>\frac{n}{4}+c\).
Proof. If \(n\le 3\), then, by Theorem 1.2(ii) and (iv), \(G\in \{K_1, K_2, K_{2,1}\}\). So, we have \(\alpha (G)\ge \frac{n}{2}>\frac{4\ln 4-3}{9}n\). Suppose \(n\ge 4\). Since \(1<4-\frac{10}{n}<4\), by Lemma 2.2 and Theorem 2.3, \(\alpha(G)\ge n*f(4-\frac{10}{n})>f(4)n=\frac{4\ln 4-3}{9}n\). For any \(c>0\), if \(n\ge N(c)=\frac{36c}{16\ln 4-21}\), then \(\alpha(G)>\frac{4\ln 4-3}{9}n=\frac{n}{4}+\frac{16\ln 4-21}{36}n\ge \frac{n}{4}+c\). ◻
According to Theorem 1.5, \(\alpha (G)\) has a lower bound of \(\frac{n+5}{4}\). Corollary 2.5 improves the coefficient of \(n\) in the lower bound to \(\frac{4\ln 4-3}{9}\), but does not achieve the coefficient of \(n\), which is \(\frac{1}{3}\), in Conjecture 1.4. Therefore, we make a further investigation by considering cases where the number of vertices is restricted. For clarity, let \(d_G(u)\) represent the degree of vertex \(u\) in the graph \(G\), and \(N(u)\) represent the set of vertices adjacent to \(u\) in graph \(G\). Define \(N[u]\) as the closed neighborhood of \(u\), given by \(N(u)\cup\{u\}\). If \(X\) is a vertex subset, we set \(N(X)=\bigcup_{x\in X}N(x)-X\) and \(N[X]=X\cup N(X)\). Furthermore, let \(G-X\) be the graph obtained from \(G\) by removing all vertices in \(X\) along with their incident edges. Finally, we define \(\partial (X)\) as the set of edges with one endpoint in \(X\) and the other endpoint outside of \(X\) in graph \(G\).
Next, we try to partially prove Conjecture 1.4 with a given upper bound on the number of vertices. The following proposition can be got from the contrapositive of upper bound part of Theorem 1.5 when \(\alpha(G)=3, 4, 5\).
Proposition 2.6. Let \(G\) be a reduced graph with \(n\) vertices.
(i) If \(n\ge 9\), then \(\alpha(G)\ge 4\).
(ii) If \(n\ge 12\), then \(\alpha(G)\ge 5\).
(iii) If \(n\ge 16\), then \(\alpha(G)\ge 6\).
Proof. We first prove condition (i). Assume \(\alpha(G)\le 3\). By Theorem 1.5, we have \(n\le 8\). It contradicts \(n\ge 9\). So, we have \(\alpha(G)\ge 4\) if \(n\ge 9\). Similar proofs can be applied to prove conditions (ii) and (iii). ◻
Theorem 2.7. Let \(G\) be a connected reduced graph with \(n\) vertices and \(3\le n\le 21\). Then \(\alpha(G)\ge \frac{n}{3}\).
Proof. When \(3\le n\le 21\) and \(n\neq 16, 19\), the result can be got from Corollary 2.4, because \[\alpha(G)\ge \left\lceil\frac{(4n-10)\ln(4-\frac{10}{n})-3n+10}{(3-\frac{10}{n})^2}\right\rceil\ge \frac{n}{3}.\]
When \(n=16\), it can be proved by Proposition 2.6(iii). So, our analysis can be restricted to the case when \(n=19\). In the following, we try to prove \(\alpha(G)\ge 7\).
By Theorem 1.2(ii), we have \(\delta(G)\le 3\). Let \(d_G(u)=\delta(G)\) and \(G'=G-N[u]\). By Theorem 1.2(iii), \(G'\) is reduced. Moreover, by Theorem 1.2(ii), \(\delta(G')\le 3\). If \(d_G(u)\le 2\), then \(|V(G')|\ge 16\). By Proposition 2.6(iii), \(\alpha(G')\ge 6\). Because \(u\) is only adjacent to the vertices in \(N(u)\), which is not in \(G'\), the union between the maximum independent set of \(G'\) and vertex \(u\) is an independent set in \(G\). Then we have \(\alpha(G)\ge 7\). In the following, we only need to prove the case when \(\delta(G)=3\).
Claim 1. If there exists \(p\in V(G)\) such that \(d_G(p)=3\) and \(\delta(G-N[p])\le 2\), then \(\alpha(G)\ge 7\).
Let \(d_{G-N[p]}(q)=\delta(G-N[p])\le 2\) and \(G^*=G-(N[p]\cup N[q])\). By Theorem 1.2(iii), \(G^*\) is reduced. Because \(d_G(p)=3\) and \(d_{G-N[p]}(q)\le 2\), \(|V(G^*)|\ge 12\). By Proposition 2.6(ii), \(\alpha(G^*)\ge 5\). Because \(q\) is only adjacent to the vertices in \(N(q)\), and \(N[q]\) is not in \(G^*\), the union between the maximum independent set of \(G^*\) and \(\{p, q\}\) is an independent set in \(G\). So, \(\alpha(G)\ge 7\). This proves Claim 1.
Let \(d_{G'}(v)=\delta(G')\), by Claim 1, we only need to prove the case when \(d_{G'}(v)=3\).
Case 1. \(|\partial (N[u])|\neq 7\).
If \(|\partial (N[u])|\ge 8\), since \(\delta(G')=3\) and \(|V(G')|=15\), then \(|E(G')|\ge \frac{3*15}{2}\), which means \(|E(G')|\ge 23\). So, we have \(|E(G)|=|E(G')|+|\partial (N[u])|+d_G(u)\ge 23+8+3=34\). It implies \(F(G)\le 2\). But \(G\ncong K_{2, 17}\) because \(\delta(G)=3\). So, by Theorem 1.2(iv), \(G\) is not reduced. If \(|\partial (N[u])|\le 6\), then it follows that \(|N(N[u])|\le 6\), which in turn implies \(|V(G'-N(N[u]))|\ge 9\). By Proposition 2.6(i), \(\alpha(G'-N(N[u]))\ge 4\). By Theorem 1.2(ii), \(G\) is \(K_3\)-free, so \(N(u)\) is a 3-independent set in \(G\). And the union between the maximum independent set of \(G'-N(N[u])\) and \(N(u)\) is an independent set in \(G\). So, \(\alpha(G)\ge 7\).
Case 2. \(|\partial (N[u])|=7\).
If \(|N(N[u])|\ge 8\), then \(|\partial (N[u])|\ge 8\), a contradiction. If \(|N(N[u])|\le 6\), based on the same proof as in Case 1, then we can get either \(G\) is not reduced or \(\alpha(G)\ge 7\). So, we only need to prove the case when \(|N(N[u])|=7\). Suppose \(N(u)=\{u_1, u_2, u_3\}\) and \(d_G(u_1)\le d_G(u_2)\le d_G(u_3)\). Since \(|N(N[u])|=7=|\partial (N[u])|\) and \(\delta(G)=3\), we have \(d_G(u_1)=3=d_G(u_2)\). Suppose \(N(u_1)=\{u, v_1, v_2\}\). Because \(d_G(u_2)=3\) and \(\delta(G')=3\), we have \(\delta(G-N[u_1])=2\). By Claim 1, \(\alpha(G)\ge 7\). This completes the proof. ◻
In this section, we discuss Conjecture 1.3 in the context of reduced planar graphs. Grötzsch [11] proved that every \(K_3\)-free planar graph is 3-colorable. By Theorem 1.2(ii), Conjecture 1.3 holds for reduced planar graphs. Therefore, our focus shifts to identify conditions under which a reduced planar graph is 2-colorable.
Let \(s_i\ge 1~(i=1, 2, 3)\) be integers. We define \(K_4(s_1, s_2, s_3)\), \(T(s_1, s_2)\), \(C_3(s_1, s_2)\), \(S(s_1, s_2)\), and \(K_{2,3}(s_1, s_2)\) as the graphs shown in Figure 1. Each hollow circle in Figure 1, labeled \(s_i\), with two attached black dots represents a \(K_{2,s_i}\). Each of the \(s_i\) vertices within the hollow circle is connected to both black dots by two edges.
Let \(\mathcal{F}_1=\{K_4(s_1, s_2, s_3), T(s_1, s_2), C_3(s_1, s_2), S(s_1, s_2), K_{2,3}(s_1, s_2)~|~s_i\ge 1~(i=1,2,3)\}\) and \(\mathcal{F}=\mathcal{F}_1\cup \{K_{2,t'}~|~t'\ge 2\}\). In [14], Lai et al. proved the following theorems.
Theorem 3.1. Let \(G\) be a planar graph with \(F(G)\le 3\).
(i) (H.-J. Lai, et al., Theorem 1.2 of [14]) If \(\kappa'(G)\ge 3\), then \(G\) is collapsible.
(ii) (H.-J. Lai, et al., Theorem 1.3 of [14]) If \(\kappa'(G)\ge 2\), then either \(G\) is collapsible or the reduction of \(G\) is a graph in \(\mathcal{F}\).
Before applying the theorem to Conjecture 1.3, we first analyze the structure of graphs in \(\mathcal{F}\). Let \(C_n\) be the cycle graph with \(n\) vertices.
Proposition 3.2. If \(G\in \mathcal{F}_1\), then \(F(G)=3\). Also, each of the following holds.
(i) \(\chi (K_4(s_1, s_2, s_3))=2\) and \(\alpha(K_4(s_1, s_2, s_3))=s_1+s_2+s_3+1\).
(ii) \(\chi (T(s_1, s_2))=2\) and \(\alpha(T(s_1, s_2))=s_1+s_2+1\).
(iii) \(\chi (C_3(s_1, s_2))=3\) and \(\alpha(C_3(s_1, s_2))=s_1+s_2\).
(iv) \(\chi (S(s_1, s_2))=2\) and \(\alpha(S(s_1, s_2))=\max\{\max\{s_1,s_2\}+2, s_1+s_2\}\).
(v) \(\chi (K_{2,3}(s_1, s_2))=3\) and \(\alpha(K_{2,3}(s_1, s_2))=s_1+s_2+1\).
Proof. Since \(\mathcal{F}_1\cap\{K_1, K_2, K_{2,t}~|~t\ge 1\}=\emptyset\), by Theorem 1.2 (iv) and Theorem 3.1 (ii), \(F(G)=3\). Recall that the set of vertices with the same color is an independent set in the following proof.
Case 1. In \(K_4(s_1, s_2, s_3)\), the vertices in \(s_1\), \(s_2\), \(s_3\), and vertex \(o_4\) can share a color. And it is the biggest set of vertices with one color. The rest of the vertices share another color. So, \(\chi (K_4(s_1, s_2, s_3))=2\) and \(\alpha(K_4(s_1, s_2, s_3))=s_1+s_2+s_3+1\).
Case 2. In \(T(s_1, s_2)\), the vertices in \(s_1\), \(s_2\), and vertex \(o_2\) can share a color. And it is the biggest set of vertices with one color. The rest of the vertices share another color. So, \(\chi (T(s_1, s_2))=2\) and \(\alpha(T(s_1, s_2))=s_1+s_2+1\).
Case 3. Because \(C_3(s_1, s_2)\) contains \(C_5\) as a subgraph, we have \(\chi (C_3(s_1, s_2))\ge 3\). The vertices in \(s_1\) and \(s_2\) can share the first color. And it is the biggest set of vertices with one color. The vertex \(o_1\) can share the second color with one of \(o_2\) and \(o_3\), and the last vertex needs to be colored with the third color. So, \(\chi (C_3(s_1, s_2))=3\) and \(\alpha(C_3(s_1, s_2))=s_1+s_2\).
Case 4. In \(S(s_1, s_2)\), the vertices in \(s_1\) and vertices \(o_2\), \(o_3\) can share a color. The rest of the vertices share another color. So, \(\chi (S(s_1, s_2))=2\). If \(s_1\ge 2\) and \(s_2\ge 2\), then the vertices in \(s_1\) and \(s_2\) can form the biggest independent set, which implies \(\alpha(S(s_1, s_2))=s_1+s_2\). Otherwise, without loss of generality, suppose \(s_1=1\). Then the vertices in \(s_2\) and vertices \(o_1\), \(o_4\) can form the biggest independent set, which implies \(\alpha(S(s_1, s_2))=\max\{s_1,s_2\}+2\). Therefore, in the general case, \(\alpha(S(s_1, s_2))=\max\{\max\{s_1,s_2\}+2, s_1+s_2\}\).
Case 5. Because \(K_{2,3}(s_1, s_2)\) contains \(C_5\) as a subgraph, we have \(\chi (K_{2,3}(s_1, s_2))\ge 3\). The vertices in \(s_1\), \(s_2\), and vertex \(o_1\) can share the first color. And it is the biggest set of vertices with one color. Vertices \(o_2\), \(o_3\), and \(o_4\) can share the second color. And \(o_5\) needs to be colored with the third color. So, \(\chi (K_{2,3}(s_1, s_2))=3\) and \(\alpha(K_{2,3}(s_1, s_2))=s_1+s_2+1\). ◻
Corollary 3.3. Let \(G\) be a reduced planar graph without \(C_5\) as a subgraph. If any of the following holds, then \(\chi(G)=2\).
(i) \(F(G)\le 3\).
(ii) \(F(G)=4\) and \(G\) has a cut edge.
Proof. Since \(G\) does not have \(C_5\) as a subgraph, \(G\) does not contain \(C_3(s_1, s_2)\) or \(K_{2,3}(s_1, s_2)\) as a subgraph. If \(F(G)\le 3\) and \(\kappa'(G)\ge 2\), by Theorem 3.1(ii) and Proposition 3.2, then \(\chi(G)=2\). So, we only need to prove the case when \(\kappa'(G)=1\) in both conditions. Suppose \(e\) is a cut edge. \(H_1\) and \(H_2\) are two connected components in \(G-e\). And, by Theorem 1.2 (iii), \(H_1\) and \(H_2\) are reduced. If \(F(G)\le 3\), by Theorem 1.2 (i), then \(F(H_1)+F(H_2)\le 2\). By Theorem 1.2 (iv), \(H_1, H_2\in \{K_1, K_2, K_{2,t}~|~t\ge 1\}\). These implies \(\chi(G)=2\), which proves condition (i). If \(F(G)=4\), then \(F(H_1)+F(H_2)=3\). Without loss of generality, suppose \(F(H_1)\le F(H_2)\). We have \(F(H_1)\le 1\), which means \(H_1\in \{K_1, K_2\}\) by Theorem 1.2 (iv). We know that \(H_2\) does not contain \(C_5\) as a subgraph. If \(F(H_2)\le 3\), then \(\chi(H_2)=2\) by condition (i), which we just proved. So, \(\chi(G)=2\). These prove condition (ii). ◻
At last, we extend Corollary 3.3 to the case of the independence number. By Proposition 3.2 (iii) and (v), if \(s_1+s_2\ge 3\), then \(\alpha(C_3(s_1, s_2))\ge \frac{n}{2}\) and \(\alpha(K_{2,3}(s_1, s_2))\ge \frac{n}{2}\). Combining these with Corollary 3.3 (i), we conclude that \(\alpha(G)\ge \frac{n}{2}\) for any reduced planar graph \(G\) with \(F(G)\le 3\) and \(G\notin \{C_3(1, 1), K_{2,3}(1, 1)\}\).
Proposition 3.4. If \(G\) is a connected reduced planar graph with \(n\) vertices and \(F(G)\le 3\). If \(G\notin \{C_3(1, 1), K_{2,3}(1, 1)\}\), then \(\alpha(G)\ge \frac{n}{2}\).
Moreover, \(\alpha(C_n)=\frac{n}{2}\) when \(n\) is an even number with \(n\ge 4\). This implies the existence of infinitely many reduced planar graphs whose independence number equals to \(\frac{n}{2}\).
The author would like to thank Dr. Hong-Jian Lai for introducing the concept of collapsible graph and proposing the research problem.