On Vertex-Disjoint Chorded Cycles and Degree Sum Conditions

Gould, Ronald; Hirohata, Kazuhide; Rorabaugh, Ariel

doi:10.61091/jcmcc120-07

Abstract

1. Introduction
2. Preliminaries
3. Lemmas
4. Proof of Theorem 4
5. Proof of Theorem 5
Acknowledgments

References

Journal of Combinatorial Mathematics and Combinatorial Computing

Volume 120
Pages: 75-90

Research article

On Vertex-Disjoint Chorded Cycles and Degree Sum Conditions

^¹, ^², ^³

¹Department of Mathematics, Emory University, Atlanta, GA 30322 USA.

²Department of Industrial Engineering, Computer Science, National Institute of Technology, Ibaraki College, Hitachinaka, Ibaraki 312-8508 Japan.

³Department of Electrical Engineering and Computer Science, University of Tennessee, Knoxville, TN 37996 USA.

Received: 10/09/2019
Accepted: 20/12/2020
Published: 30/06/2024

Copyright Link
License

Abstract

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 $σ_{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 $11 k + 7$ and $σ_{4} (G) \geq 12 k - 3$ with $k \geq 1$ ,
then $G$ contains $k$ vertex-disjoint chorded cycles.
We also show that the degree sum condition on $σ_{4} (G)$ is sharp.

Keywords: vertex-disjoint chorded cycles, minimum degree sum, degree sequence

1. Introduction

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 | \geq 3 k$ and the minimum degree $δ (G) \geq 2 k$ , then $G$ contains $k$ vertex-disjoint cycles. For an integer $t \geq 1$ , let $σ_{t} (G) = min {\sum_{v \in X} d_{G} (v) : \begin{matrix} X i s a n i n d e p e n d e n t v e r t e x s e t o f G w i t h | X | = t . \end{matrix}},$ and $σ_{t} (G) = \infty$ when the independence number $α (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 | \geq 3 k$ and $σ_{2} (G) \geq 4 k - 1$ , then $G$ contains $k$ vertex-disjoint cycles. In 2006, Fujita et al. [4] proved that if $| G | \geq 3 k + 2$ and $σ_{3} (G) \geq 6 k - 2$ , then $G$ contains $k$ vertex-disjoint cycles, and in [5], this result was extended to $σ_{4} (G) \geq 8 k - 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 \geq 1$ be an integer. If $G$ is a graph of order at least $4 k$ and $δ (G) \geq 3 k$ , then $G$ contains $k$ vertex-disjoint chorded cycles.

In 2010, Chiba et al. proved Theorem 2. Since $σ_{2} (G) \geq 2 δ (G)$ , Theorem 2 is stronger than Theorem 1.

Theorem 2 (Chiba, Fujita, Gao, Li [7]). Let $k \geq 1$ be an integer. If $G$ is a graph of order at least 4k and $σ_{2} (G) \geq 6 k - 1$ , then $G$ contains $k$ vertex-disjoint chorded cycles.

Recently, Theorem 2 was extended as follows. Since $σ_{3} (G) \geq 3 σ_{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 \geq 1$ be an integer. If $G$ is a graph of order at least $8 k + 5$ and $σ_{3} (G) \geq 9 k - 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 | \geq 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 $σ_{4} (G)$ . In particular, we first show the following.

Theorem 4. If $G$ is a graph of order at least $15$ and $σ_{4} (G) \geq 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 $σ_{4} (G)$ condition in Theorem 4. However, $G$ does not contain a chorded cycle. Thus $| G | \geq 15$ is necessary.

Figure 1. The Graph of G of Order 14. The White Vertex (o) shows Degree 2, and the Black Vertex (o) shows Degree 3

Theorem 5. Let $k \geq 1$ be an integer. If $G$ is a graph of order $n \geq 11 k + 7$ and $σ_{4} (G) \geq 12 k - 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_{3 k - 1, n - 3 k + 1}$ , where large $n = | G |$ . Then $σ_{4} (G) = 4 (3 k - 1) = 12 k - 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 $3 k - 1$ partite set. Thus $σ_{4} (G) \geq 12 k - 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 $⟨ X ⟩$ . Let $G - X = ⟨ V (G) - X ⟩$ and $G - H = ⟨ V (G) - V (H) ⟩$ . 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}, \dots, 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 \geq 1$ and two vertex-disjoint subgraphs $A, B$ of $G$ , we denote by $(d_{1}, d_{2}, \dots, d_{r})$ a degree sequence from $A$ to $B$ such that $d_{B} (v_{i}) \geq d_{i}$ and $v_{i} \in V (A)$ for each $1 \leq i \leq 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}, \dots, d_{r})$ , we assume $d_{B} (v_{i}) = d_{i}$ for each $1 \leq i \leq 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$ , $c o m p (G)$ is the number of components of $G$ . A cycle of length $ℓ$ is called a $ℓ$ -cycle. For terminology and notation not defined here, see [13].

2. Preliminaries

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_{i} v_{j}$ , $i < j$ . We say a chord $v v^{'} \neq v_{i} v_{j}$ is parallel to $v_{i} v_{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_{i} v_{j}$ and $u_{ℓ} 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_{i} v_{j}$ and $u_{ℓ} v_{m}$ are parallel if either $i \leq ℓ$ and $j \leq m$ , or $ℓ \leq i$ and $m \leq 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_{i} v_{j}$ and $v_{ℓ} v_{m}$ be two distinct edges between vertices of a path $P = v_{1}, \dots, v_{t}$ , with $j \geq i + 2$ and $m \geq ℓ + 2$ . We say $v_{i} v_{j}$ and $v_{ℓ} v_{m}$ are nested if either $i \leq ℓ < m \leq j$ or $ℓ \leq i < j \leq 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_{i} v_{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_{i} v_{j}$ for some $j > i + 1$ , that is not an edge of the path.

3. Lemmas

The following lemmas will be needed.

Lemma 1 ([8]). Let $r \geq 1$ be an integer, and let $C = {C_{1}, \dots, C_{r}}$ be a minimal set of $r$ vertex-disjoint chorded cycles in a graph $G$ . If $| C_{i} | \geq 7$ for some $1 \leq i \leq 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 \geq 1$ be an integer, and let $C = {C_{1}, \dots, C_{r}}$ be a minimal set of $r$ vertex-disjoint chorded cycles in a graph $G$ . Then $d_{C_{i}} (x) \leq 4$ for any $1 \leq i \leq r$ and any $x \in V (G) - \cup_{i = 1}^{r} V (C_{i})$ . Furthermore, for some $C \in 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 | \leq 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 $⟨ P_{1} \cup P_{2} ⟩$ .

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} | \geq 7$ . Then there exists a chorded cycle in $⟨ P_{1} \cup P_{2} ⟩$ not containing at least one vertex of $⟨ P_{1} \cup P_{2} ⟩$ .

Lemma 5 ([8]). Let $P_{1}, P_{2}$ be two vertex-disjoint paths, and let $u_{1}, u_{2}$ $(u_{1} \neq u_{2})$ be in that order on $P_{1}$ . Suppose $d_{P_{2}} (u_{i}) \geq 2$ for each $i \in {1, 2}$ . Then there exists a chorded cycle in $⟨ P_{1} [u_{1}, u_{2}] \cup P_{2} ⟩$ .

Lemma 6 ([8]). Let $H$ be a graph containing a path $P = v_{1}, \dots, v_{t}$ $(t \geq 3)$ , and not containing a chorded cycle. If $v_{1} v_{i} \in E (H)$ for some $i \geq 3$ , then $d_{P} (v_{j}) \leq 3$ for any $j \leq i - 1$ and in particular, $d_{P} (v_{i - 1}) = 2$ . And if $v_{t} v_{i} \in E (H)$ for some $i \leq t - 2$ , then $d_{P} (v_{j}) \leq 3$ for any $j \geq 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 \geq 6)$ , and not containing a chorded cycle. If $d_{P} (v_{1}) = 1$ , then $d_{P} (v_{i}) = 2$ for some $3 \leq i \leq 5$ , and if $v_{1} v_{3} \in E (H)$ , then $d_{P} (v_{i}) = 2$ for some $4 \leq i \leq 6$ .

