Menu
In this paper, we consider a degree sum condition sufficient to imply the existence of \(k\) vertex-disjoint chorded cycles in a graph \(G\).
Let \(\sigma_4(G)\) be the minimum degree sum of four independent vertices of \(G\).
We prove that if \(G\) is a graph of order at least \(11k+7\) and \(\sigma_4(G)\ge 12k-3\) with \(k\ge 1\),
then \(G\) contains \(k\) vertex-disjoint chorded cycles.
We also show that the degree sum condition on \(\sigma_4(G)\) is sharp.
The study of cycles in graphs is a rich and an important area. One question of particular interest is to find conditions that guarantee the existence of \(k\) vertex-disjoint cycles. Corrádi and Hajnal [1] first considered a minimum degree condition to imply a graph must contain \(k\) vertex-disjoint cycles, proving that if \(|G|\ge 3k\) and the minimum degree \(\delta(G) \ge 2k\), then \(G\) contains \(k\) vertex-disjoint cycles. For an integer \(t\ge 1\), let \[\sigma_t (G)=\mbox{min}\left\{\sum_{v\in X}d_G(v)\, : \begin{array}{c} X\ {\rm is\ an\ independent\ vertex\ set} {\rm of}\ G\ {\rm with}\ |X|=t. \end{array} \right\},\] and \(\sigma_t (G)=\infty\) when the independence number \(\alpha(G)<t\). Enomoto [2] and Wang [3] independently extended the Corrádi and Hajnal result, requiring a weaker condition on the minimum degree sum of any two non-adjacent vertices. They proved that if \(|G|\ge 3k\) and \(\sigma_2(G)\ge 4k-1\), then \(G\) contains \(k\) vertex-disjoint cycles. In 2006, Fujita et al. [4] proved that if \(|G| \ge 3k+2\) and \(\sigma_3 (G) \ge 6k-2\), then \(G\) contains \(k\) vertex-disjoint cycles, and in [5], this result was extended to \(\sigma_4(G)\ge 8k-3\).
An extension of the study of vertex-disjoint cycles is that of vertex-disjoint chorded cycles. A chord of a cycle is an edge between two non-adjacent vertices of the cycle. We say a cycle is chorded if it contains at least one chord. In 2008, Finkel proved the following result on the existence of \(k\) vertex-disjoint chorded cycles.
Theorem 1. \((\)Finkel [6]\()\) Let \(k\ge 1\) be an integer. If \(G\) is a graph of order at least \(4k\) and \(\delta(G) \geq 3k\), then \(G\) contains \(k\) vertex-disjoint chorded cycles.
In 2010, Chiba et al. proved Theorem 2. Since \(\sigma_2(G) \geq 2\delta(G)\), Theorem 2 is stronger than Theorem 1.
Theorem 2 (Chiba, Fujita, Gao, Li [7]). Let \(k\ge 1\) be an integer. If \(G\) is a graph of order at least 4k and \(\sigma_2(G)\ge 6k-1\), then \(G\) contains \(k\) vertex-disjoint chorded cycles.
Recently, Theorem 2 was extended as follows. Since \(\sigma_3(G) \geq 3\sigma_2(G)/2\), when the order of \(G\) is sufficiently large, Theorem 3 is stronger than Theorem 2.
Theorem 3 (Gould, Hirohata, Rorabaugh [8]). Let \(k\ge 1\) be an integer. If \(G\) is a graph of order at least \(8k+5\) and \(\sigma_3(G) \geq 9k-2\), then \(G\) contains \(k\) vertex-disjoint chorded cycles.
Remark 1. We note if \(k=1\) in Theorem 3, then Theorem 3 holds under the condition that \(|G|\ge 7\).
In this paper, we consider a similar extension for chorded cycles, as, in [5], the existence of \(k\) vertex-disjoint cycles was proved under the condition \(\sigma_4(G)\). In particular, we first show the following.
Theorem 4. If \(G\) is a graph of order at least \(15\) and \(\sigma_4 (G) \ge 9\), then \(G\) contains a chorded cycle.
Remark 2. We consider the following graph \(G\) of order 14. (See Fig. 1.) Then \(G\) satisfies the \(\sigma_4(G)\) condition in Theorem 4. However, \(G\) does not contain a chorded cycle. Thus \(|G|\ge 15\) is necessary.
Theorem 5. Let \(k\ge 1\) be an integer. If \(G\) is a graph of order \(n \ge 11k+7\) and \(\sigma_4 (G) \ge 12k – 3\), then \(G\) contains \(k\) vertex-disjoint chorded cycles.
Remark 3. Theorem 5 is sharp with respect to the degree sum condition. Consider the complete bipartite graph \(G= K_{{3k-1}, {n-3k+1}}\), where large \(n=|G|\). Then \(\sigma_4(G)=4(3k-1)=12k-4\). However, \(G\) does not contain \(k\) vertex-disjoint chorded cycles, since any chorded cycle must contain at least three vertices from each partite set, in particular, from the \(3k-1\) partite set. Thus \(\sigma_4(G)\ge 12k-3\) is necessary.
For other related results on vertex-disjoint chorded cycles in graphs and bipartite graphs, we refer the reader to see [9-12].
Let \(G\) be a graph, \(H\) a subgraph of \(G\) and \(X \subseteq V(G)\). For \(u\in V(G)\), the set of neighbors of \(u\) in \(G\) is denoted by \(N_G(u)\), and we denote \(d_G(u)=|N_G(u)|\). For \(u\in V(G)\), we denote \(N_H(u)=N_G(u)\cap V(H)\) and \(d_H(u)=|N_H(u)|\). Also we denote \(d_H(X)=\sum_{u\in X} d_H(u)\). If \(H=G\), then \(d_G(X)=d_H(X)\). Furthermore, \(N_G(X)=\cup_{u\in X}N_G(u)\) and \(N_H(X)=N_G(X)\cap V(H)\). Let \(A, B\) be two vertex-disjoint subgraphs of \(G\). Then \(N_G(A)=N_G(V(A))\) and \(N_B(A)=N_G(A)\cap V(B)\). The subgraph of \(G\) induced by \(X\) is denoted by \(\langle X \rangle\). Let \(G-X=\langle V(G)-X\rangle\) and \(G-H=\langle V(G)-V(H)\rangle\). If \(X=\{x\}\), then we write \(G-x\) for \(G-X\). If there is no fear of confusion, then we use the same symbol for a graph and its vertex set. For two disjoint graphs \(G_1\) and \(G_2\), \(G_1\cup G_2\) denotes the union of \(G_1\) and \(G_2\). Let \(Q\) be a path or a cycle with a given orientation and \(x\in V(Q)\). Then \(x^+\) denotes the first successor of \(x\) on \(Q\) and \(x^-\) denotes the first predecessor of \(x\) on \(Q\). If \(x, y\in V(Q)\), then \(Q[x,y]\) denotes the path of \(Q\) from \(x\) to \(y\) (including \(x\) and \(y\)) in the given direction. The reverse sequence of \(Q[x,y]\) is denoted by \(Q^-[y,x]\). We also write \(Q(x,y]=Q[x^+,y]\), \(Q[x, y)=Q[x, y^-]\) and \(Q(x, y)=Q[x^+, y^-]\). If \(Q\) is a path (or a cycle), say \(Q = x_1,x_2, \ldots ,x_t (,x_1)\), then we assume an orientation of \(Q\) is given from \(x_1\) to \(x_t\) (if \(Q\) is a cycle, then the orientation is clockwise). If \(P\) is a path connecting \(x\) and \(y\) of \(V(G)\), then we denote the path \(P\) as \(P[x,y]\). If \(G\) is one vertex, that is, \(V(G)=\{x\}\), then we simply write \(x\) instead of \(G\). For an integer \(r\ge 1\) and two vertex-disjoint subgraphs \(A, B\) of \(G\), we denote by \((d_1, d_2, \ldots , d_r)\) a degree sequence from \(A\) to \(B\) such that \(d_B(v_i)\ge d_i\) and \(v_i\in V(A)\) for each \(1\le i\le r\). In this paper, since it is sufficient to consider the case of equality in the above inequality, when we write \((d_1, d_2, \ldots , d_r)\), we assume \(d_B(v_i)=d_i\) for each \(1\le i\le r\). For two disjoint \(X,Y\subseteq V(G)\), \(E(X,Y)\) denotes the set of edges of \(G\) connecting a vertex in \(X\) and a vertex in \(Y\). For a graph \(G\), \(comp(G)\) is the number of components of \(G\). A cycle of length \(\ell\) is called a \(\ell\)-cycle. For terminology and notation not defined here, see [13].
Definition 1. Suppose \(C_1, \dots , C_r\) are \(r\) vertex-disjoint chorded cycles in a graph \(G\). We say \(\{C_1, \dots , C_r\}\) is minimal if \(G\) does not contain \(r\) vertex-disjoint chorded cycles \(C'_1, \dots , C'_r\) such that \(|\cup_{i=1}^r V(C'_i)|<|\cup_{i=1}^r V(C_i)|\).
Definition 2. Let \(C=v_1,\dots,v_t,v_1\) be a cycle with chord \(v_iv_j\), \(i< j\). We say a chord \(vv' \neq v_iv_j\) is parallel to \(v_iv_j\) if either \(v,v' \in C[v_i,v_j]\) or \(v,v' \in C[v_j,v_i]\). Note if two distinct chords share an endpoint, then they are parallel. We say two distinct chords are crossing if they are not parallel.
Definition 3. Let \(u_iv_j\) and \(u_{\ell}v_m\) be two distinct edges between two vertex-disjoint paths \(P_1=u_1, \dots, u_s\) and \(P_2=v_1, \dots, v_t\). We say \(u_iv_j\) and \(u_{\ell}v_m\) are parallel if either \(i \le {\ell}\) and \(j \le m\), or \({\ell} \le i\) and \(m \le j\). Note if two distinct edges between \(P_1\) and \(P_2\) share an endpoint, then they are parallel. We say two distinct edges between two vertex-disjoint paths are crossing if they are not parallel.
Definition 4. Let \(v_iv_j\) and \(v_{\ell}v_m\) be two distinct edges between vertices of a path \(P=v_1, \dots, v_t\), with \(j \ge i+2\) and \(m \ge \ell+2\). We say \(v_iv_j\) and \(v_{\ell}v_m\) are nested if either \(i \le {\ell} < m \le j\) or \({\ell} \le i < j \le m\).
Definition 5. Let \(P=v_1,\dots, v_t\) be a path. We say a vertex \(v_i\) on \(P\) has a left edge if there exists an edge \(v_iv_j\) for some \(j < i-1\), that is not an edge of the path. We also say \(v_i\) has a right edge if there exists an edge \(v_iv_j\) for some \(j > i+1\), that is not an edge of the path.
The following lemmas will be needed.
Lemma 1 ([8]). Let \(r\ge 1\) be an integer, and let \(\mathscr{C} = \{C_1, \ldots, C_r\}\) be a minimal set of \(r\) vertex-disjoint chorded cycles in a graph \(G\). If \(|C_i|\ge 7\) for some \(1\le i\le r\), then \(C_i\) has at most two chords. Furthermore, if the \(C_i\) has two chords, then these chords must be crossing.
Lemma 2 ([8]). Let \(r\ge 1\) be an integer, and let \(\mathscr{C} = \{C_1,\ldots, C_r\}\) be a minimal set of \(r\) vertex-disjoint chorded cycles in a graph \(G\). Then \(d_{C_i}(x)\le 4\) for any \(1\le i\le r\) and any \(x\in V(G)-\cup_{i=1}^r V(C_i)\). Furthermore, for some \(C\in \mathscr{C}\) and some \(x\in V(G)-\cup_{i=1}^r V(C_i)\), if \(d_C(x) = 4\), then \(|C|=4\), and if \(d_C(x) = 3\), then \(|C|\le 6\).
Lemma 3 ([8]). Suppose there exist at least three mutually parallel edges or at least three mutually crossing edges connecting two vertex-disjoint paths \(P_1\) and \(P_2\). Then there exists a chorded cycle in \(\left<P_1 \cup P_2\right>\).
Lemma 4 ([8]). Suppose there exist at least five edges connecting two vertex-disjoint paths \(P_1\) and \(P_2\) with \(|P_1\cup P_2|\ge 7\). Then there exists a chorded cycle in \(\left<P_1 \cup P_2\right>\) not containing at least one vertex of \(\left<P_1\cup P_2\right>\).
Lemma 5 ([8]). Let \(P_1, P_2\) be two vertex-disjoint paths, and let \(u_1, u_2\) \((u_1\ne u_2)\) be in that order on \(P_1\). Suppose \(d_{P_2}(u_i)\ge 2\) for each \(i\in \{1,2\}\). Then there exists a chorded cycle in \(\left<P_1[u_1,u_2] \cup P_2\right>\).
Lemma 6 ([8]). Let \(H\) be a graph containing a path \(P=v_1, \dots,v_t\) \((t \ge 3)\), and not containing a chorded cycle. If \(v_1v_i\in E(H)\) for some \(i\ge 3\), then \(d_{P}(v_j)\le 3\) for any \(j \le i-1\) and in particular, \(d_{P}(v_{i-1})=2\). And if \(v_tv_i \in E(H)\) for some \(i \le t-2\), then \(d_{P}(v_{j})\le 3\) for any \(j\ge i+1\) and in particular, \(d_{P}(v_{i+1}) =2\).
Lemma 7 ([8]). Let \(H\) be a graph containing a path \(P=v_1, \dots, v_t\) \((t \ge 6)\), and not containing a chorded cycle. If \(d_{P}(v_1)=1\), then \(d_{P}(v_i)=2\) for some \(3\le i\le 5\), and if \(v_1v_3 \in E(H)\), then \(d_{P}(v_i)=2\) for some \(4\le i\le 6\).
Lemma 8 ([8]). Let \(H\) be a graph containing a path \(P=v_1, \dots, v_t\) \((t \ge 6)\), and not containing a chorded cycle. If \(d_{P}(v_t)=1\), then \(d_{P}(v_i)=2\) for some \(t-4\le i\le t-2\), and if \(v_{t}v_{t-2} \in E(H)\), then \(d_{P}(v_i)=2\) for some \(t-5\le i \le t-3\).
Lemma 9. Let \(H\) be a connected graph of order at least \(6\). Suppose \(H\) contains neither a chorded cycle nor a Hamiltonian path. Let \(H=\left< P_1 \cup P_2 \right>\), where \(P_1=u_1, \dots, u_s\) \((s\ge 5)\) is a longest path in \(H\) and \(P_2=v_1, \dots, v_t\) \((t\ge 1)\) is a longest path in \(H-P_1\). If \(u_i \in V(P_1)\) for some \(2 \le i \le s-3\) is adjacent to an endpoint \(v\) of \(P_2\) and \(u_j\in V(P_1)\) for some \(i+2 \le j \le s-1\) is adjacent to an endpoint \(v'\) of \(P_2\) \((\)possibly, \(v=v'\)\()\), then \(d_{H}(u_{\ell})=2\) for some \(\ell\in \{i+1,j-1\}\).
Proof. Let \(v, v'\) be as in the lemma, and we may assume \(v=v_1\) and \(v'=v_t\) (possibly, \(v=v'\)). Suppose \(d_{H}(u_{\ell})\ge 3\) for each \(\ell \in \{i+1,j-1\}\). If \(u_{i+1}\) has a left edge, say \(u_{i+1}u_h\) with \(h < i\), then \[P_1[u_h,u_i],v_1,P_2[v_1,v_t],u_j,P_1^{-}[u_j,u_{i+1}],u_h\] is a cycle with chord \(u_i u_{i+1}\), a contradiction. By symmetry, \(u_{j-1}\) does not have a right edge. Since \(u_iv_1, u_jv_t\in E(H)\), \(N_{P_2}(u_{\ell})=\emptyset\) for each \(\ell \in \{i+1,j-1\}\), otherwise, since consecutive vertices on \(P_1\) each have adjacencies on \(P_2\), there exists a longer path than \(P_1\) in \(H\), a contradiction. Note that even if \(v=v'\), \(N_{P_2}(u_{\ell})=\emptyset\) for each \(\ell \in \{i+1,j-1\}\). Since \(d_{H}(u_{\ell})\ge 3\) for each \(\ell \in \{i+1,j-1\}\), \(u_{i+1}\) has a right edge and \(u_{j-1}\) has a left edge. No vertex in \(P_1[u_i,u_j]\) can have an edge that does not lie on \(P_1\) to some other vertex in \(P_1[u_i,u_j]\), otherwise, this edge is a chord of the cycle \(P_1[u_i,u_j],v_t,P_2^{-}[v_t,v_1],u_i\). Thus we have edges \(u_{i+1}u_h\) with \(h > j\), and \(u_{j-1}u_{h'}\) with \(h' < i\). Then \[P_1[u_{h'},u_i],v_1,P_2[v_1,v_t],u_j,P_1[u_j,u_{h}],u_{i+1},P_1[u_{i+1},u_{j-1}],u_{h'}\] is a cycle with chord \(u_iu_{i+1}\) (and \(u_{j-1}u_j\)), a contradiction. Thus the lemma holds. ◻
Lemma 10 ([8]). Let \(H\) be a graph of order at least \(13\). Suppose \(H\) does not contain a chorded cycle. If \(H\) contains a Hamiltonian path, then there exists an independent set \(X\) of four vertices in \(H\) such that \(d_H(X) \le 8\).
Lemma 11 ([8]). Let \(H\) be a connected graph of order at least
\(4\). Suppose \(H\) contains neither a chorded cycle nor a
Hamiltonian path. Let \(P_1=u_1, \dots,
u_s\) \((s\ge 3)\) be a longest
path in \(H\), and let \(P_2=v_1, \dots, v_t\) \((t\ge 1)\) be a longest path in \(H-P_1\). Then the following statements
hold.
(i) \(N_{H-P_1}(u_i)=\emptyset\) for each \(i\in \{1,s\}\).
(ii) \(d_H(u_i)=d_{P_1}(u_i)\le
2\) for each \(i\in
\{1,s\}\).
(iii) \(N_{H-(P_1\cup
P_2)}(v_j)=\emptyset\) for each \(j\in
\{1,t\}\).
(iv) \(d_{P_2}(v_j)\le 2\)
for each \(j\in \{1,t\}\).
(v) \(d_{P_i}(z)\le 2\)
for each \(z\in V(H)-V(P_i)\) and each
\(i\in\{1,2\}\).
(vi) \(d_{P_1}(\{v_1,v_t\}) \le
3\) for each \(t\ge 2\).
Proofs of (v) and (vi). Note parts (i) to (iv) are from [8], hence we only prove parts (v) and (vi). Since \(H\) does not contain a chorded cycle, (v) holds. Suppose \(d_{P_1}(\{v_1,v_t\}) \ge 4\). By (v), \(d_{P_1}(v_j)=2\) for each \(j\in \{1,t\}\). Then, by Lemma 5, \(H\) has a chorded cycle, a contradiction. Thus (vi) holds. 0◻
Lemma 12. Let \(H\) be a connected graph of order at least \(15\). Suppose \(H\) contains neither a chorded cycle nor a Hamiltonian path. Let \(P_1=u_1, \dots, u_s\) \((s\ge 3)\) be a longest path in \(H\), and let \(P_2=v_1, \dots, v_t\) \((t\ge 1)\) be a longest path in \(H-P_1\) such that \(d_{P_1}(v_1) \le d_{P_1}(v_t)\). Then there exists an independent set \(X\) of four vertices in \(H\) such that \(\{u_1,u_s,v_1\}\subseteq X\) and \(d_{H}(X)\le 8\).
Remark 4. Let \(H\) be a graph of order 14 shown in Fig. 1 (Remark 2, Theorem 4), \(P_1=u_1, \dots, u_{11}\), and \(P_2=v_1, v_2, v_3\). Then \(H\) satisfies all the conditions except for the order in Lemma 12. However, the conclusion does not hold. Thus \(|H|\ge 15\) is necessary.
Proof. Suppose \(u_1u_s\in E(H)\). Since \(H\) is connected and \(V(H-P_1)\ne \emptyset\), there exists a longer path than \(P_1\), a contradiction. Thus \(u_1u_s\not\in E(H)\). Let \(R=H-(P_1\cup P_2)\). If \(t=1\), that is, \(v_1=v_t\), then \(d_{P_1}(v_1)\le 2\) by Lemma 11(v). If \(t\ge 2\), then \(d_{P_1}(\{v_1,v_t\})\le 3\) by Lemma 11(vi). Then \(d_{P_1}(v_1)\le 1\) by the assumption (\(d_{P_1}(v_1) \le d_{P_1}(v_t)\)), and \(d_{P_1}(v_t) \le 2\) by Lemma 11(v).
Claim 6. If \(|P_2| \le 3\), then \(H=\left< P_1 \cup P_2 \right>\).
Proof. Suppose \(H\ne \left< P_1 \cup P_2 \right>\). Now we prove the following two subclaims.
Subclaim 7. For any \(v\in V(P_2)\), \(N_R(v)=\emptyset\).
Proof. By Lemma 11(iii), \(N_R(v_j)=\emptyset\) for each \(j\in \{1,t\}\). If \(|P_2|\le 2\), then the subclaim holds. Thus we may assume \(|P_2|=3\). Suppose \(N_R(v')\ne \emptyset\) for some \(v'\in V(P_2)\). Then \(v'=v_2\). Let \(w_1\in N_R(v_2)\). If \(v_1v_3\in E(H)\), then the subclaim holds, otherwise, there exists a longer path than \(P_2\) in \(H-P_1\), a contradiction. Thus \(v_1v_3 \not\in E(H)\). Since \(d_{P_1}(v_1) \le 1\) and \(d_{P_1}(v_3)\le 2\), we have \(d_{H}(v_1)\le 2\) and \(d_{H}(v_3)\le 3\). Suppose a vertex on \(P_2\) has a neighbor \(w_1\) in \(R\). Then \(v_2w_1 \in E(H)\). Recall \(u_1u_s \not\in E(H)\), and note \(u_iv_j\not\in E(H)\) for any \(i\in \{1,s\}\) and any \(j\in \{1,3\}\) by Lemma 11(i). We also note \(d_{H}(u_i)\le 2\) for any \(i\in \{1,s\}\) by Lemma 11(ii). If \(d_{H}(\{v_1,v_3\}) \le 4\), then \(X=\{u_1,u_s,v_1,v_3\}\) is an independent set in \(H\) and \(d_{H}(X)\le 8\), and \(X\) is the desired set. Thus we may assume \(d_{H}(\{v_1,v_3\})=5\), that is, \(d_{H}(v_1)=2\) and \(d_{H}(v_3)=3\). Then \(d_{P_1}(v_1)=1\) and \(d_{P_1}(v_3)=2\). Recall \(w_1\in N_R(v_2)\). Clearly, \(N_R(w_1)=\emptyset\), otherwise, there exists a longer path than \(P_2\) in \(H-P_1\), a contradiction. If \(d_{H}(w_1)\le 2\), then \(X=\{u_1,u_s,v_1,w_1\}\) is the desired set. Thus \(d_{H}(w_1)\ge 3\), that is, \(d_{P_1}(w_1)\ge 2\). Note \(w_1\) and \(v_3\) lie on a path \(P=w_1,v_2,v_3\), and \(w_1,v_3\) send at least two edges each to \(P_1\). By Lemma 5, there exists a chorded cycle in \(\left<P_1 \cup P\right>\), a contradiction. ◻
Subclaim 8. For any \(u\in V(P_1)\), \(N_R(u)=\emptyset\).
Proof. We first prove \(d_{H}(v_1)\le 2\). Suppose not, that is, \(d_{H}(v_1)\ge 3\). Recall \(d_{P_1}(v_1)\le 1\). By Subclaim 7 and Lemma 11(iv), \(d_{P_1}(v_1)=1\) and \(d_{P_2}(v_1)=2\). Thus \(|P_2|=3\) and \(v_1v_3\in E(H)\). Since \(d_{P_1}(v_1) \le d_{P_1}(v_3)\) by the assumption, \(d_{P_1}(v_3)\ge 1\). Then \(\langle P_1\cup P_2 \rangle\) contains a cycle with chord \(v_1v_3\), a contradiction. Thus \(d_{H}(v_1)\le 2\). Suppose there exists a vertex in \(P_1\) with a neighbor \(w_1\) in \(R\). If \(d_{H}(w_1)\le 2\), then \(X=\{u_1,u_s,v_1,w_1\}\) is the desired set. Thus \(d_{H}(w_1) \ge 3\).
First suppose \(d_{P_1}(w_1)\ge 2\). Then \(d_{P_1}(w_1)=2\) by Lemma 11(v), and \(d_R(w_1)\ge 1\) by Subclaim 7. Let \(w_2\in N_{R}(w_1)\). If \(d_{H}(w_2) \le 2\), then \(X=\{u_1,u_s,v_1,w_2\}\) is the desired set. Thus \(d_{H}(w_2) \ge 3\). If \(d_{P_1}(w_2)\ge 2\), then we have two vertices on a path \(P=w_1,w_2\), each sending at least two edges to another path \(P_1\), and by Lemma 5, a chorded cycle exists in \(\left<P_1 \cup P\right>\), a contradiction. Thus \(d_{P_1}(w_2) \le 1\), and by Subclaim 7, \(d_{R}(w_2)\ge 2\). Let \(w_3\in N_{R-w_1}(w_2)\). If \(d_{H}(w_3)\le 2\), then \(X=\{u_1,u_s,v_1,w_3\}\) is the desired set. Thus \(d_{H}(w_3) \ge 3\). Suppose \(d_{P_1}(w_3) \ge 2\). Then consider the path \(P=w_1,w_2,w_3\). Since \(w_1\) and \(w_3\) send at least two edges to another path \(P_1\), a chorded cycle exists in \(\left<P_1 \cup P\right>\) by Lemma 5, a contradiction. Thus \(d_{P_1}(w_3) \le 1\). Also, \(N_{R-\{w_1,w_2\}}(w_3)=\emptyset\), otherwise, there exists a longer path than \(P_2\) in \(H-P_1\), a contradiction. By Subclaim 7, \(N_{P_2}(w_3)=\emptyset\). Thus \(d_{P_1}(w_3)=1\) and \(w_1,w_2\in N_H(w_3)\). Then \(\langle P_1\cup P \rangle\) contains a cycle with chord \(w_1w_3\), a contradiction.
Next suppose \(d_{P_1}(w_1)=1\). Then \(d_{R}(w_1)\ge 2\) by Subclaim 7. Let \(w_2, w_3\in N_{R}(w_1)\). If \(d_{H}(w_i)\le 2\) for some \(i\in \{2,3\}\), then \(X=\{u_1,u_s,v_1,w_i\}\) is the desired set. Thus \(d_{H}(w_i) \ge 3\) for each \(i\in \{2,3\}\). Suppose \(d_{R}(w_i)\ge 3\) for some \(i\in \{2,3\}\). Without loss of generality, we may assume \(i=2\). Then \(w_2\) has a neighbor \(w_4\) in \(R\) distinct from \(w_1\) and \(w_3\), and hence \(w_3, w_1, w_2, w_4\) is a longer path than \(P_2\) in \(H-P_1\), a contradiction. Thus for each \(i\in \{2,3\}\), \(d_{R}(w_i)\le 2\), and then \(d_{P_1}(w_i)\ge 1\) by Subclaim 7. Note \(w_i\) for each \(i\in \{2,3\}\) does not have a neighbor in \(R\) distinct from \(w_1,w_2,w_3\), otherwise, there exists a longer path than \(P_2\) in \(H-P_1\), a contradiction. Now suppose \(d_{R}(w_i)=2\) for some \(i\in \{2,3\}\). Then \(w_2w_3\in E(H)\). Let \(P=w_2,w_1,w_3\). Since \(d_{P_1}(w_i)\ge 1\) for each \(i\in \{2,3\}\), there exists a cycle with chord \(w_2w_3\) in \(\langle P_1\cup P \rangle\), a contradiction. Thus \(d_{R}(w_i)\le 1\) for each \(i\in \{2,3\}\), and then \(d_{P_1}(w_i)\ge 2\) by Subclaim 7. By Lemma 5, a chorded cycle exists in \(\langle P_1\cup P \rangle\), a contradiction. ◻
Since \(H\) is connected, we get a contradiction by Subclaims 7 and 8. Thus Claim 6 holds. ◻
Claim 9. We have \(d_{P_1}(v_t)\ge 1\).
Proof. Suppose \(d_{P_1}(v_t) =0\). By the assumption (\(d_{P_1}(v_1) \le d_{P_1}(v_t)\)), we have \(d_{P_1}(v_1) =0\). Then we may assume \(|P_2|=t\ge 3\), otherwise, we get a contradiction by Claim 6 and the connectedness of \(H\). Recall \(u_1u_s\not\in E(H)\). By Lemmas 11(iii) and (iv), \(d_H(v_j)\le 2\) for each \(j\in \{1,t\}\). If \(v_1v_t\not\in E(H)\), then \(X=\{u_1,u_s,v_1,v_t\}\) is the desired set. Thus \(v_1v_t \in E(H)\).
First suppose \(|P_2|=t=3\). By Claim 6, \(H=\left<P_1 \cup P_2\right>\). Since \(v_1v_3\in E(H)\), consider \(P'_2=v_2,v_1,v_3\). Then \(v_2\) can be regarded as an endpoint of \(P'_2\). Since \(d_{P_1}(v_1)=0\), we may assume \(d_{P_1}(v_2)=0\) by considering \(v_2\) instead of \(v_1\). Since \(N_{P_1}(P_2)=\emptyset\), this contradicts the connectedness of \(H\).
Next suppose \(|P_2|=t\ge 4\). Recall \(u_1u_s \not\in E(H)\) and \(v_1v_t \in E(H)\). Consider \(P'_2=P_2^-[v_{t-1},v_1],v_t\). Then \(v_{t-1}\) can be regarded as an endpoint of \(P'_2\). Thus \(N_R(v_{t-1})=\emptyset\) by Lemma 11(iii), and \(d_{P_2}(v_{t-1})\le 2\) by Lemma 11(iv). Since \(d_{P_1}(v_1)=0\), we may assume \(d_{P_1}(v_{t-1})=0\) by considering \(v_{t-1}\) instead of \(v_1\). Thus \(d_{H}(v_{t-1})=2\). Hence \(X=\{u_1,u_s,v_1,v_{t-1}\}\) is the desired set, and Claim 9 holds. ◻
Now we consider the following three cases based on \(|P_2|\).
Case 1. Suppose \(|P_2|=t=1\).
Then \(P_2=v_1\). By Claim 6, \({H}=\left<P_1 \cup P_2\right>\). Since \(|H|\ge 15\), \(|P_1| \ge 14\). Recall \(d_{P_1}(v_1)\le 2\) when \(t=1\). By Claim 9, \(d_{P_1}(v_1)\in \{1,2\}\). Note \(d_H(v_1)=d_{P_1}(v_1)\).
First suppose \(d_{P_1}(v_1)=2\). Let \(u_i,u_j\in N_{P_1}(v_1)\) with \(i<j\). Note \(i\ge 2\) and \(j\le s-1\) by Lemma 11(i). If \(j=i+1\), then \({H}\) contains a Hamiltonian path, a contradiction. Thus \(j \ge i+2\). By Lemma 9, \(d_{H}(u_{\ell})=2\) for some \(\ell \in \{i+1,j-1\}\). Note \(u_{\ell}u_1, u_{\ell}u_s\not\in E(H)\). Then \(X=\{u_1,u_{\ell},u_s,v_1\}\) is the desired set.
Next suppose \(d_{P_1}(v_1)=1\). Note \(d_{P_1}(u_1)\le 2\). Assume \(u_1u_i\in E(H)\) for some \(4\le i \le s-1\). By Lemma 6, \(d_{P_1}(u_{i-1})=2\). If \(v_1u_{i-1}\in E(H)\), then \(v_1,u_{i-1},P_1^{-}[u_{i-1},u_1],u_i,P_1[u_i,u_s]\) is a Hamiltonian path, a contradiction. Thus \(v_1u_{i-1}\not\in E(H)\) and \(d_H(u_{i-1})=2\). Then \(X=\{u_1,u_{i-1},u_s,v_1\}\) is the desired set. Thus if \(d_{P_1}(u_1)=2\), then \(u_1u_3\in E(H)\). Then \(d_{P_1}(u_i)=2\) for some \(3\le i\le 6\) by Lemma 7. Similarly, either \(d_{P_1}(u_s)=1\) or \(u_su_{s-2}\in E(H)\) by symmetry. Then \(d_{P_1}(u_j)=2\) for some \(s-5\le j\le s-2\) by Lemma 8. Note \(|P_1|=s\ge 14\). Since \(d_{P_1}(v_1)=1\) by our assumption, \(v_1u_{\ell}\not\in E(H)\) for some \(\ell \in\{i,j\}\), and \(d_H(u_{\ell})=2\). Thus \(X=\{u_1,u_{\ell},u_s,v_1\}\) is the desired set.
Case 2. Suppose \(|P_2|=t\in \{2,3\}\).
By Claim 6, \(H=\left<P_1 \cup P_2\right>\). Recall \(d_{P_1}(\{v_1,v_t\})\le 3\), \(d_{P_1}(v_1) \le 1\), and \(d_{P_1}(v_t) \le 2\). We also note \(d_{P_1}(\{v_1,v_t\})\ge 1\) by Claim 9. Since \(|H|\ge 15\), \(|P_1|=s\ge 12\).
First suppose \(|N_{P_1}(\{v_1,v_t\})|\in \{2,3\}\). Let \(u_i, u_j\in N_{P_1}(\{v_1,v_t\})\) with \(i<j\). Assume \(j=i+1\). Then \(H\) contains a longer path than \(P_1\), a contradiction. Thus \(j\ge i+2\). Note \(i\ge 2\) and \(j\le s-1\) by Lemma 11(i). By Lemma 9, \(d_{H}(u_{\ell})=2\) for some \(\ell \in \{i+1,j-1\}\). Note \(u_{\ell}u_1\not\in E(H)\) and \(u_{\ell}u_s\not\in E(H)\). If \(d_H(v_1)\le 2\), then \(X=\{u_1,u_{\ell},u_s,v_1\}\) is the desired set. Thus we may assume that \(d_H(v_1)\ge 3\). Since \(d_{P_1}(v_1) \le 1\) and \(d_{P_2}(v_1) \le 2\), we have \(d_{P_1}(v_1)=1\) and \(d_{P_2}(v_1)=2\). Then \(t=3\) and \(v_1v_3\in E(H)\). Since \(d_{P_1}(v_1) \le d_{P_1}(v_t)=d_{P_1}(v_3)\) by the assumption, we have \(d_{P_1}(v_3)\ge 1\). Thus \(\langle P_1\cup P_2 \rangle\) contains a cycle with chord \(v_1v_3\), a contradiction.
Next suppose \(|N_{P_1}(\{v_1,v_t\})|=1\). Assume \(u_1u_i\in E(H)\) for some \(4\le i\le s-1\). By Lemma 6, \(d_{P_1}(u_{i-1})=2\). Let \(P'_1=P^-_1[u_{i-1},u_1],u_i,P_1[u_i,u_s]\). Then \(|P'_1|=|P_1|\) and \(u_{i-1}\) can be regarded as an endpoint of \(P'_1\). By Lemma 11(i), \(d_{P_2}(u_{i-1})=0\). Then \(d_{H}(u_{i-1})=d_{P_1}(u_{i-1})=2\). If \(d_H(v_1)\le 2\), then \(X=\{u_1,u_{i-1},u_s,v_1\}\) is the desired set. Thus we may assume that \(d_H(v_1)\ge 3\). Then \(d_{P_1}(v_1)=1\), and \(d_{P_2}(v_1)=2\), that is, \(t=3\) and \(v_1v_3\in E(H)\). Also, \(d_{P_1}(v_3)\ge 1\). Thus \(\langle P_1\cup P_2 \rangle\) contains a cycle with chord \(v_1v_3\), a contradiction. Hence, either \(d_{P_1}(u_1)=1\) or \(u_1u_3\in E(H)\). Then \(d_{P_1}(u_i)=2\) for some \(3\le i\le 6\) by Lemma 7. Similarly, either \(d_{P_1}(u_s)=1\) or \(u_su_{s-2}\in E(H)\) by symmetry. Then \(d_{P_1}(u_j)=2\) for some \(s-5\le j\le s-2\) by Lemma 8. Since \(|N_{P_1}(\{v_1,v_t\})|=1\) by our assumption, \(u_{\ell} \not\in N_{P_1}(\{v_1,v_t\})\) for some \(\ell \in\{i,j\}\). Suppose \(t=2\). Then \(d_H(v_1)\le 2\) and \(d_{H}(u_{\ell})=d_{P_1}(u_{\ell})=2\). Thus \(X=\{u_1,u_{\ell},u_s,v_1\}\) is the desired set. Hence \(t=3\). If \(v_1v_3\not\in E(H)\), then \(d_H(v_1)\le 2\) and \(d_H(v_3)\le 2\). Thus \(X=\{u_1,u_s,v_1,v_3\}\) is the desired set. Hence we may assume that \(v_1v_3\in E(H)\). Note \(d_{P_1}(v_1)\le 1\). Suppose \(d_{P_1}(v_1)=1\). Since \(d_{P_1}(v_3)\ge 1\), \(\langle P_1\cup P_2 \rangle\) contains a cycle with chord \(v_1v_3\), a contradiction. Suppose \(d_{P_1}(v_1)=0\). Then \(d_H(v_1)=2\). If \(d_H(u_{\ell})=2\), then \(X=\{u_1,u_{\ell},u_s,v_1\}\) is the desired set. Thus we may assume that \(d_H(u_{\ell})\ge 3\). Then \(u_{\ell}v_2\in E(H)\). Since \(d_{P_1}(v_3)\ge 1\), \(\langle P_1\cup P_2 \rangle\) contains a cycle with chord \(v_2v_3\), a contradiction.
Case 3. Suppose \(|P_2|=t\ge 4\).
Recall \(d_{P_1}(v_1) \le 1\) and \(d_{P_1}(v_t) \le 2\). We consider two subcases as follows.
Subcase 1. Suppose \(d_{P_1}(v_1)=1\).
By Claim 9, \(d_{P_1}(v_t) \ge 1\). Then \(d_{P_2}(v_1)=d_{P_2}(v_t)=1\), otherwise, there exists a cycle in \(\langle P_1\cup P_2 \rangle\) with chord adjacent to \(v_1\) or \(v_t\), a contradiction. Thus \(d_{H}(v_1)=2\) by Lemma 11(iii). If \(d_{P_1}(v_t)=1\), then \(d_{H}(v_t)=2\) by Lemma 11(iii). Then \(X=\{u_1,u_s,v_1,v_t\}\) is the desired set. Thus \(d_{P_1}(v_t)=2\). Let \(u_i, u_j\in N_{P_1}(v_t)\) with \(i<j\). Consider the vertex \(v_{t-1}\). If \(d_{H}(v_{t-1})=2\), then \(X=\{u_1,u_s,v_1,v_{t-1}\}\) is the desired set. Thus \(d_{H}(v_{t-1})\ge 3\). If \(d_{P_2}(v_{t-1})\ge 3\), then there exists a cycle in \(\langle P_1\cup P_2 \rangle\) with chord adjacent to \(v_{t-1}\), a contradiction. Thus \(d_{P_2}(v_{t-1})=2\), and then \(N_{P_1}(v_{t-1})\ne \emptyset\) or \(N_{R}(v_{t-1})\ne \emptyset\).
First suppose \(N_{P_1}(v_{t-1})\ne \emptyset\). If \(v_1\) or \(v_{t-1}\) has a neighbor in \(P_1[u_1,u_i]\cup P_1[u_j,u_s]\), then there exist three parallel edges between \(P_1\) and \(P_2\), and by Lemma 3, a chorded cycle exists in \(\langle P_1\cup P_2 \rangle\), a contradiction. Thus \(N_{P_1(u_i,u_j)}(v_{\ell})\ne \emptyset\) for each \(\ell\in \{1,t-1\}\). Then we again have three parallel edges or three crossing edges, and by Lemma 3, a chorded cycle exists in \(\langle P_1\cup P_2 \rangle\), a contradiction.
Next suppose \(N_{R}(v_{t-1})\ne \emptyset\). Let \(w\in N_{R}(v_{t-1})\). If \(d_{H}(w)\le 2\), then \(X=\{u_1,u_s,v_1,w\}\) is the desired set. Thus \(d_{H}(w) \ge 3\). Then \(d_{P_1}(w)\le 1\), otherwise, since \(d_{P_1}(v_t)=2\), there exists a chorded cycle in \(\langle P_1\cup P_2 \rangle\) by Lemma 5, a contradiction. Since \(P_2\) is a longest path in \(H-P_1\), \(N_R(w)=\emptyset\). Thus \(d_{P_1}(w)=1\) and \(d_{P_2}(w)=2\). Let \(u_p\in N_{P_1}(v_1)\) and \(u_q\in N_{P_1}(w)\). Without loss of generality, we may assume \(p\le q\). By Lemma 11(iii), \(wv_1, wv_t\not\in E(H)\). Thus \(wv_{\ell}\in E(H)\) for some \(2\le \ell \le t-2\). Then \(w,v_{t-1},P_2^{-}[v_{t-1},v_1],u_p,P_1[u_p,u_q],w\) is a cycle with chord \(wv_{\ell}\), a contradiction.
Subcase 2. Suppose \(d_{P_1}(v_1)=0\).
Suppose \(v_1v_t\in E(H)\). Then note \(d_H(v_1)=2\). Now we consider the path \(P'_2=P_2^-[v_{t-1},v_1],v_t\). Then \(v_{t-1}\) can be regarded as an endpoint of \(P'_2\). Since \(d_{P_1}(v_1)=0\) by the assumption, we may assume \(d_{P_1}(v_{t-1})=0\) by considering \(v_{t-1}\) instead of \(v_1\). Thus \(d_H(v_{t-1})=2\). Recall \(u_1u_s\not\in E(H)\). Then \(X=\{u_1,u_s,v_1,v_{t-1}\}\) is the desired set. Thus \(v_1v_t\not\in E(H)\). If \(d_{H}(v_t)\le 2\), then \(X=\{u_1,u_s,v_1,v_t\}\) is the desired set. Thus \(d_{H}(v_t)\ge 3\). By Lemma 11(iii), (iv), and (v), we have \(d_{H}(v_t)\le 4\) and \(d_{P_1}(v_t)\in \{1,2\}\).
First suppose \(d_{P_1}(v_t)=2\). Let \(u_i, u_j\in N_{P_1}(v_t)\) with \(i<j\). Note \(i\ge 2\) and \(j\le s-1\) by Lemma 11(i), and \(|P_1|\ge |P_2|\ge 4\). If \(j=i+1\), then there exists a longer path than \(P_1\), a contradiction. Thus \(j\ge i+2\). Therefore, \(|P_1|\ge 5\). If \(d_{H}(u_{\ell})=2\) for some \(\ell \in \{i+1,j-1\}\), then \(X=\{u_1,u_{\ell},u_s,v_1\}\) is the desired set. Thus \(d_{H}(u_{\ell})\ge 3\) for each \(\ell \in \{i+1,j-1\}\). By Lemma 9, we may assume \(H\ne \left< P_1 \cup P_2 \right>\). Now we claim \(N_{R}(u_{\ell})\ne \emptyset\) for some \(\ell \in \{i+1,j-1\}\). Assume not. Note \(N_{P_2}(u_{\ell})=\emptyset\) since \(P_1\) is a longest path in \(H\). Since \(H\) does not contain a chorded cycle, there exist edges \(u_{i+1}u_h\) with \(h>j\) and \(u_{j-1}u_{h'}\) with \(h'<i\). Then \[P_1[u_{h'},u_i],v_t,u_j,P_1[u_j,u_{h}],u_{i+1},P_1[u_{i+1},u_{j-1}],u_{h'}\] is a cycle with chord \(u_iu_{i+1}\) (and \(u_{j-1}u_j\)), a contradiction. Thus the claim holds. If \(j\ge i+3\), then we may assume \(\ell=j-1\), that is, \(N_{R}(u_{j-1})\ne \emptyset\), otherwise, consider \(P^-[u_s,u_1]\). Let \(w_1\in N_{R}(u_{j-1})\), and let \(P_3=w_1, \ldots, w_p\, (p\ge 1)\) be a longest path starting from \(w_1\) in \(R\). If \(d_{H}(w_p)\le 2\), then \(X=\{u_1,u_s,v_1,w_p\}\) is the desired set. Thus \(d_{H}(w_p)\ge 3\). If \(N_{P_2}(w)\ne \emptyset\) for some \(w\in V(P_3)\), that is, \(v_{\ell}\in N_{P_2}(w)\) for some \(1\le \ell \le t\), then \[P_1[u_1,u_{j-1}], w_1, P_3[w_1,w], v_{\ell}, P_2[v_{\ell},v_t], u_j, P_1[u_j,u_s]\] is a longer path than \(P_1\), a contradiction. Thus \(N_{P_2}(w)=\emptyset\) for any \(w\in V(P_3)\). Since \(P_3\) is a longest path starting from \(w_1\) in \(R\), \(N_{R-P_3}(w_p)=\emptyset\). Suppose \(|P_3|=p=1\). Since \(N_R(w_1)=\emptyset\) and \(d_H(w_p)\ge 3\), \(d_{P_1}(w_1)\ge 3\). This contradicts Lemma 11(v). Suppose \(|P_3|=p=2\). Then \(d_H(w_2)\ge 3\), and by Lemma 11(v), \(d_{P_1}(w_2)=2\). If \(u_{\ell}\in N_{P_1}(w_2)\) for some \(j\le \ell \le s\), then \[P_1[u_i,u_{j-1}],w_1,P_3[w_1,w_2],u_{\ell},P_1^-[u_{\ell},u_j],v_t,u_i\] is a cycle with chord \(u_{j-1}u_j\), a contradiction. Thus \(u_{\ell},u_{\ell'}\in N_{P_1}(w_2)\) for some \(1\le \ell<\ell' \le j-1\). Then \(P_1[u_{\ell},u_{j-1}],w_1,P_3[w_1,w_2],u_{\ell}\) is a cycle with chord \(w_2u_{\ell'}\), a contradiction. Suppose \(|P_3|=p\ge 3\). Then \(d_{P_3}(w_p)\le 2\). Assume \(d_{P_3}(w_p)=2\). Since \(d_{P_1}(w_p)\ge 1\), there exists a cycle in \(\langle P_1\cup P_3 \rangle\) with chord adjacent to \(w_p\), a contradiction. Thus \(d_{P_3}(w_p)=1\), and \(d_{P_1}(w_p)=2\). Then we have a chorded cycle in \(\langle P_1\cup P_3 \rangle\) as in the case where \(|P_3|=2\) by considering \(w_p\) instead of \(w_2\), a contradiction.
Next suppose \(d_{P_1}(v_t)=1\). Let \(u_i\in N_{P_1}(v_t)\) with \(1\le i\le s\). Note \(i\not\in \{1,s\}\) by Lemma 11(i). Since \(d_{H}(v_t)\ge 3\), \(d_{P_2}(v_t)=2\) by Lemmas 11(iii) and (iv). Let \(v_{\ell}\in N_{P_2}(v_t)\) with \(\ell \le t-2\). Now we consider the path \(P'_2=P_2[v_1,v_{\ell}],v_t,P_2^-[v_t,v_{\ell+1}]\). Then \(v_{\ell+1}\) can be regarded as an endpoint of \(P'_2\). Since \(d_{P_1}(v_t)=1\), we may assume \(d_{P_1}(v_{\ell+1})=1\). Let \(u_j\in N_{P_1}(v_{\ell+1})\) with \(1\le j\le s\). Note \(j\not\in \{1,s\}\) by Lemma 11(i). Then we may assume \(j\le i\), otherwise, consider \(P^-[u_s,u_1]\). Suppose \(\ell=t-2\), that is, \(v_tv_{t-2}\in E(H)\). Then \(P_1[u_j,u_i],v_t,v_{t-2},v_{t-1},u_j\) is a cycle with chord \(v_{t-1}v_t\), a contradiction. Thus \(\ell \le t-3\). If \(j=i-1\), then there exists a longer path than \(P_1\), a contradiction.
Suppose \(j=i\). Recall \(v_tv_{\ell}\in E(H)\) with \(\ell \le t-3\). If \(d_{H}(v_{t-1})=2\), then \(X=\{u_1,u_s,v_1,v_{t-1}\}\) is the desired set. Thus \(d_{H}(v_{t-1}) \ge 3\). Assume \(u_j\in N_{P_1}(v_{t-1})\) for some \(1\le j\le s\). We may assume \(j\le i\), otherwise, consider \(P^-[u_s,u_1]\). Then \(P_1[u_j,u_i],v_t,P_2[v_{\ell},v_{t-1}],u_j\) is a cycle with chord \(v_{t-1}v_t\), a contradiction. Assume \(v_{\ell'}\in N_{P_2}(v_{t-1})\) for some \(\ell' \le t-3\). Since \(v_tv_{\ell}\in E(H)\), we may assume \(\ell'<\ell\). Then \(P_2[v_{\ell'},v_{\ell}],v_t,u_i,P_2[v_{\ell+1},v_{t-1}],v_{\ell'}\) is a cycle with chord \(v_{\ell}v_{\ell+1}\) (and \(v_{t-1}v_t\)), a contradiction. Assume \(N_{R}(v_{t-1})\ne \emptyset\). Let \(w\in N_{R}(v_{t-1})\). Now we consider the path \(P'_2=P_2[v_1,v_{t-1}],w\). Then \(w\) can be regarded as an endpoint of \(P'_2\). Since \(d_{P_1}(v_t)=1\), we may assume \(d_{P_1}(w)=1\). Let \(u_j\in N_{P_1}(w)\) for some \(1\le j\le s\). We may assume \(j\le i\). Then \(P_2[v_{\ell},v_{t-1}],w,P_1[u_j,u_i],v_t,v_{\ell}\) is a cycle with chord \(v_{t-1}v_t\), a contradiction.
Suppose \(j\le i-2\). If \(d_{H}(u_h)=2\) for some \(h \in \{j+1,i-1\}\), then \(X=\{u_1,u_h,u_s,v_1\}\) is the desired set. Thus \(d_{H}(u_h)\ge 3\) for each \(h\in \{j+1,i-1\}\). Now we claim \(N_{R}(u_{h})\ne \emptyset\) for some \(h\in \{j+1,i-1\}\). Assume not. Note \(N_{P_2}(u_{h})=\emptyset\), since \(P_1\) is a longest path in \(H\). Since \(H\) does not contain a chorded cycle, there exist edges \(u_{j+1}u_m\) with \(m>i\) and \(u_{i-1}u_{m'}\) with \(m'<j\). Then \[P_1[u_{m'},u_j],v_{\ell+1}, P_2[v_{\ell+1},v_{t}],u_i,P_1[u_i,u_m],u_{j+1},P_1[u_{j+1},u_{i-1}],u_{m'}\] is a cycle with chord \(u_ju_{j+1}\) (and \(u_{i-1}u_i\)), a contradiction. Thus the claim holds. We also note that if \(j\le i-3\), then we may assume \(N_{R}(u_{i-1})\ne \emptyset\), otherwise, consider \(P^-[u_s,u_1]\). Let \(w_1\in N_{R}(u_{i-1})\), and let \(P_3=w_1, \ldots, w_p\, (p\ge 1)\) be a longest path in \(R\). Then, as in the above case where \(d_{P_1}(v_t)=2\), there exists a chorded cycle in \(H\), a contradiction. ◻
Lemma 13 ([8]). Let \(k\ge 2\) be an integer, and let \(G\) be a graph. Suppose \(G\) does not contain \(k\) vertex-disjoint chorded cycles. Let \(\mathscr{C}=\{C_1,\ldots, C_{k-1}\}\) be a minimal set of \(k-1\) vertex-disjoint chorded cycles in \(G\), and let \(H=G-\mathscr{C}\) and \(X\subseteq V(H)\) with \(|X|=4\). Suppose \(H\) contains a Hamiltonian path. Then \(d_{C_i}(X)\le 12\) for each \(1\le i\le k-1\).
Suppose \(G\) does not contain a chorded cycle.
Claim 10. \(G\) is connected.
Proof. Suppose not, then \(comp(G)\ge 2\). Let \(G_1, G_2, \ldots, G_{comp(G)}\) be the components of \(G\).
First suppose \(comp(G)\ge 4\). By Theorem 1, there exists \(x_i \in V(G_i)\) for each \(1\le i\le 4\) such that \(d_{G_i}(x_i)\le 2\). Let \(X=\{x_1,x_2,x_3,x_4\}\). Then \(X\) is an independent set with \(d_{G}(X)\le 8\). This contradicts the \(\sigma_4(G)\) condition.
Next suppose \(comp(G)=3\). Let \(|G_1|\ge |G_2|\ge |G_3|\). Since \(|G|\ge 15\) by the assumption, we have \(|G_1|\ge 5\). If \(G_1\) is complete, then \(G_1\) contains a chorded cycle. Thus we may assume \(G_1\) is not complete. By Theorem 2, there exist non-adjacent \(x_0,x_1\in V(G_1)\) such that \(d_{G_1}(\{x_0,x_1\})\le 4\). Also, by Theorem 1, there exists \(x_i \in V(G_i)\) for each \(i\in \{2,3\}\) such that \(d_{G_i}(x_i)\le 2\). Then \(X=\{x_0,x_1,x_2,x_3\}\) is an independent set with \(d_{G}(X)\le 8\), a contradiction.
Finally, suppose \(comp(G)=2\). Let \(|G_1|\ge |G_2|\). Since \(|G|\ge 15\), \(|G_1|\ge 8\). By Theorem 3 (Remark 1), \(G_1\) contains an independent set \(X_0\) of three vertices with \(d_{G_1}(X_0)\le 6\). Also, by Theorem 1, there exists \(x\in V(G_2)\) such that \(d_{G_2}(x)\le 2\). Then \(X=X_0\cup \{x\}\) is an independent set with \(d_{G}(X)\le 8\), a contradiction. ◻
Let \(P_1=u_1, \ldots, u_s\) be a longest path in \(G\). Note \(s\ge 3\), since \(|G|\ge 15\) and \(G\) is connected by Claim 10.
Claim 11. \(G\) contains a Hamiltonian path.
Proof. Suppose not, then \(P_1\) is not a Hamiltonian path in \(G\), and \(V(G-P_1)\ne \emptyset\). Let \(P_2=v_1, \ldots, v_t\) (\(t\ge 1\)) be a longest path in \(G-P_1\) such that \(d_{P_1}(v_1) \le d_{P_1}(v_t)\). By Lemma 12, there exists an independent set \(X\) of four vertices in \(G\) such that \(d_{G}(X)\le 8\). This contradicts the \(\sigma_4(G)\) condition. ◻
Since \(|G|\ge 15\), by Claim 11 and Lemma 10, there exists an independent set \(X\) of four vertices in \(G\) such that \(d_{G}(X) \le 8\), a contradiction. This completes the proof of Theorem 4. 0◻
By Theorem 4, we may assume \(k\ge 2\). Suppose Theorem 5 does not hold. Let \(G\) be an edge-maximal counter-example. If \(G\) is complete, then \(G\) contains \(k\) vertex-disjoint chorded cycles. Thus we may assume \(G\) is not complete. Let \(xy\not\in E(G)\) for some \(x, y\in V(G)\), and define \(G'=G+xy\), the graph obtained from \(G\) by adding the edge \(xy\). By the edge-maximality of \(G\), \(G'\) is not a counter-example. Thus \(G'\) contains \(k\) vertex-disjoint chorded cycles \(C_1, \ldots, C_k\). Without loss of generality, we may assume \(xy\not\in\cup_{i=1}^{k-1}E(C_i)\), that is, \(G\) contains \(k-1\) vertex-disjoint chorded cycles. Over all sets of \(k-1\) vertex-disjoint chorded cycles, choose \(C_1, \ldots , C_{k-1}\) with \(\mathscr{C}=\cup_{i=1}^{k-1}C_i\), \(H=G-\mathscr{C}\), and with \(P_1\) a longest path in \(H\), such that:
(A1) \(|\mathscr{C}|\) is as small as possible,
(A2) subject to (A1), \(comp(H)\) is as small as possible, and
(A3) subject to (A1) and (A2), \(|P_1|\) is as large as possible.
We may also assume \(H\) does not contain a chorded cycle, otherwise, \(G\) contains \(k\) vertex-disjoint chorded cycles, a contradiction.
Claim 12. \(H\) has an order at least \(18\).
Proof. Suppose to the contrary that \(|H|\le 17\). Next suppose \(|C_i| \le 11\) for each \(1 \le i \le k-1\). Since \(|G| \ge 11k+7\) by assumption, it follows that \(|H| \ge (11k+7)-11(k-1)=18\), a contradiction. Thus \(|C_i| \ge 12\) for some \(1 \le i \le k-1\). Without loss of generality, we may assume \(C_1\) is a longest cycle in \(\mathscr{C}\). Then \(|C_1|\ge 12\). By Lemma 1, \(C_1\) contains at most two chords, and if \(C_1\) has two chords, then these chords must be crossing. For integers \(t\) and \(r\), let \(|C_1|=4t+r\), where \(t \ge 3\) and \(0 \le r \le 3\).
Subclaim 13. Let \(t \ge 3\) be an integer. The cycle \(C_1\) contains \(t\) vertex-disjoint sets \(X_1, \ldots, X_t\) of four independent vertices each in \(G\) such that \(d_{C_1}(\cup_{i=1}^t X_i) \le 8t + 4\).
Proof. For any \(4t\) vertices of \(C_1\), their degree sum in \(C_1\) is at most \(4t \times 2+4=8t+4\), since \(C_1\) has at most two chords. Thus it only remains to show that \(C_1\) contains \(t\) vertex-disjoint sets of four independent vertices each. Recall \(|C_1|=4t+r \geq4t\). Start anywhere on \(C_1\) and label the first \(4t\) vertices of \(C_1\) with labels 1 through \(t\) in order, starting over again with 1 after using label \(t\). If \(r\ge 1\), then label the remaining \(r\) vertices of \(C_1\) with the labels \(t+1, \dots, t+r\). (See Fig. 2.) The labeling above yields \(t\) vertex-disjoint sets of four vertices each, where all the vertices labeled with 1 are one set, all the vertices labeled with 2 are another set, and so on. Given this labeling, since \(t \ge 3\), any vertex in \(C_1\) has a different label than the vertex that precedes it on \(C_1\) and the vertex that succeeds it on \(C_1\). Let \(C_0\) be the cycle obtained from \(C_1\) by removing all chords. Then the vertices in each of the sets are independent in \(C_0\). Thus the only way vertices in the same set are not independent in \(C_1\) is if the endpoints of a chord of \(C_1\) were given the same label. Note any vertex labeled \(i\) is distance at least 3 in \(C_0\) from any other vertex labeled \(i\). Thus even if we exchange the label of \(x\) in \(C_0\) for the one of \(x^-\) (or \(x^+\)), the vertices in each of the resulting \(t\) sets are still independent in \(C_0\).
Case 1. No chord of \(C_1\) has endpoints with the same label.
Then there exist \(t\) vertex-disjoint sets of four independent vertices each in \(C_1\).
Case 2. Exactly one chord of \(C_1\) has endpoints with the same label.
Recall \(C_1\) contains at most two chords, and if \(C_1\) contains two chords, then these chords must be crossing. Since \(|C_1|\geq 12\), even if \(C_1\) has two chords, each chord has an endpoint \(x\) such that there exists a vertex \(x'\in \{x^-,x^+\}\) which is not an endpoint of the other chord. Choose such an endpoint \(x\) of the chord whose endpoints were assigned the same label, and exchange the label of \(x\) for the one of \(x'\). The vertices in each of the resulting \(t\) sets are independent in \(C_1\), and now no chord of \(C_1\) has endpoints with the same label. Thus there exist \(t\) vertex-disjoint sets of four independent vertices each in \(C_1\).
Case 3. Two chords of \(C_1\) each have endpoints with the same label.
Then the two chords are crossing. Since endpoints of a chord have the same label in this case, recall these endpoints have distance at least 3. First suppose there exists an endpoint \(x\) of one chord of \(C_1\) which is adjacent to an endpoint \(y\,(=x^+)\) of the other chord on \(C_1\). (See Fig. 3(a).) Now we exchange the label of \(x\) for the one of \(y\). Then no chord of \(C_1\) has endpoints with the same label, and the vertices in each of the resulting \(t\) sets are independent in \(C_1\). Thus there exist \(t\) vertex-disjoint sets of four independent vertices each in \(C_1\).
Next suppose no endpoint of one chord of \(C_1\) is adjacent to an endpoint of the other chord on \(C_1\). (See Fig. 3(b).) Let \(x_1x_2, y_1y_2\) be the two distinct chords of \(C_1\). Since the two chords are crossing, without loss of generality, we may assume \(x_1, y_1, x_2, y_2\) are in that order on \(C_1\). Now we exchange the labels of \(x_1\) and \(x_1^+\), and next the ones of \(y_2\) and \(y_2^-\). Then no chord of \(C_1\) has endpoints with the same label, and the vertices in each of the resulting \(t\) sets are independent in \(C_1\). Thus there exist \(t\) vertex-disjoint sets of four independent vertices each in \(C_1\). ◻
Since \(|C_1| \ge 12\), \(d_{C_1}(v)\le 2\) for any \(v \in V(H)\) by Lemma 2 and (A1). Thus since \(|H| \le 17\) by our assumption, it follows that \(|E(H,C_1)| \le 34\). Let \(\mathscr{X}=\cup_{i=1}^t X_i\) be as in Subclaim 13. By the \(\sigma_4(G)\) condition, \(d_G(\mathscr{X})\ge t(12k-3)\). Suppose \(k=2\). Then \(\mathscr{C}\) has only one cycle \(C_1\). Since \(k=2\) and \(t \ge 3\), \(|E(C_1,H)| \ge d_H(\mathscr{X}) \ge t(12k-3)-(8t+4)=13t-4 \ge 35\), a contradiction. Thus \(k\ge 3\). Then we have \[\begin{aligned} |E(\mathscr{X}, \mathscr{C}-C_1)| &= d_{G}(\mathscr{X})-d_{C_1}(\mathscr{X})-d_H(\mathscr{X})\\ & \ge t(12k-3) – (8t+4) -34\\ &=12kt -11t -38, \end{aligned}\] and since \(t \ge 3\), \[\begin{aligned} 12kt -11t -38 &= 12t(k-1)+t-38 \ge 12t(k-1)-35 \\ &> 12t(k-1)-12t \\ &= 12t(k-2). \end{aligned}\] Thus \(|E(\mathscr{X}, C')|>12t\) for some \(C'\) in \(\mathscr{C}-C_1\), since \(\mathscr{C}-C_1\) contains \(k-2\) vertex-disjoint chorded cycles. Let \(h=\max\{d_{C'}(v)|v \in \mathscr{X}\}\). Let \(v^{*}\) be a vertex of \(\mathscr{X}\) such that \(d_{C'}(v^{*})=h\). Since \(|E(\mathscr{X}, C')|>12t\), if \(h\le 3\), then \(|E(\mathscr{X}, C')|\le 3\times 4t=12t\), a contradiction. Thus we may assume \(h\ge 4\). By the maximality of \(C_1\), \(|C'| \le |C_1| = 4t+r\). It follows that \(h=d_{C'}(v^{*}) \le |C'| \le 4t+r\). Recall \(t \ge 3\) and \(0\le r \le 3\). Then \[\begin{aligned} |E(\mathscr{X}-\{v^{*}\}, C')| \ge (12t+1)-d_{C'}(v^{*}) \ge (12t+1)-(4t+r) =8t-r+1 \ge 22. \label{21 edges out} \end{aligned}\tag{1}\] Since \(h=d_{C'}(v^{*})\ge 4\), let \(v_1,v_2,v_3,v_4\) be neighbors of \(v^{*}\) in that order on \(C'\). Note \(v_1,v_2,v_3,v_4\) partition \(C'\) into four intervals \(C'[v_i,v_{i+1})\) for each \(1\le i \le 4\), where \(v_5=v_1\). By (1), there exist at least 22 edges from \(C_1-v^{*}\) to \(C'\). Thus some interval \(C'[v_i,v_{i+1})\) contains at least six of these edges. Without loss of generality, we may assume this interval is \(C'[v_4,v_1)\). Then by Lemma 4, \(\langle(C_1-v^{*}) \cup C'[v_4,v_1)\rangle\) contains a chorded cycle not containing at least one vertex of \(\left<(C_1-v^{*}) \cup C'[v_4,v_1)\right>\). Also, \(v^{*},C'[v_1,v_3],v^{*}\) is a cycle with chord \(v^{*}v_2\), and it uses no vertices from \(C'[v_4,v_1)\). Thus we have two shorter vertex-disjoint chorded cycles in \(\left<C_1 \cup C' \right>\), contradicting (A1). Hence Claim 12 holds. ◻
Claim 14. \(H\) is connected.
Proof. Suppose not, then \(comp(H)\ge 2\). Let \(H_1, H_2, \dots, H_{comp(H)}\) be the components of \(H\). First we prove the following subclaim.
Subclaim 15. Suppose \(X\) is an independent set of four vertices in \(H\) such that \(d_{H}(X)\le 8\). Then there exists some \(C\) in \(\mathscr{C}\) such that the degree sequences from four vertices of \(X\) to \(C\) are \((4,4,4,1)\), \((4,4,3,2)\) or \((4,3,3,3)\). Furthermore, then \(|C|=4\).
Proof. By the \(\sigma_4(G)\) condition, \(d_\mathscr{C}(X)\ge (12k-3)-8=12k-11>12(k-1)\). Thus there exists some \(C\) in \(\mathscr{C}\) such that \(d_C(X) \ge 13\). By Lemma 2, \(d_C(x) \le 4\) for any \(x\in X\). Now we consider degree sequences defined in Section 1 (Introduction) from four vertices of \(X\) to \(C\). Recall that when we write \((d_1,d_2,d_3,d_4)\), we assume \(d_{C}(x_j)=d_j\) for each \(1\le j\le 4\), since it is sufficient to consider the case of equality. It follows that the degree sequences from four vertices of \(X\) to \(C\) are \((4,4,4,1)\), \((4,4,3,2)\) or \((4,3,3,3)\). Since each degree sequence contains a vertex with degree 4 in \(C\), we have \(|C|=4\) by Lemma 2. Thus the subclaim holds. ◻
Now we consider the following three cases based on \(comp(H)\).
Case 1. Suppose \(comp(H)\ge 4\).
By Theorem 1, there exists \(x_i \in V(H_i)\) for each \(1\le i\le 4\) such that \(d_{H_i}(x_i)\le 2\). Let \(X=\{x_1,x_2,x_3,x_4\}\). Then \(X\) is an independent set and \(d_{H}(X)\le 8\). By Subclaim 15, the degree sequences from four vertices of \(X\) to some \(C\) in \(\mathscr{C}\) are \((4,4,4,1)\), \((4,4,3,2)\) or \((4,3,3,3)\) and \(|C|=4\). Let \(C=v_1,v_2,v_3,v_4,v_1\). Without loss of generality, we may assume \(d_C(x_1) \ge d_C(x_2) \ge d_C(x_3) \ge d_C(x_4)\). Then \(d_C(x_1)=4\). Since \(|C|=4\), for each degree sequence, \(x_2, x_3, x_4\) must all have a common neighbor in \(C\), say \(v_1\). Since \(d_C(x_1)=4\), \(C'=x_1,v_2,v_3,v_4,x_1\) is a 4-cycle with chord \(x_1v_3\). If \(x_1\) is not a cut-vertex of \(H_1\), then \(H_1-x_1\) is connected. Replacing \(C\) in \(\mathscr{C}\) by \(C'\), we consider the new \(H'\). Then \(comp(H')\le comp(H)-2\). This contradicts (A2). Thus we may assume \(x_1\) is a cut-vertex of \(H_1\). Since \(d_{H_1}(x_1)\le 2\), \(d_{H_1}(x_1)=2\). Thus \(comp(H_1-x_1)=2\), and \(comp(H')\le comp(H)-1\) for the new \(H'\). This contradicts (A2).
Case 2. Suppose \(comp(H)=3\).
Without loss of generality, we may assume \(|H_1|\ge |H_2|\ge |H_3|\). Since \(|H| \ge 18\) by Claim 12, we have \(|H_1|\ge 6\). Let \(P_1=u_1, \ldots, u_s\) be a longest path in \(H_1\). Note \(s\ge 3\). By Theorem 1, there exists \(x_j\in V(H_j)\) for each \(j\in \{2,3\}\) such that \(d_{H_j}(x_j)\le 2\).
First suppose \(u_1u_s\in E(G)\). Then \(P_1[u_1,u_s],u_1\) is a Hamiltonian cycle in \(H_1\), otherwise, since \(H_1\) is connected, there exists a longer path than \(P_1\), a contradiction. Since \(H_1\) does not contain a chorded cycle, we have \(u_1u_3\not\in E(H_1)\). Note \(d_{H_1}(u_i)=2\) for each \(i\in \{1,3\}\). Let \(X=\{u_1,u_3,x_2,x_3\}\). Then \(X\) is an independent set and \(d_{H}(X)\le 8\). By Subclaim 15, the degree sequences from four vertices of \(X\) to some \(C\) in \(\mathscr{C}\) are \((4,4,4,1)\), \((4,4,3,2)\) or \((4,3,3,3)\) and \(|C|=4\). Let \(C=v_1,v_2,v_3,v_4,v_1\). Without loss of generality, we may assume \(d_{C}(u_1)\ge d_{C}(u_3)\). Then \(d_C(u_1)\ge 3\) and \(N_C(u_3)\cap N_C(x_2)\cap N_C(x_3)\ne \emptyset\) by the degree sequences. Without loss of generality, we may assume \(v_1\in N_C(u_3)\cap N_C(x_2)\cap N_C(x_3)\). Suppose \(d_C(u_1)=4\). Then \(C'=u_1,v_2,v_3,v_4,u_1\) is a 4-cycle with chord \(u_1v_3\). Since \(H_1\) contains a Hamiltonian cycle, \(u_1\) is not a cut-vertex of \(H_1\). Thus \(H_1-u_1\) is connected. Replacing \(C\) in \(\mathscr{C}\) by \(C'\), we consider the new \(H'\). Then \(comp(H')\le comp(H)-2=3-2=1\). This contradicts (A2). Thus \(d_C(u_1)=3\) since \(d_C(u_1)\ge 3\). Then the degree sequence is \((4,4,3,2)\) or \((4,3,3,3)\). Without loss of generality, we may assume \(d_C(x_2)\le d_C(x_3)\). In each degree sequence, it is sufficient to consider \(d_C(u_1)=3\), \(d_C(u_3)=2\), \(d_C(x_2)=3\) and \(d_C(x_3)=4\). Without loss of generality, we may assume \(v_j\in N_C(u_1)\) for each \(1\le j\le 3\). Then \(C'=u_1,v_1,v_2,v_3,u_1\) is a 4-cycle with chord \(u_1v_2\). If \(v_4\in N_C(x_2)\), then \(v_4\in N_C(x_2)\cap N_C(x_3)\) since \(d_C(x_3)=4\). Then \(comp(H')\le comp(H)-1=3-1=2\) for the new \(H'\), a contradiction. Thus \(N_C(u_1)=N_C(x_2)\). Note \(C\) has a chord. Suppose \(v_1v_3\in E(G)\). Then \(C'=u_1,v_1,v_4,v_3,u_1\) is a 4-cycle with chord \(v_1v_3\). Since \(d_C(x_3)=4\), \(v_2\in N_C(x_2)\cap N_C(x_3)\). Then \(comp(H')\le comp(H)-1=3-1=2\) for the new \(H'\), a contradiction. Suppose \(v_2v_4\in E(G)\). Then \(C'=u_1,v_1,v_4,v_2,u_1\) is a 4-cycle with chord \(v_1v_2\). Since \(d_C(x_3)=4\), \(v_3\in N_C(x_2)\cap N_C(x_3)\). Then \(comp(H')\le comp(H)-1=3-1=2\) for the new \(H'\), a contradiction.
Next suppose \(u_1u_s\not\in E(G)\). Let \(X=\{u_1,u_s,x_2,x_3\}\). Since \(H_1\) does not contain a chorded cycle, \(d_{H_1}(u_i)\le 2\) for each \(i\in \{1,s\}\). Then \(X\) is an independent set and \(d_{H}(X)\le 8\). Replacing \(u_3\) by \(u_s\) in the above case where \(u_1u_s\in E(G)\), we get a similar contradiction.
Case 3. Suppose \(comp(H)=2\).
Let \(|H_1|\ge |H_2|\). Since \(|H|\ge 18\) by Claim 12, \(|H_1|\ge 9\). Let \(P_1=u_1, \ldots, u_s\) be a longest path in \(H_1\). Note \(s\ge 3\). By Theorem 1, there exists \(x_2\in V(H_2)\) such that \(d_{H_2}(x_2)\le 2\).
First suppose \(u_1u_s\in E(H_1)\). Note \(P_1[u_1,u_s],u_1\) is a Hamiltonian cycle in \(H_1\). Then \(X_0=\{u_1,u_3,u_5\}\) is an independent set and \(d_{H_1}(X_0)=6\), and \(X=X_0\cup \{x_2\}\) is an independent set and \(d_{H}(X)\le 8\). By Subclaim 15, the degree sequences from four vertices of \(X\) to some \(C\) in \(\mathscr{C}\) are \((4,4,4,1)\), \((4,4,3,2)\) or \((4,3,3,3)\), and \(|C|=4\). Let \(C=v_1,v_2,v_3,v_4,v_1\). Since \(X_0\) is on the Hamiltonian cycle, we may assume \(d_C(u_1)=\max\{d_C(u)\,|\, u\in \{u_1,u_3,u_5\}\}\). Then \(d_C(u_1)\ge 3\) by the degree sequences. Suppose \(d_C(u_1)=4\). Since \(N_C(u_3) \cap N_C(x_2)\ne \emptyset\) by the degree sequences, without loss of generality, we may assume \(v_4\in N_C(u_3) \cap N_C(x_2)\). Since \(d_C(u_1)=4\), \(v_i\in N_C(u_1)\) for each \(1\le i\le 3\). Then \(C'=u_1,v_1,v_2,v_3,u_1\) is a 4-cycle with chord \(u_1v_2\). Since \(H_1\) contains a Hamiltonian cycle, \(u_1\) is not a cut-vertex of \(H_1\). Thus \(H_1-u_1\) is connected. Replacing \(C\) in \(\mathscr{C}\) by \(C'\), we consider the new \(H'\). Then \(comp(H')\le comp(H)-1=2-1=1\) for the new \(H'\). This contradicts (A2). Now suppose \(d_C(u_1)=3\). Then by the maximality of \(d_C(u_1)\), we have only to consider the case where \(d_C(u_i)=3\) for each \(i\in \{1,3,5\}\), and \(d_C(x_2)=4\). Let \(v_i\in N_C(u_1)\) for each \(1\le i\le 3\). Then we may assume \(N_C(u_1)=N_C(u_3)=N_C(u_5)\), otherwise, we get a contradiction by the same arguments as the case where \(d_C(u_1)=4\). Note \(C\) has a chord. Suppose \(v_1v_3\in E(G)\). Then \(C'=u_1,v_1,v_4,v_3,u_1\) is a 4-cycle with chord \(v_1v_3\). Since \(d_C(x_2)=4\), \(v_2\in N_C(u_3)\cap N_C(x_2)\). Then \(comp(H')\le comp(H)-1=2-1=1\) for the new \(H'\), a contradiction. Suppose \(v_2v_4\in E(G)\). Then \(C'=u_1,v_1,v_4,v_2,u_1\) is a 4-cycle with chord \(v_1v_2\). Since \(d_C(x_2)=4\), \(v_3\in N_C(u_3)\cap N_C(x_2)\). Then \(comp(H')\le comp(H)-1=2-1=1\) for the new \(H'\), a contradiction.
Next suppose \(u_1u_s\not\in E(H_1)\). Without loss of generality, we may assume \(d_C(u_1)\ge d_C(u_s)\). Assume \(P_1\) is a Hamiltonian path in \(H_1\). Note \(s\ge 9\) since \(|H_1|\ge 9\). Since \(P_1\) is a Hamiltonian path in \(H_1\), note \(d_{P_1}(u)=d_{H_1}(u)\) for any \(u\in V(P_1)\). We also note \(d_{P_1}(u_i)\le 2\) for each \(i\in \{1,s\}\). Suppose \(d_{P_1}(u_1)=1\). By Lemma 7, \(d_{H_1}(u_i)=2\) for some \(3 \le i\le 5\). Since \(s\ge 9\), \(X_0=\{u_1,u_i,u_s\}\) is an independent set and \(d_{H_1}(X_0)\le 6\). Thus \(X=X_0\cup \{x_2\}\) is an independent set and \(d_{H}(X)\le 8\). Then we get a contradiction by the same arguments as the case where \(u_1u_s\in E(G)\). Next suppose \(d_{P_1}(u_1)=2\). Now assume \(u_1u_3 \in E(H_1)\). By Lemma 7, \(d_{H_1}(u_i)=2\) for some \(4 \le i\le 6\). Since \(s\ge 9\), \(X_0=\{u_1,u_i,u_s\}\) is an independent set and \(d_{H_1}(X_0)\le 6\), and we get a contradiction by considering \(X=X_0\cup \{x_2\}\) similar to the case where \(u_1u_s\in E(H_1)\). Thus \(u_1u_3 \not\in E(H_1)\), that is, \(u_1u_i\in E(H_1)\) for some \(4\le i\le s-1\). By Lemma 6, \(d_{H_1}(u_{i-1})=2\). Since \(s\ge 9\), \(X_0=\{u_1,u_{i-1},u_s\}\) is an independent set and \(d_{H_1}(X_0)\le 6\), and we get a contradiction by considering \(X=X_0\cup \{x_2\}\).
Assume \(P_1\) is not a Hamiltonian path in \(H_1\). Then \(V(H_1-P_1)\ne \emptyset\). Let \(P_2=v_1, \ldots, v_t\,(t\ge 1)\) be a longest path in \(H_1-P_1\). Without loss of generality, we may assume \(d_{H_1}(v_1) \le d_{H_1}(v_t)\). If \(u_1u_s\in E(H_1)\), then since there exists a longer path than \(P_1\), we may assume \(u_1u_s\not\in E(H_1)\). Also we may assume \(d_{H_1}(v_1)\le 2\), otherwise, since \(d_{P_1}(v_i)\ge 1\) for each \(i\in \{1,t\}\) by Lemma 11(iii) and (iv), there exists a cycle in \(\langle P_1\cup P_2 \rangle\) with chord incident to \(v_1\) or \(v_t\), a contradiction. Thus \(X_0=\{u_1,u_s,v_1\}\) is an independent set and \(d_{H_1}(X_0)\le 6\). Then \(X=X_0\cup \{x_2\}\) is an independent set and \(d_H(X)\le 8\). By Subclaim 15, the degree sequences from four vertices of \(X\) to some \(C\) in \(\mathscr{C}\) are \((4,4,4,1)\), \((4,4,3,2)\) or \((4,3,3,3)\), and \(|C|=4\). Let \(C=w_1,w_2,w_3,w_4,w_1\). Since \(d_C(u_1)\ge d_C(u_s)\) by our assumption, \(d_C(u_1)\ge 3\) by the degree sequences. First suppose \(d_C(u_1)=4\). Since \(N_C(v_1) \cap N_C(x_2)\ne \emptyset\) by the degree sequences, without loss of generality, we may assume \(w_4\in N_C(v_1) \cap N_C(x_2)\). Since \(d_C(u_1)=4\), \(w_i\in N_C(u_1)\) for each \(1\le i\le 3\). Then \(C'=u_1,w_1,w_2,w_3,u_1\) is a 4-cycle with chord \(u_1w_2\). Since \(u_1\) is an endpoint of the longest path \(P_1\), \(u_1\) is not a cut-vertex of \(H_1\). Thus \(H_1-u_1\) is connected. Then \(comp(H')\le comp(H)-1=2-1=1\) for the new \(H'\). This contradicts (A2). Suppose \(d_C(u_1)=3\). Then we may assume the degree sequence is \((4,4,3,2)\) or \((4,3,3,3)\). In each degree sequence, it is sufficient to consider \(d_C(u_1)=3\), \(d_C(u_s)=2\), and \(\{d_C(v_1),d_C(x_2)\}=\{3,4\}\). First assume \(d_C(v_1)=3\) and \(d_C(x_2)=4\). Without loss of generality, we may assume \(w_i\in N_C(u_1)\) for each \(1\le i\le 3\). Then \(C'=u_1,w_1,w_2,w_3,u_1\) is a 4-cycle with chord \(u_1w_2\). If \(w_4\in N_C(v_1)\), then \(w_4\in N_C(v_1)\cap N_C(x_2)\) since \(d_C(x_2)=4\). Then \(comp(H')\le comp(H)-1=2-1=1\) for the new \(H'\), a contradiction. Thus \(N_C(u_1)=N_C(v_1)\). Note \(C\) has a chord. Suppose \(w_1w_3\in E(G)\). Then \(C'=u_1,w_1,w_4,w_3,u_1\) is a 4-cycle with chord \(w_1w_3\). Since \(d_C(x_2)=4\), \(w_2\in N_C(v_1)\cap N_C(x_2)\). Then \(comp(H')\le comp(H)-1=2-1=1\) for the new \(H'\), a contradiction. Suppose \(w_2w_4\in E(G)\). Then \(C'=u_1,w_1,w_4,w_2,u_1\) is a 4-cycle with chord \(w_1w_2\). Since \(d_C(x_2)=4\), \(w_3\in N_C(v_1)\cap N_C(x_2)\). Then \(comp(H')\le comp(H)-1=2-1=1\) for the new \(H'\), a contradiction. If \(d_C(v_1)=4\) and \(d_C(x_2)=3\), then we get a contradiction, similarly. ◻
Claim 16. \(H\) contains a Hamiltonian path.
Proof. Suppose not, and let \(P_1=u_1, \ldots, u_s\) be a longest path in \(H\). Note \(s\ge 3\) since \(|H|\ge 18\) and \(H\) is connected by Claim 14. Let \(P_2=v_1, \ldots, v_t\) (\(t\ge 1\)) be a longest path in \(G-P_1\) such that \(d_{P_1}(v_1) \le d_{P_1}(v_t)\). By Lemma 12, there exists an independent set \(X\) of four vertices in \(H\) such that \(\{u_1,u_s,v_1\}\subseteq X\) and \(d_{H}(X)\le 8\). Then the degree sequences from four vertices of \(X\) to some \(C\) in \(\mathscr{C}\) are \((4,4,4,1)\), \((4,4,3,2)\) or \((4,3,3,3)\), and \(|C|=4\). Let \(C=x_1,x_2,x_3,x_4,x_1\). We may assume \(u_1u_s\not\in E(H)\), otherwise, a path longer than \(P_1\) exists, a contradiction. Without loss of generality, we may assume \(d_C(u_1) \ge d_C(u_s)\). By the degree sequences, we have \(d_C(u_1)\ge 3\).
Suppose \(d_C(u_1)=4\). Since \(N_C(u_s) \cap N_C(v_1)\ne \emptyset\) by the degree sequences, without loss of generality, we may assume \(x_4\in N_C(u_s) \cap N_C(v_1)\). Since \(d_C(u_1)=4\), we have \(x_i\in N_C(u_1)\) for each \(1\le i\le 3\). Then \(C'=u_1,x_1,x_2,x_3,u_1\) is a 4-cycle with chord \(u_1x_2\). Since \(u_1\) is an endpoint of the longest path \(P_1\), \(u_1\) is not a cut-vertex of \(H\). Thus \(H-u_1\) is connected. Replacing \(C\) in \(\mathscr{C}\) by \(C'\), we consider the new \(H'\). Then \(P_1[u_2,u_s],x_4,P_2[v_1,v_t]\) is a longer path than \(P_1\) in \(H'\). This contradicts (A3).
Suppose \(d_C(u_1)=3\). Then we may assume the degree sequence is \((4,4,3,2)\) or \((4,3,3,3)\). First assume the degree sequence is \((4,4,3,2)\). Since \(d_C(u_1)\ge d_C(u_s)\), we have \(d_C(u_1)=3\), \(d_C(u_s)=2\) and \(d_C(v_1)=4\). Without loss of generality, we may assume \(x_i\in N_C(u_1)\) for each \(1\le i\le 3\). Then \(C'=u_1,x_1,x_2,x_3,u_1\) is a 4-cycle with chord \(u_1x_2\). Note \(u_1\) is not a cut-vertex of \(H\). If \(x_4\in N_C(u_s)\), then since \(d_C(v_1)=4\), there exists a longer path than \(P_1\) in the new \(H'\), a contradiction. Thus we may assume \(x_4\not\in N_C(u_s)\). Note \(C\) has a chord. Suppose \(x_1x_3\in E(G)\). Assume \(x_2\in N_C(u_s)\). Then \(C'=u_1,x_3,x_4,x_1,u_1\) is a 4-cycle with chord \(x_1x_3\). Since \(d_C(v_1)=4\), \(x_2\in N_C(u_s)\cap N_C(v_1)\), and there exists a longer path than \(P_1\) in the new \(H'\), a contradiction. Thus \(x_2\not\in N_C(u_s)\). Since \(d_C(u_s)=2\), \(x_1,x_3\in N_C(u_s)\). Then \(C'=u_s,x_3,x_4,x_1,u_s\) is a 4-cycle with chord \(x_1x_3\). Note \(u_s\) is not a cut-vertex of \(H\). Since \(d_C(v_1)=4\), \(x_2\in N_C(u_1)\cap N_C(v_1)\). Then \(P_1^-[u_{s-1},u_1],x_2,P_2[v_1,v_t]\) is a longer path than \(P_1\) in the new \(H'\), a contradiction. Suppose \(x_2x_4\in E(G)\). Assume \(x_3\in N_C(u_s)\). Then \(C'=u_1,x_1,x_4,x_2,u_1\) is a 4-cycle with chord \(x_1x_2\). Since \(d_C(v_1)=4\), \(x_3\in N_C(u_s)\cap N_C(v_1)\). Then there exists a longer path than \(P_1\) in the new \(H'\), a contradiction. Thus \(x_3\not\in N_C(u_s)\). By symmetry, \(x_1\not\in N_C(u_s)\). Thus \(d_C(u_s)\le 1\). This contradicts \(d_C(u_s)=2\).
Next assume the degree sequence is \((4,3,3,3)\). Since \(d_C(u_1) \ge d_C(u_s)\) and \(d_C(u_1)=3\) by our assumption, we have \(d_C(u_s)=3\). Thus \(d_C(v_1)\ge 3\). First assume \(d_C(v_1)=4\). Let \(x_i\in N_C(u_1)\) for each \(1\le i\le 3\). Then \(C'=u_1,x_1,x_2,x_3,u_1\) is a 4-cycle with chord \(u_1x_2\). If \(x_4\in N_C(u_s)\), then since \(d_C(v_1)=4\), there exists a longer path than \(P_1\) in the new \(H'\), a contradiction. Thus \(N_C(u_1)=N_C(u_s)\). Suppose \(x_1x_3\in E(G)\). Then \(C'=u_1,x_1,x_4,x_3,u_1\) is a 4-cycle with chord \(x_1x_3\). Since \(d_C(v_1)=4\), \(x_2\in N_C(u_s)\cap N_C(v_1)\). Then there exists a longer path than \(P_1\) in the new \(H'\), a contradiction. Suppose \(x_2x_4\in E(G)\). Then \(C'=u_1,x_1,x_4,x_2,u_1\) is a 4-cycle with chord \(x_1x_2\). Since \(d_C(v_1)=4\), \(x_3\in N_C(u_s)\cap N_C(v_1)\). Then there exists a longer path than \(P_1\) in the new \(H'\), a contradiction.
Next assume \(d_C(v_1)=3\). Recall \(d_C(u_1)=d_C(u_s)=3\). Then \(|N_C(u_s)\cap N_C(v_1)|\ge 2\). Let \(x_i\in N_C(u_1)\) for each \(1\le i\le 3\). Suppose \(x_1x_3\in E(G)\). If \(x_i\in N_C(u_s)\cap N_C(v_1)\) for some \(i\in \{2,4\}\), then there exists a longer path than \(P_1\), a contradiction. Thus \(x_1,x_3\in N_C(u_s)\cap N_C(v_1)\). Suppose \(x_4\in N_C(u_s)\) and \(x_2\in N_C(v_1)\). Then \(C'=u_s,x_4,x_1,x_3,u_s\) is a 4-cycle with chord \(x_3x_4\), and \(P_1^-[u_{s-1},u_1],x_2,P_2[v_1,v_t]\) is a longer path than \(P_1\) in the new \(H'\), a contradiction. Suppose \(x_2\in N_C(u_s)\) and \(x_4\in N_C(v_1)\). Let \(w\in X-\{u_1,u_s,v_1\}\). Since we assume the degree sequence is \((4,3,3,3)\), we have \(d_C(w)=4\). Assume \(w\in V(P_1)\). Then \(P_1[u_1,u_s],x_2,u_1\) is a cycle with chord \(wx_2\), and \(v_1,x_1,x_4,x_3,v_1\) is the other cycle with chord \(x_1x_3\). Thus we have two vertex-disjoint chorded cycles in \(\langle H\cup C\rangle\), and \(G\) contains \(k\) vertex-disjoint chorded cycles, a contradiction. Assume \(w\not\in V(P_1)\). Then \(C'=u_s,x_3,x_4,x_1,u_s\) is a 4-cycle with chord \(x_1x_3\). Since \(d_C(w)=4\), \(w,x_2,P_1[u_1,u_{s-1}]\) is a longer path than \(P_1\) in the new \(H'\), a contradiction. Suppose \(x_2x_4\in E(G)\). Note \(|N_C(u_s)\cap N_C(v_1)|\ge 2\). If \(x_i\in N_C(u_s)\cap N_C(v_1)\) for some \(i\in \{1,3,4\}\), then there exists a longer path than \(P_1\), a contradiction. Thus \(|N_C(u_s)\cap N_C(v_1)|\le 1\), a contradiction. ◻
By Claims 10, 16 and Lemma 10, \(H\) contains an independent set \(X\) of four vertices such that \(d_H(X) \le 8\). By Claim 16 and Lemma 13, \[\begin{aligned} d_G(X)=d_{\mathscr{C}}(X)+d_H(X)\le 12(k-1)+8=12k-4. \end{aligned}\] This contradicts the \(\sigma_4(G)\) condition. This completes the proof of Theorem 5. 0◻
The authors would like to thank referees for valuable suggestions and comments. The first author is supported by the Heilbrun Distinguished Emeritus Fellowship from Emory University. The second author is supported by JSPS KAKENHI Grant Number JP19K03610.