Lemma 8 ([8]). Let $H$ be a graph containing a path $P = v_{1}, \dots, v_{t}$ $(t \geq 6)$ , and not containing a chorded cycle. If $d_{P} (v_{t}) = 1$ , then $d_{P} (v_{i}) = 2$ for some $t - 4 \leq i \leq t - 2$ , and if $v_{t} v_{t - 2} \in E (H)$ , then $d_{P} (v_{i}) = 2$ for some $t - 5 \leq i \leq 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 = ⟨ P_{1} \cup P_{2} ⟩$ , where $P_{1} = u_{1}, \dots, u_{s}$ $(s \geq 5)$ is a longest path in $H$ and $P_{2} = v_{1}, \dots, v_{t}$ $(t \geq 1)$ is a longest path in $H - P_{1}$ . If $u_{i} \in V (P_{1})$ for some $2 \leq i \leq s - 3$ is adjacent to an endpoint $v$ of $P_{2}$ and $u_{j} \in V (P_{1})$ for some $i + 2 \leq j \leq s - 1$ is adjacent to an endpoint $v^{'}$ of $P_{2}$ $($ possibly, $v = v^{'}$ $)$ , then $d_{H} (u_{ℓ}) = 2$ for some $ℓ \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_{ℓ}) \geq 3$ for each $ℓ \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_{i} v_{1}, u_{j} v_{t} \in E (H)$ , $N_{P_{2}} (u_{ℓ}) = \emptyset$ for each $ℓ \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_{ℓ}) = \emptyset$ for each $ℓ \in {i + 1, j - 1}$ . Since $d_{H} (u_{ℓ}) \geq 3$ for each $ℓ \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_{i} u_{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) \leq 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 \geq 3)$ be a longest path in $H$ , and let $P_{2} = v_{1}, \dots, v_{t}$ $(t \geq 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}) \leq 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}) \leq 2$ for each $j \in {1, t}$ .
(v) $d_{P_{i}} (z) \leq 2$ for each $z \in V (H) - V (P_{i})$ and each $i \in {1, 2}$ .
(vi) $d_{P_{1}} ({v_{1}, v_{t}}) \leq 3$ for each $t \geq 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}}) \geq 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 \geq 3)$ be a longest path in $H$ , and let $P_{2} = v_{1}, \dots, v_{t}$ $(t \geq 1)$ be a longest path in $H - P_{1}$ such that $d_{P_{1}} (v_{1}) \leq 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) \leq 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 | \geq 15$ is necessary.

Proof. Suppose $u_{1} u_{s} \in E (H)$ . Since $H$ is connected and $V (H - P_{1}) \neq \emptyset$ , there exists a longer path than $P_{1}$ , a contradiction. Thus $u_{1} u_{s} \notin 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}) \leq 2$ by Lemma 11(v). If $t \geq 2$ , then $d_{P_{1}} ({v_{1}, v_{t}}) \leq 3$ by Lemma 11(vi). Then $d_{P_{1}} (v_{1}) \leq 1$ by the assumption ( $d_{P_{1}} (v_{1}) \leq d_{P_{1}} (v_{t})$ ), and $d_{P_{1}} (v_{t}) \leq 2$ by Lemma 11(v).

Claim 6. If $| P_{2} | \leq 3$ , then $H = ⟨ P_{1} \cup P_{2} ⟩$ .

Proof. Suppose $H \neq ⟨ P_{1} \cup P_{2} ⟩$ . 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} | \leq 2$ , then the subclaim holds. Thus we may assume $| P_{2} | = 3$ . Suppose $N_{R} (v^{'}) \neq \emptyset$ for some $v^{'} \in V (P_{2})$ . Then $v^{'} = v_{2}$ . Let $w_{1} \in N_{R} (v_{2})$ . If $v_{1} v_{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_{1} v_{3} \notin E (H)$ . Since $d_{P_{1}} (v_{1}) \leq 1$ and $d_{P_{1}} (v_{3}) \leq 2$ , we have $d_{H} (v_{1}) \leq 2$ and $d_{H} (v_{3}) \leq 3$ . Suppose a vertex on $P_{2}$ has a neighbor $w_{1}$ in $R$ . Then $v_{2} w_{1} \in E (H)$ . Recall $u_{1} u_{s} \notin E (H)$ , and note $u_{i} v_{j} \notin 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}) \leq 2$ for any $i \in {1, s}$ by Lemma 11(ii). If $d_{H} ({v_{1}, v_{3}}) \leq 4$ , then $X = {u_{1}, u_{s}, v_{1}, v_{3}}$ is an independent set in $H$ and $d_{H} (X) \leq 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}) \leq 2$ , then $X = {u_{1}, u_{s}, v_{1}, w_{1}}$ is the desired set. Thus $d_{H} (w_{1}) \geq 3$ , that is, $d_{P_{1}} (w_{1}) \geq 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 $⟨ P_{1} \cup P ⟩$ , a contradiction.

Subclaim 8. For any $u \in V (P_{1})$ , $N_{R} (u) = \emptyset$ .

Proof. We first prove $d_{H} (v_{1}) \leq 2$ . Suppose not, that is, $d_{H} (v_{1}) \geq 3$ . Recall $d_{P_{1}} (v_{1}) \leq 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_{1} v_{3} \in E (H)$ . Since $d_{P_{1}} (v_{1}) \leq d_{P_{1}} (v_{3})$ by the assumption, $d_{P_{1}} (v_{3}) \geq 1$ . Then $⟨ P_{1} \cup P_{2} ⟩$ contains a cycle with chord $v_{1} v_{3}$ , a contradiction. Thus $d_{H} (v_{1}) \leq 2$ . Suppose there exists a vertex in $P_{1}$ with a neighbor $w_{1}$ in $R$ . If $d_{H} (w_{1}) \leq 2$ , then $X = {u_{1}, u_{s}, v_{1}, w_{1}}$ is the desired set. Thus $d_{H} (w_{1}) \geq 3$ .

First suppose $d_{P_{1}} (w_{1}) \geq 2$ . Then $d_{P_{1}} (w_{1}) = 2$ by Lemma 11(v), and $d_{R} (w_{1}) \geq 1$ by Subclaim 7. Let $w_{2} \in N_{R} (w_{1})$ . If $d_{H} (w_{2}) \leq 2$ , then $X = {u_{1}, u_{s}, v_{1}, w_{2}}$ is the desired set. Thus $d_{H} (w_{2}) \geq 3$ . If $d_{P_{1}} (w_{2}) \geq 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 $⟨ P_{1} \cup P ⟩$ , a contradiction. Thus $d_{P_{1}} (w_{2}) \leq 1$ , and by Subclaim 7, $d_{R} (w_{2}) \geq 2$ . Let $w_{3} \in N_{R - w_{1}} (w_{2})$ . If $d_{H} (w_{3}) \leq 2$ , then $X = {u_{1}, u_{s}, v_{1}, w_{3}}$ is the desired set. Thus $d_{H} (w_{3}) \geq 3$ . Suppose $d_{P_{1}} (w_{3}) \geq 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 $⟨ P_{1} \cup P ⟩$ by Lemma 5, a contradiction. Thus $d_{P_{1}} (w_{3}) \leq 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 $⟨ P_{1} \cup P ⟩$ contains a cycle with chord $w_{1} w_{3}$ , a contradiction.

Next suppose $d_{P_{1}} (w_{1}) = 1$ . Then $d_{R} (w_{1}) \geq 2$ by Subclaim 7. Let $w_{2}, w_{3} \in N_{R} (w_{1})$ . If $d_{H} (w_{i}) \leq 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}) \geq 3$ for each $i \in {2, 3}$ . Suppose $d_{R} (w_{i}) \geq 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}) \leq 2$ , and then $d_{P_{1}} (w_{i}) \geq 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_{2} w_{3} \in E (H)$ . Let $P = w_{2}, w_{1}, w_{3}$ . Since $d_{P_{1}} (w_{i}) \geq 1$ for each $i \in {2, 3}$ , there exists a cycle with chord $w_{2} w_{3}$ in $⟨ P_{1} \cup P ⟩$ , a contradiction. Thus $d_{R} (w_{i}) \leq 1$ for each $i \in {2, 3}$ , and then $d_{P_{1}} (w_{i}) \geq 2$ by Subclaim 7. By Lemma 5, a chorded cycle exists in $⟨ P_{1} \cup P ⟩$ , 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}) \geq 1$ .

Proof. Suppose $d_{P_{1}} (v_{t}) = 0$ . By the assumption ( $d_{P_{1}} (v_{1}) \leq d_{P_{1}} (v_{t})$ ), we have $d_{P_{1}} (v_{1}) = 0$ . Then we may assume $| P_{2} | = t \geq 3$ , otherwise, we get a contradiction by Claim 6 and the connectedness of $H$ . Recall $u_{1} u_{s} \notin E (H)$ . By Lemmas 11(iii) and (iv), $d_{H} (v_{j}) \leq 2$ for each $j \in {1, t}$ . If $v_{1} v_{t} \notin E (H)$ , then $X = {u_{1}, u_{s}, v_{1}, v_{t}}$ is the desired set. Thus $v_{1} v_{t} \in E (H)$ .

First suppose $| P_{2} | = t = 3$ . By Claim 6, $H = ⟨ P_{1} \cup P_{2} ⟩$ . Since $v_{1} v_{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 \geq 4$ . Recall $u_{1} u_{s} \notin E (H)$ and $v_{1} v_{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}) \leq 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 = ⟨ P_{1} \cup P_{2} ⟩$ . Since $| H | \geq 15$ , $| P_{1} | \geq 14$ . Recall $d_{P_{1}} (v_{1}) \leq 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 \geq 2$ and $j \leq s - 1$ by Lemma 11(i). If $j = i + 1$ , then $H$ contains a Hamiltonian path, a contradiction. Thus $j \geq i + 2$ . By Lemma 9, $d_{H} (u_{ℓ}) = 2$ for some $ℓ \in {i + 1, j - 1}$ . Note $u_{ℓ} u_{1}, u_{ℓ} u_{s} \notin E (H)$ . Then $X = {u_{1}, u_{ℓ}, u_{s}, v_{1}}$ is the desired set.

Next suppose $d_{P_{1}} (v_{1}) = 1$ . Note $d_{P_{1}} (u_{1}) \leq 2$ . Assume $u_{1} u_{i} \in E (H)$ for some $4 \leq i \leq s - 1$ . By Lemma 6, $d_{P_{1}} (u_{i - 1}) = 2$ . If $v_{1} u_{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_{1} u_{i - 1} \notin 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_{1} u_{3} \in E (H)$ . Then $d_{P_{1}} (u_{i}) = 2$ for some $3 \leq i \leq 6$ by Lemma 7. Similarly, either $d_{P_{1}} (u_{s}) = 1$ or $u_{s} u_{s - 2} \in E (H)$ by symmetry. Then $d_{P_{1}} (u_{j}) = 2$ for some $s - 5 \leq j \leq s - 2$ by Lemma 8. Note $| P_{1} | = s \geq 14$ . Since $d_{P_{1}} (v_{1}) = 1$ by our assumption, $v_{1} u_{ℓ} \notin E (H)$ for some $ℓ \in {i, j}$ , and $d_{H} (u_{ℓ}) = 2$ . Thus $X = {u_{1}, u_{ℓ}, u_{s}, v_{1}}$ is the desired set.

Case 2. Suppose $| P_{2} | = t \in {2, 3}$ .

By Claim 6, $H = ⟨ P_{1} \cup P_{2} ⟩$ . Recall $d_{P_{1}} ({v_{1}, v_{t}}) \leq 3$ , $d_{P_{1}} (v_{1}) \leq 1$ , and $d_{P_{1}} (v_{t}) \leq 2$ . We also note $d_{P_{1}} ({v_{1}, v_{t}}) \geq 1$ by Claim 9. Since $| H | \geq 15$ , $| P_{1} | = s \geq 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 \geq i + 2$ . Note $i \geq 2$ and $j \leq s - 1$ by Lemma 11(i). By Lemma 9, $d_{H} (u_{ℓ}) = 2$ for some $ℓ \in {i + 1, j - 1}$ . Note $u_{ℓ} u_{1} \notin E (H)$ and $u_{ℓ} u_{s} \notin E (H)$ . If $d_{H} (v_{1}) \leq 2$ , then $X = {u_{1}, u_{ℓ}, u_{s}, v_{1}}$ is the desired set. Thus we may assume that $d_{H} (v_{1}) \geq 3$ . Since $d_{P_{1}} (v_{1}) \leq 1$ and $d_{P_{2}} (v_{1}) \leq 2$ , we have $d_{P_{1}} (v_{1}) = 1$ and $d_{P_{2}} (v_{1}) = 2$ . Then $t = 3$ and $v_{1} v_{3} \in E (H)$ . Since $d_{P_{1}} (v_{1}) \leq d_{P_{1}} (v_{t}) = d_{P_{1}} (v_{3})$ by the assumption, we have $d_{P_{1}} (v_{3}) \geq 1$ . Thus $⟨ P_{1} \cup P_{2} ⟩$ contains a cycle with chord $v_{1} v_{3}$ , a contradiction.

Next suppose $| N_{P_{1}} ({v_{1}, v_{t}}) | = 1$ . Assume $u_{1} u_{i} \in E (H)$ for some $4 \leq i \leq 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}) \leq 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}) \geq 3$ . Then $d_{P_{1}} (v_{1}) = 1$ , and $d_{P_{2}} (v_{1}) = 2$ , that is, $t = 3$ and $v_{1} v_{3} \in E (H)$ . Also, $d_{P_{1}} (v_{3}) \geq 1$ . Thus $⟨ P_{1} \cup P_{2} ⟩$ contains a cycle with chord $v_{1} v_{3}$ , a contradiction. Hence, either $d_{P_{1}} (u_{1}) = 1$ or $u_{1} u_{3} \in E (H)$ . Then $d_{P_{1}} (u_{i}) = 2$ for some $3 \leq i \leq 6$ by Lemma 7. Similarly, either $d_{P_{1}} (u_{s}) = 1$ or $u_{s} u_{s - 2} \in E (H)$ by symmetry. Then $d_{P_{1}} (u_{j}) = 2$ for some $s - 5 \leq j \leq s - 2$ by Lemma 8. Since $| N_{P_{1}} ({v_{1}, v_{t}}) | = 1$ by our assumption, $u_{ℓ} \notin N_{P_{1}} ({v_{1}, v_{t}})$ for some $ℓ \in {i, j}$ . Suppose $t = 2$ . Then $d_{H} (v_{1}) \leq 2$ and $d_{H} (u_{ℓ}) = d_{P_{1}} (u_{ℓ}) = 2$ . Thus $X = {u_{1}, u_{ℓ}, u_{s}, v_{1}}$ is the desired set. Hence $t = 3$ . If $v_{1} v_{3} \notin E (H)$ , then $d_{H} (v_{1}) \leq 2$ and $d_{H} (v_{3}) \leq 2$ . Thus $X = {u_{1}, u_{s}, v_{1}, v_{3}}$ is the desired set. Hence we may assume that $v_{1} v_{3} \in E (H)$ . Note $d_{P_{1}} (v_{1}) \leq 1$ . Suppose $d_{P_{1}} (v_{1}) = 1$ . Since $d_{P_{1}} (v_{3}) \geq 1$ , $⟨ P_{1} \cup P_{2} ⟩$ contains a cycle with chord $v_{1} v_{3}$ , a contradiction. Suppose $d_{P_{1}} (v_{1}) = 0$ . Then $d_{H} (v_{1}) = 2$ . If $d_{H} (u_{ℓ}) = 2$ , then $X = {u_{1}, u_{ℓ}, u_{s}, v_{1}}$ is the desired set. Thus we may assume that $d_{H} (u_{ℓ}) \geq 3$ . Then $u_{ℓ} v_{2} \in E (H)$ . Since $d_{P_{1}} (v_{3}) \geq 1$ , $⟨ P_{1} \cup P_{2} ⟩$ contains a cycle with chord $v_{2} v_{3}$ , a contradiction.

Case 3. Suppose $| P_{2} | = t \geq 4$ .

Recall $d_{P_{1}} (v_{1}) \leq 1$ and $d_{P_{1}} (v_{t}) \leq 2$ . We consider two subcases as follows.

Subcase 1. Suppose $d_{P_{1}} (v_{1}) = 1$ .

By Claim 9, $d_{P_{1}} (v_{t}) \geq 1$ . Then $d_{P_{2}} (v_{1}) = d_{P_{2}} (v_{t}) = 1$ , otherwise, there exists a cycle in $⟨ P_{1} \cup P_{2} ⟩$ 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}) \geq 3$ . If $d_{P_{2}} (v_{t - 1}) \geq 3$ , then there exists a cycle in $⟨ P_{1} \cup P_{2} ⟩$ 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}) \neq \emptyset$ or $N_{R} (v_{t - 1}) \neq \emptyset$ .

First suppose $N_{P_{1}} (v_{t - 1}) \neq \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 $⟨ P_{1} \cup P_{2} ⟩$ , a contradiction. Thus $N_{P_{1} (u_{i}, u_{j})} (v_{ℓ}) \neq \emptyset$ for each $ℓ \in {1, t - 1}$ . Then we again have three parallel edges or three crossing edges, and by Lemma 3, a chorded cycle exists in $⟨ P_{1} \cup P_{2} ⟩$ , a contradiction.

Next suppose $N_{R} (v_{t - 1}) \neq \emptyset$ . Let $w \in N_{R} (v_{t - 1})$ . If $d_{H} (w) \leq 2$ , then $X = {u_{1}, u_{s}, v_{1}, w}$ is the desired set. Thus $d_{H} (w) \geq 3$ . Then $d_{P_{1}} (w) \leq 1$ , otherwise, since $d_{P_{1}} (v_{t}) = 2$ , there exists a chorded cycle in $⟨ P_{1} \cup P_{2} ⟩$ 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 \leq q$ . By Lemma 11(iii), $w v_{1}, w v_{t} \notin E (H)$ . Thus $w v_{ℓ} \in E (H)$ for some $2 \leq ℓ \leq 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 $w v_{ℓ}$ , a contradiction.

Subcase 2. Suppose $d_{P_{1}} (v_{1}) = 0$ .

Suppose $v_{1} v_{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_{1} u_{s} \notin E (H)$ . Then $X = {u_{1}, u_{s}, v_{1}, v_{t - 1}}$ is the desired set. Thus $v_{1} v_{t} \notin E (H)$ . If $d_{H} (v_{t}) \leq 2$ , then $X = {u_{1}, u_{s}, v_{1}, v_{t}}$ is the desired set. Thus $d_{H} (v_{t}) \geq 3$ . By Lemma 11(iii), (iv), and (v), we have $d_{H} (v_{t}) \leq 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 \geq 2$ and $j \leq s - 1$ by Lemma 11(i), and $| P_{1} | \geq | P_{2} | \geq 4$ . If $j = i + 1$ , then there exists a longer path than $P_{1}$ , a contradiction. Thus $j \geq i + 2$ . Therefore, $| P_{1} | \geq 5$ . If $d_{H} (u_{ℓ}) = 2$ for some $ℓ \in {i + 1, j - 1}$ , then $X = {u_{1}, u_{ℓ}, u_{s}, v_{1}}$ is the desired set. Thus $d_{H} (u_{ℓ}) \geq 3$ for each $ℓ \in {i + 1, j - 1}$ . By Lemma 9, we may assume $H \neq ⟨ P_{1} \cup P_{2} ⟩$ . Now we claim $N_{R} (u_{ℓ}) \neq \emptyset$ for some $ℓ \in {i + 1, j - 1}$ . Assume not. Note $N_{P_{2}} (u_{ℓ}) = \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_{i} u_{i + 1}$ (and $u_{j - 1} u_{j}$ ), a contradiction. Thus the claim holds. If $j \geq i + 3$ , then we may assume $ℓ = j - 1$ , that is, $N_{R} (u_{j - 1}) \neq \emptyset$ , otherwise, consider $P^{-} [u_{s}, u_{1}]$ . Let $w_{1} \in N_{R} (u_{j - 1})$ , and let $P_{3} = w_{1}, \dots, w_{p} (p \geq 1)$ be a longest path starting from $w_{1}$ in $R$ . If $d_{H} (w_{p}) \leq 2$ , then $X = {u_{1}, u_{s}, v_{1}, w_{p}}$ is the desired set. Thus $d_{H} (w_{p}) \geq 3$ . If $N_{P_{2}} (w) \neq \emptyset$ for some $w \in V (P_{3})$ , that is, $v_{ℓ} \in N_{P_{2}} (w)$ for some $1 \leq ℓ \leq t$ , then $P_{1} [u_{1}, u_{j - 1}], w_{1}, P_{3} [w_{1}, w], v_{ℓ}, P_{2} [v_{ℓ}, 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}) \geq 3$ , $d_{P_{1}} (w_{1}) \geq 3$ . This contradicts Lemma 11(v). Suppose $| P_{3} | = p = 2$ . Then $d_{H} (w_{2}) \geq 3$ , and by Lemma 11(v), $d_{P_{1}} (w_{2}) = 2$ . If $u_{ℓ} \in N_{P_{1}} (w_{2})$ for some $j \leq ℓ \leq s$ , then $P_{1} [u_{i}, u_{j - 1}], w_{1}, P_{3} [w_{1}, w_{2}], u_{ℓ}, P_{1}^{-} [u_{ℓ}, u_{j}], v_{t}, u_{i}$ is a cycle with chord $u_{j - 1} u_{j}$ , a contradiction. Thus $u_{ℓ}, u_{ℓ^{'}} \in N_{P_{1}} (w_{2})$ for some $1 \leq ℓ < ℓ^{'} \leq j - 1$ . Then $P_{1} [u_{ℓ}, u_{j - 1}], w_{1}, P_{3} [w_{1}, w_{2}], u_{ℓ}$ is a cycle with chord $w_{2} u_{ℓ^{'}}$ , a contradiction. Suppose $| P_{3} | = p \geq 3$ . Then $d_{P_{3}} (w_{p}) \leq 2$ . Assume $d_{P_{3}} (w_{p}) = 2$ . Since $d_{P_{1}} (w_{p}) \geq 1$ , there exists a cycle in $⟨ P_{1} \cup P_{3} ⟩$ 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 $⟨ P_{1} \cup P_{3} ⟩$ 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 \leq i \leq s$ . Note $i \notin {1, s}$ by Lemma 11(i). Since $d_{H} (v_{t}) \geq 3$ , $d_{P_{2}} (v_{t}) = 2$ by Lemmas 11(iii) and (iv). Let $v_{ℓ} \in N_{P_{2}} (v_{t})$ with $ℓ \leq t - 2$ . Now we consider the path $P_{2}^{'} = P_{2} [v_{1}, v_{ℓ}], v_{t}, P_{2}^{-} [v_{t}, v_{ℓ + 1}]$ . Then $v_{ℓ + 1}$ can be regarded as an endpoint of $P_{2}^{'}$ . Since $d_{P_{1}} (v_{t}) = 1$ , we may assume $d_{P_{1}} (v_{ℓ + 1}) = 1$ . Let $u_{j} \in N_{P_{1}} (v_{ℓ + 1})$ with $1 \leq j \leq s$ . Note $j \notin {1, s}$ by Lemma 11(i). Then we may assume $j \leq i$ , otherwise, consider $P^{-} [u_{s}, u_{1}]$ . Suppose $ℓ = t - 2$ , that is, $v_{t} v_{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 $ℓ \leq t - 3$ . If $j = i - 1$ , then there exists a longer path than $P_{1}$ , a contradiction.

Suppose $j = i$ . Recall $v_{t} v_{ℓ} \in E (H)$ with $ℓ \leq 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}) \geq 3$ . Assume $u_{j} \in N_{P_{1}} (v_{t - 1})$ for some $1 \leq j \leq s$ . We may assume $j \leq i$ , otherwise, consider $P^{-} [u_{s}, u_{1}]$ . Then $P_{1} [u_{j}, u_{i}], v_{t}, P_{2} [v_{ℓ}, v_{t - 1}], u_{j}$ is a cycle with chord $v_{t - 1} v_{t}$ , a contradiction. Assume $v_{ℓ^{'}} \in N_{P_{2}} (v_{t - 1})$ for some $ℓ^{'} \leq t - 3$ . Since $v_{t} v_{ℓ} \in E (H)$ , we may assume $ℓ^{'} < ℓ$ . Then $P_{2} [v_{ℓ^{'}}, v_{ℓ}], v_{t}, u_{i}, P_{2} [v_{ℓ + 1}, v_{t - 1}], v_{ℓ^{'}}$ is a cycle with chord $v_{ℓ} v_{ℓ + 1}$ (and $v_{t - 1} v_{t}$ ), a contradiction. Assume $N_{R} (v_{t - 1}) \neq \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 \leq j \leq s$ . We may assume $j \leq i$ . Then $P_{2} [v_{ℓ}, v_{t - 1}], w, P_{1} [u_{j}, u_{i}], v_{t}, v_{ℓ}$ is a cycle with chord $v_{t - 1} v_{t}$ , a contradiction.

Suppose $j \leq 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}) \geq 3$ for each $h \in {j + 1, i - 1}$ . Now we claim $N_{R} (u_{h}) \neq \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_{ℓ + 1}, P_{2} [v_{ℓ + 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_{j} u_{j + 1}$ (and $u_{i - 1} u_{i}$ ), a contradiction. Thus the claim holds. We also note that if $j \leq i - 3$ , then we may assume $N_{R} (u_{i - 1}) \neq \emptyset$ , otherwise, consider $P^{-} [u_{s}, u_{1}]$ . Let $w_{1} \in N_{R} (u_{i - 1})$ , and let $P_{3} = w_{1}, \dots, w_{p} (p \geq 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 \geq 2$ be an integer, and let $G$ be a graph. Suppose $G$ does not contain $k$ vertex-disjoint chorded cycles. Let $C = {C_{1}, \dots, C_{k - 1}}$ be a minimal set of $k - 1$ vertex-disjoint chorded cycles in $G$ , and let $H = G - C$ and $X \subseteq V (H)$ with $| X | = 4$ . Suppose $H$ contains a Hamiltonian path. Then $d_{C_{i}} (X) \leq 12$ for each $1 \leq i \leq k - 1$ .

4. Proof of Theorem 4

Suppose $G$ does not contain a chorded cycle.

Claim 10. $G$ is connected.

Proof. Suppose not, then $c o m p (G) \geq 2$ . Let $G_{1}, G_{2}, \dots, G_{c o m p (G)}$ be the components of $G$ .

First suppose $c o m p (G) \geq 4$ . By Theorem 1, there exists $x_{i} \in V (G_{i})$ for each $1 \leq i \leq 4$ such that $d_{G_{i}} (x_{i}) \leq 2$ . Let $X = {x_{1}, x_{2}, x_{3}, x_{4}}$ . Then $X$ is an independent set with $d_{G} (X) \leq 8$ . This contradicts the $σ_{4} (G)$ condition.

Next suppose $c o m p (G) = 3$ . Let $| G_{1} | \geq | G_{2} | \geq | G_{3} |$ . Since $| G | \geq 15$ by the assumption, we have $| G_{1} | \geq 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}}) \leq 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}) \leq 2$ . Then $X = {x_{0}, x_{1}, x_{2}, x_{3}}$ is an independent set with $d_{G} (X) \leq 8$ , a contradiction.

Finally, suppose $c o m p (G) = 2$ . Let $| G_{1} | \geq | G_{2} |$ . Since $| G | \geq 15$ , $| G_{1} | \geq 8$ . By Theorem 3 (Remark 1), $G_{1}$ contains an independent set $X_{0}$ of three vertices with $d_{G_{1}} (X_{0}) \leq 6$ . Also, by Theorem 1, there exists $x \in V (G_{2})$ such that $d_{G_{2}} (x) \leq 2$ . Then $X = X_{0} \cup {x}$ is an independent set with $d_{G} (X) \leq 8$ , a contradiction.

Let $P_{1} = u_{1}, \dots, u_{s}$ be a longest path in $G$ . Note $s \geq 3$ , since $| G | \geq 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}) \neq \emptyset$ . Let $P_{2} = v_{1}, \dots, v_{t}$ ( $t \geq 1$ ) be a longest path in $G - P_{1}$ such that $d_{P_{1}} (v_{1}) \leq d_{P_{1}} (v_{t})$ . By Lemma 12, there exists an independent set $X$ of four vertices in $G$ such that $d_{G} (X) \leq 8$ . This contradicts the $σ_{4} (G)$ condition.

Since $| G | \geq 15$ , by Claim 11 and Lemma 10, there exists an independent set $X$ of four vertices in $G$ such that $d_{G} (X) \leq 8$ , a contradiction. This completes the proof of Theorem 4. 0

5. Proof of Theorem 5

By Theorem 4, we may assume $k \geq 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 $x y \notin E (G)$ for some $x, y \in V (G)$ , and define $G^{'} = G + x y$ , the graph obtained from $G$ by adding the edge $x y$ . By the edge-maximality of $G$ , $G^{'}$ is not a counter-example. Thus $G^{'}$ contains $k$ vertex-disjoint chorded cycles $C_{1}, \dots, C_{k}$ . Without loss of generality, we may assume $x y \notin \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}, \dots, C_{k - 1}$ with $C = \cup_{i = 1}^{k - 1} C_{i}$ , $H = G - C$ , and with $P_{1}$ a longest path in $H$ , such that:

(A1) $| C |$ is as small as possible,

(A2) subject to (A1), $c o m p (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 | \leq 17$ . Next suppose $| C_{i} | \leq 11$ for each $1 \leq i \leq k - 1$ . Since $| G | \geq 11 k + 7$ by assumption, it follows that $| H | \geq (11 k + 7) - 11 (k - 1) = 18$ , a contradiction. Thus $| C_{i} | \geq 12$ for some $1 \leq i \leq k - 1$ . Without loss of generality, we may assume $C_{1}$ is a longest cycle in $C$ . Then $| C_{1} | \geq 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} | = 4 t + r$ , where $t \geq 3$ and $0 \leq r \leq 3$ .

Subclaim 13. Let $t \geq 3$ be an integer. The cycle $C_{1}$ contains $t$ vertex-disjoint sets $X_{1}, \dots, X_{t}$ of four independent vertices each in $G$ such that $d_{C_{1}} (\cup_{i = 1}^{t} X_{i}) \leq 8 t + 4$ .

Proof. For any $4 t$ vertices of $C_{1}$ , their degree sum in $C_{1}$ is at most $4 t \times 2 + 4 = 8 t + 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} | = 4 t + r \geq 4 t$ . Start anywhere on $C_{1}$ and label the first $4 t$ vertices of $C_{1}$ with labels 1 through $t$ in order, starting over again with 1 after using label $t$ . If $r \geq 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 \geq 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_{1} x_{2}, y_{1} y_{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}$ .

Figure 3: Examples: (a) The Labels of $x$ and $y$ are 2 and 3; (b) The Labels of $x_{1}$ and $y_{2}$ are 2 and 1. ([ $i$ ] Means $i$ is a New Label for a Vertex after the Exchange)

Since $| C_{1} | \geq 12$ , $d_{C_{1}} (v) \leq 2$ for any $v \in V (H)$ by Lemma 2 and (A1). Thus since $| H | \leq 17$ by our assumption, it follows that $| E (H, C_{1}) | \leq 34$ . Let $X = \cup_{i = 1}^{t} X_{i}$ be as in Subclaim 13. By the $σ_{4} (G)$ condition, $d_{G} (X) \geq t (12 k - 3)$ . Suppose $k = 2$ . Then $C$ has only one cycle $C_{1}$ . Since $k = 2$ and $t \geq 3$ , $| E (C_{1}, H) | \geq d_{H} (X) \geq t (12 k - 3) - (8 t + 4) = 13 t - 4 \geq 35$ , a contradiction. Thus $k \geq 3$ . Then we have $\begin{aligned} | E (X, C - C_{1}) | & = d_{G} (X) - d_{C_{1}} (X) - d_{H} (X) \\ \geq t (12 k - 3) - (8 t + 4) - 34 \\ = 12 k t - 11 t - 38, \end{aligned}$ and since $t \geq 3$ , $\begin{aligned} 12 k t - 11 t - 38 & = 12 t (k - 1) + t - 38 \geq 12 t (k - 1) - 35 \\ > 12 t (k - 1) - 12 t \\ = 12 t (k - 2) . \end{aligned}$ Thus $| E (X, C^{'}) | > 12 t$ for some $C^{'}$ in $C - C_{1}$ , since $C - C_{1}$ contains $k - 2$ vertex-disjoint chorded cycles. Let $h = max {d_{C^{'}} (v) | v \in X}$ . Let $v^{*}$ be a vertex of $X$ such that $d_{C^{'}} (v^{*}) = h$ . Since $| E (X, C^{'}) | > 12 t$ , if $h \leq 3$ , then $| E (X, C^{'}) | \leq 3 \times 4 t = 12 t$ , a contradiction. Thus we may assume $h \geq 4$ . By the maximality of $C_{1}$ , $| C^{'} | \leq | C_{1} | = 4 t + r$ . It follows that $h = d_{C^{'}} (v^{*}) \leq | C^{'} | \leq 4 t + r$ . Recall $t \geq 3$ and $0 \leq r \leq 3$ . Then $\begin{matrix} (1) & \begin{aligned} | E (X - {v^{*}}, C^{'}) | \geq (12 t + 1) - d_{C^{'}} (v^{*}) \geq (12 t + 1) - (4 t + r) = 8 t - r + 1 \geq 22. \end{aligned} \end{matrix}$ Since $h = d_{C^{'}} (v^{*}) \geq 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 \leq i \leq 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, $⟨ (C_{1} - v^{*}) \cup C^{'} [v_{4}, v_{1}) ⟩$ contains a chorded cycle not containing at least one vertex of $⟨ (C_{1} - v^{*}) \cup C^{'} [v_{4}, v_{1}) ⟩$ . 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 $⟨ C_{1} \cup C^{'} ⟩$ , contradicting (A1). Hence Claim 12 holds.

Claim 14. $H$ is connected.

Proof. Suppose not, then $c o m p (H) \geq 2$ . Let $H_{1}, H_{2}, \dots, H_{c o m p (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) \leq 8$ . Then there exists some $C$ in $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 $σ_{4} (G)$ condition, $d_{C} (X) \geq (12 k - 3) - 8 = 12 k - 11 > 12 (k - 1)$ . Thus there exists some $C$ in $C$ such that $d_{C} (X) \geq 13$ . By Lemma 2, $d_{C} (x) \leq 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 \leq j \leq 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 $c o m p (H)$ .

Case 1. Suppose $c o m p (H) \geq 4$ .

By Theorem 1, there exists $x_{i} \in V (H_{i})$ for each $1 \leq i \leq 4$ such that $d_{H_{i}} (x_{i}) \leq 2$ . Let $X = {x_{1}, x_{2}, x_{3}, x_{4}}$ . Then $X$ is an independent set and $d_{H} (X) \leq 8$ . By Subclaim 15, the degree sequences from four vertices of $X$ to some $C$ in $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}) \geq d_{C} (x_{2}) \geq d_{C} (x_{3}) \geq 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_{1} v_{3}$ . If $x_{1}$ is not a cut-vertex of $H_{1}$ , then $H_{1} - x_{1}$ is connected. Replacing $C$ in $C$ by $C^{'}$ , we consider the new $H^{'}$ . Then $c o m p (H^{'}) \leq c o m p (H) - 2$ . This contradicts (A2). Thus we may assume $x_{1}$ is a cut-vertex of $H_{1}$ . Since $d_{H_{1}} (x_{1}) \leq 2$ , $d_{H_{1}} (x_{1}) = 2$ . Thus $c o m p (H_{1} - x_{1}) = 2$ , and $c o m p (H^{'}) \leq c o m p (H) - 1$ for the new $H^{'}$ . This contradicts (A2).

Case 2. Suppose $c o m p (H) = 3$ .

Without loss of generality, we may assume $| H_{1} | \geq | H_{2} | \geq | H_{3} |$ . Since $| H | \geq 18$ by Claim 12, we have $| H_{1} | \geq 6$ . Let $P_{1} = u_{1}, \dots, u_{s}$ be a longest path in $H_{1}$ . Note $s \geq 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}) \leq 2$ .

First suppose $u_{1} u_{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_{1} u_{3} \notin 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) \leq 8$ . By Subclaim 15, the degree sequences from four vertices of $X$ to some $C$ in $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}) \geq d_{C} (u_{3})$ . Then $d_{C} (u_{1}) \geq 3$ and $N_{C} (u_{3}) \cap N_{C} (x_{2}) \cap N_{C} (x_{3}) \neq \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_{1} v_{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 $C$ by $C^{'}$ , we consider the new $H^{'}$ . Then $c o m p (H^{'}) \leq c o m p (H) - 2 = 3 - 2 = 1$ . This contradicts (A2). Thus $d_{C} (u_{1}) = 3$ since $d_{C} (u_{1}) \geq 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}) \leq 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 \leq j \leq 3$ . Then $C^{'} = u_{1}, v_{1}, v_{2}, v_{3}, u_{1}$ is a 4-cycle with chord $u_{1} v_{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 $c o m p (H^{'}) \leq c o m p (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_{1} v_{3} \in E (G)$ . Then $C^{'} = u_{1}, v_{1}, v_{4}, v_{3}, u_{1}$ is a 4-cycle with chord $v_{1} v_{3}$ . Since $d_{C} (x_{3}) = 4$ , $v_{2} \in N_{C} (x_{2}) \cap N_{C} (x_{3})$ . Then $c o m p (H^{'}) \leq c o m p (H) - 1 = 3 - 1 = 2$ for the new $H^{'}$ , a contradiction. Suppose $v_{2} v_{4} \in E (G)$ . Then $C^{'} = u_{1}, v_{1}, v_{4}, v_{2}, u_{1}$ is a 4-cycle with chord $v_{1} v_{2}$ . Since $d_{C} (x_{3}) = 4$ , $v_{3} \in N_{C} (x_{2}) \cap N_{C} (x_{3})$ . Then $c o m p (H^{'}) \leq c o m p (H) - 1 = 3 - 1 = 2$ for the new $H^{'}$ , a contradiction.

Next suppose $u_{1} u_{s} \notin 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}) \leq 2$ for each $i \in {1, s}$ . Then $X$ is an independent set and $d_{H} (X) \leq 8$ . Replacing $u_{3}$ by $u_{s}$ in the above case where $u_{1} u_{s} \in E (G)$ , we get a similar contradiction.

Case 3. Suppose $c o m p (H) = 2$ .

Let $| H_{1} | \geq | H_{2} |$ . Since $| H | \geq 18$ by Claim 12, $| H_{1} | \geq 9$ . Let $P_{1} = u_{1}, \dots, u_{s}$ be a longest path in $H_{1}$ . Note $s \geq 3$ . By Theorem 1, there exists $x_{2} \in V (H_{2})$ such that $d_{H_{2}} (x_{2}) \leq 2$ .

First suppose $u_{1} u_{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) \leq 8$ . By Subclaim 15, the degree sequences from four vertices of $X$ to some $C$ in $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}) \geq 3$ by the degree sequences. Suppose $d_{C} (u_{1}) = 4$ . Since $N_{C} (u_{3}) \cap N_{C} (x_{2}) \neq \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 \leq i \leq 3$ . Then $C^{'} = u_{1}, v_{1}, v_{2}, v_{3}, u_{1}$ is a 4-cycle with chord $u_{1} v_{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 $C$ by $C^{'}$ , we consider the new $H^{'}$ . Then $c o m p (H^{'}) \leq c o m p (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 \leq i \leq 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_{1} v_{3} \in E (G)$ . Then $C^{'} = u_{1}, v_{1}, v_{4}, v_{3}, u_{1}$ is a 4-cycle with chord $v_{1} v_{3}$ . Since $d_{C} (x_{2}) = 4$ , $v_{2} \in N_{C} (u_{3}) \cap N_{C} (x_{2})$ . Then $c o m p (H^{'}) \leq c o m p (H) - 1 = 2 - 1 = 1$ for the new $H^{'}$ , a contradiction. Suppose $v_{2} v_{4} \in E (G)$ . Then $C^{'} = u_{1}, v_{1}, v_{4}, v_{2}, u_{1}$ is a 4-cycle with chord $v_{1} v_{2}$ . Since $d_{C} (x_{2}) = 4$ , $v_{3} \in N_{C} (u_{3}) \cap N_{C} (x_{2})$ . Then $c o m p (H^{'}) \leq c o m p (H) - 1 = 2 - 1 = 1$ for the new $H^{'}$ , a contradiction.

Next suppose $u_{1} u_{s} \notin E (H_{1})$ . Without loss of generality, we may assume $d_{C} (u_{1}) \geq d_{C} (u_{s})$ . Assume $P_{1}$ is a Hamiltonian path in $H_{1}$ . Note $s \geq 9$ since $| H_{1} | \geq 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}) \leq 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 \leq i \leq 5$ . Since $s \geq 9$ , $X_{0} = {u_{1}, u_{i}, u_{s}}$ is an independent set and $d_{H_{1}} (X_{0}) \leq 6$ . Thus $X = X_{0} \cup {x_{2}}$ is an independent set and $d_{H} (X) \leq 8$ . Then we get a contradiction by the same arguments as the case where $u_{1} u_{s} \in E (G)$ . Next suppose $d_{P_{1}} (u_{1}) = 2$ . Now assume $u_{1} u_{3} \in E (H_{1})$ . By Lemma 7, $d_{H_{1}} (u_{i}) = 2$ for some $4 \leq i \leq 6$ . Since $s \geq 9$ , $X_{0} = {u_{1}, u_{i}, u_{s}}$ is an independent set and $d_{H_{1}} (X_{0}) \leq 6$ , and we get a contradiction by considering $X = X_{0} \cup {x_{2}}$ similar to the case where $u_{1} u_{s} \in E (H_{1})$ . Thus $u_{1} u_{3} \notin E (H_{1})$ , that is, $u_{1} u_{i} \in E (H_{1})$ for some $4 \leq i \leq s - 1$ . By Lemma 6, $d_{H_{1}} (u_{i - 1}) = 2$ . Since $s \geq 9$ , $X_{0} = {u_{1}, u_{i - 1}, u_{s}}$ is an independent set and $d_{H_{1}} (X_{0}) \leq 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}) \neq \emptyset$ . Let $P_{2} = v_{1}, \dots, v_{t} (t \geq 1)$ be a longest path in $H_{1} - P_{1}$ . Without loss of generality, we may assume $d_{H_{1}} (v_{1}) \leq d_{H_{1}} (v_{t})$ . If $u_{1} u_{s} \in E (H_{1})$ , then since there exists a longer path than $P_{1}$ , we may assume $u_{1} u_{s} \notin E (H_{1})$ . Also we may assume $d_{H_{1}} (v_{1}) \leq 2$ , otherwise, since $d_{P_{1}} (v_{i}) \geq 1$ for each $i \in {1, t}$ by Lemma 11(iii) and (iv), there exists a cycle in $⟨ P_{1} \cup P_{2} ⟩$ 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}) \leq 6$ . Then $X = X_{0} \cup {x_{2}}$ is an independent set and $d_{H} (X) \leq 8$ . By Subclaim 15, the degree sequences from four vertices of $X$ to some $C$ in $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}) \geq d_{C} (u_{s})$ by our assumption, $d_{C} (u_{1}) \geq 3$ by the degree sequences. First suppose $d_{C} (u_{1}) = 4$ . Since $N_{C} (v_{1}) \cap N_{C} (x_{2}) \neq \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 \leq i \leq 3$ . Then $C^{'} = u_{1}, w_{1}, w_{2}, w_{3}, u_{1}$ is a 4-cycle with chord $u_{1} w_{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 $c o m p (H^{'}) \leq c o m p (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 \leq i \leq 3$ . Then $C^{'} = u_{1}, w_{1}, w_{2}, w_{3}, u_{1}$ is a 4-cycle with chord $u_{1} w_{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 $c o m p (H^{'}) \leq c o m p (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_{1} w_{3} \in E (G)$ . Then $C^{'} = u_{1}, w_{1}, w_{4}, w_{3}, u_{1}$ is a 4-cycle with chord $w_{1} w_{3}$ . Since $d_{C} (x_{2}) = 4$ , $w_{2} \in N_{C} (v_{1}) \cap N_{C} (x_{2})$ . Then $c o m p (H^{'}) \leq c o m p (H) - 1 = 2 - 1 = 1$ for the new $H^{'}$ , a contradiction. Suppose $w_{2} w_{4} \in E (G)$ . Then $C^{'} = u_{1}, w_{1}, w_{4}, w_{2}, u_{1}$ is a 4-cycle with chord $w_{1} w_{2}$ . Since $d_{C} (x_{2}) = 4$ , $w_{3} \in N_{C} (v_{1}) \cap N_{C} (x_{2})$ . Then $c o m p (H^{'}) \leq c o m p (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}, \dots, u_{s}$ be a longest path in $H$ . Note $s \geq 3$ since $| H | \geq 18$ and $H$ is connected by Claim 14. Let $P_{2} = v_{1}, \dots, v_{t}$ ( $t \geq 1$ ) be a longest path in $G - P_{1}$ such that $d_{P_{1}} (v_{1}) \leq 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) \leq 8$ . Then the degree sequences from four vertices of $X$ to some $C$ in $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_{1} u_{s} \notin E (H)$ , otherwise, a path longer than $P_{1}$ exists, a contradiction. Without loss of generality, we may assume $d_{C} (u_{1}) \geq d_{C} (u_{s})$ . By the degree sequences, we have $d_{C} (u_{1}) \geq 3$ .

Suppose $d_{C} (u_{1}) = 4$ . Since $N_{C} (u_{s}) \cap N_{C} (v_{1}) \neq \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 \leq i \leq 3$ . Then $C^{'} = u_{1}, x_{1}, x_{2}, x_{3}, u_{1}$ is a 4-cycle with chord $u_{1} x_{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 $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}) \geq 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 \leq i \leq 3$ . Then $C^{'} = u_{1}, x_{1}, x_{2}, x_{3}, u_{1}$ is a 4-cycle with chord $u_{1} x_{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} \notin N_{C} (u_{s})$ . Note $C$ has a chord. Suppose $x_{1} x_{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_{1} x_{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} \notin 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_{1} x_{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_{2} x_{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_{1} x_{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} \notin N_{C} (u_{s})$ . By symmetry, $x_{1} \notin N_{C} (u_{s})$ . Thus $d_{C} (u_{s}) \leq 1$ . This contradicts $d_{C} (u_{s}) = 2$ .

Next assume the degree sequence is $(4, 3, 3, 3)$ . Since $d_{C} (u_{1}) \geq 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}) \geq 3$ . First assume $d_{C} (v_{1}) = 4$ . Let $x_{i} \in N_{C} (u_{1})$ for each $1 \leq i \leq 3$ . Then $C^{'} = u_{1}, x_{1}, x_{2}, x_{3}, u_{1}$ is a 4-cycle with chord $u_{1} x_{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_{1} x_{3} \in E (G)$ . Then $C^{'} = u_{1}, x_{1}, x_{4}, x_{3}, u_{1}$ is a 4-cycle with chord $x_{1} x_{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_{2} x_{4} \in E (G)$ . Then $C^{'} = u_{1}, x_{1}, x_{4}, x_{2}, u_{1}$ is a 4-cycle with chord $x_{1} x_{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}) | \geq 2$ . Let $x_{i} \in N_{C} (u_{1})$ for each $1 \leq i \leq 3$ . Suppose $x_{1} x_{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_{3} x_{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 $w x_{2}$ , and $v_{1}, x_{1}, x_{4}, x_{3}, v_{1}$ is the other cycle with chord $x_{1} x_{3}$ . Thus we have two vertex-disjoint chorded cycles in $⟨ H \cup C ⟩$ , and $G$ contains $k$ vertex-disjoint chorded cycles, a contradiction. Assume $w \notin V (P_{1})$ . Then $C^{'} = u_{s}, x_{3}, x_{4}, x_{1}, u_{s}$ is a 4-cycle with chord $x_{1} x_{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_{2} x_{4} \in E (G)$ . Note $| N_{C} (u_{s}) \cap N_{C} (v_{1}) | \geq 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}) | \leq 1$ , a contradiction.

By Claims 10, 16 and Lemma 10, $H$ contains an independent set $X$ of four vertices such that $d_{H} (X) \leq 8$ . By Claim 16 and Lemma 13, $\begin{aligned} d_{G} (X) = d_{C} (X) + d_{H} (X) \leq 12 (k - 1) + 8 = 12 k - 4. \end{aligned}$ This contradicts the $σ_{4} (G)$ condition. This completes the proof of Theorem 5. 0

Acknowledgments

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.

References:

Corradi, K. and Hajnal, A., 1963. On the maximal number of independent circuits in a graph. Acta Mathematica Hungarica, 14(3-4), pp.423-439.
Enomoto, H., 1998. On the existence of disjoint cycles in a graph. Combinatorica, 18(4), pp.487-492.
Wang, H., 1999. On the maximum number of independent cycles in a graph. Discrete Mathematics, 205(1-3), pp.183-190.
Fujita, S., Matsumura, H., Tsugaki, M. and Yamashita, T., 2006. Degree sum conditions and vertex-disjoint cycles in a graph. Australasian Journal of Combinatorics, 35, pp.237-251.
Gould, R.J., Hirohata, K. and Keller, A., 2018. On vertex-disjoint cycles and degree sum conditions. Discrete Mathematics, 341(1), pp.203-212.
Finkel, D., 2008. On the number of independent chorded cycles in a graph. Discrete Mathematics, 308(22), pp.5265-5268.
Chiba, S., Fujita, S., Gao, Y. and Li, G., 2010. On a sharp degree sum condition for disjoint chorded cycles in graphs. Graphs and Combinatorics, 26, pp.173-186.
Gould, R.J., Hirohata, K. and Rorabaugh, A.K., 2020. On independent triples and vertex-disjoint chorded cycles in graphs. Australas. J Comb., 77, pp.355-372.
Chiba, S., Jiang, S. and Yan, J., 2020. Partitioning a graph into cycles with a specified number of chords. Journal of Graph Theory, 94(3), pp.463-475.
Chiba, S. and Yamashita, T., 2018. Degree conditions for the existence of vertex-disjoint cycles and paths: A survey. Graphs and Combinatorics, 34, pp.1-83.
Gao, Y., Lin, X. and Wang, H., 2019. Vertex-disjoint double chorded cycles in bipartite graphs. Discrete Mathematics, 342(9), pp.2482-2492.
Molla, T., Santana, M. and Yeager, E., 2020. Disjoint cycles and chorded cycles in a graph with given minimum degree. Discrete Mathematics, 343(6), p.111837.
Gould, R. J., (2012). Graph Theory, Dover Pub. Inc. Mineola, N.Y. 2012.

[1] Corradi, K. and Hajnal, A., 1963. On the maximal number of independent circuits in a graph. Acta Mathematica Hungarica, 14(3-4), pp.423-439.

[2] Enomoto, H., 1998. On the existence of disjoint cycles in a graph. Combinatorica, 18(4), pp.487-492.

[3] Wang, H., 1999. On the maximum number of independent cycles in a graph. Discrete Mathematics, 205(1-3), pp.183-190.

[4] Fujita, S., Matsumura, H., Tsugaki, M. and Yamashita, T., 2006. Degree sum conditions and vertex-disjoint cycles in a graph. Australasian Journal of Combinatorics, 35, pp.237-251.

[5] Gould, R.J., Hirohata, K. and Keller, A., 2018. On vertex-disjoint cycles and degree sum conditions. Discrete Mathematics, 341(1), pp.203-212.

[6] Finkel, D., 2008. On the number of independent chorded cycles in a graph. Discrete Mathematics, 308(22), pp.5265-5268.

[7] Chiba, S., Fujita, S., Gao, Y. and Li, G., 2010. On a sharp degree sum condition for disjoint chorded cycles in graphs. Graphs and Combinatorics, 26, pp.173-186.

[8] Gould, R.J., Hirohata, K. and Rorabaugh, A.K., 2020. On independent triples and vertex-disjoint chorded cycles in graphs. Australas. J Comb., 77, pp.355-372.

[9] Chiba, S., Jiang, S. and Yan, J., 2020. Partitioning a graph into cycles with a specified number of chords. Journal of Graph Theory, 94(3), pp.463-475.

[10] Chiba, S. and Yamashita, T., 2018. Degree conditions for the existence of vertex-disjoint cycles and paths: A survey. Graphs and Combinatorics, 34, pp.1-83.

[11] Gao, Y., Lin, X. and Wang, H., 2019. Vertex-disjoint double chorded cycles in bipartite graphs. Discrete Mathematics, 342(9), pp.2482-2492.

[12] Molla, T., Santana, M. and Yeager, E., 2020. Disjoint cycles and chorded cycles in a graph with given minimum degree. Discrete Mathematics, 343(6), p.111837.

[13] Gould, R. J., (2012). Graph Theory, Dover Pub. Inc. Mineola, N.Y. 2012.

Contents

Journal of Combinatorial Mathematics and Combinatorial Computing

On Vertex-Disjoint Chorded Cycles and Degree Sum Conditions

Abstract

1. Introduction

2. Preliminaries

3. Lemmas

4. Proof of Theorem 4

5. Proof of Theorem 5

Acknowledgments

References:

Information

Guidelines

CP Initiatives

Follow CP