\mychapter{A Result on Vertex Disjoint Cycles and Doubly Chorded Cycles}

\noindent 

In this chapter, we prove a result on vertex disjoint cycles and doubly chorded cycles.  Recall that a cycle is doubly chorded if it contains at least two chords (which may share at most one end-vertex). The results in this chapter differ from the results in the Chapter 2, in that the cycles in these results are not required to contain any specific elements of the graph.  First, let $r$ and $s$ be nonnegative integers and let $G$ be a graph with $|V(G)| \ge 4r+6s$ and $\sigma_2(G) \ge 4r+6s-1$. In this chapter, we prove that  such a graph $G$ contains a collection of $r+s$ vertex disjoint cycles such that $s$ of them are doubly chorded. This is an extension of earlier results.  This chapter is joint work with Dongqin Cheng and Ron Gould.



\section{Introduction}
\flushleft
As always, we let $G$ be a simple graph and $P_t$ (respectively, $C_t$) be a path (respectively, cycle) with $t$ vertices. In this chapter, a path $P$ is denoted $P=\langle u_1,u_2,\ldots,u_n \rangle$. Recall that the set of neighbors of $x$ in the subgraph $H \subseteq G$ is denoted $N_H(x)$. Again, we will focus on minimum degree and degree sum conditions. Let $\delta(G)$ denote the minimum degree of $V(G)$ and let
\begin{center}
$\sigma_2(G)$= min $\{\deg_G(u)+\deg_G(v) \mid u$ and $v$ are nonadjacent\}.
\end{center}

For terms not defined here, see \cite{G}.\\
\vspace{.1in}

As seen in Chapters 1 and 2, the study of vertex disjoint cycles and chorded cycles in graphs has attracted much attention over the past few decades. In 1963, Corr\'adi and Hajnal \cite{Corradi} proved that for an integer $r\ge 1$, any graph $G$ with $|V(G)| \ge 3r$ and minimum degree $\delta(G) \ge 2r$ contains $r$ vertex disjoint cycles. In 2008, Finkel \cite{F} proved the following extension of the Corr\'adi-Hajnal theorem for chorded cycles.\\

\begin{theorem} [\cite{F}] \label{DDCThmaa}
For an integer $k\ge1$, let $G$ be graph with $|V(G)| \ge 4k$ and $\delta(G) \ge 3k$. Then $G$ contains $k$ vertex disjoint chorded cycles.
\end{theorem}


Using Theorem \ref{DDCThmaa} as inspiration, Bialostocki, Finkel and Gy\'arf\'as \cite{BFG} proposed the following conjecture.

\begin{conjecture} [\cite{BFG}]
Let $s \ge 0$, $t \ge 0$ be two integers and $G$ be a graph with at least $3r+4s$ vertices. If $$\delta(G) \ge 2r+3s,$$ then $G$ contains $r+s$ vertex disjoint cycles such that $s$ of them are chorded cycles.
\end{conjecture}

They also proved that the conjecture is true for $r=0$, $s=2$ and for $s=1$. Their conjecture was proved to be true by Babu and Diwan \cite{Badu}, and Chiba and Fujita \cite{Chiba}. In particular, the authors in \cite{Badu, Chiba} generalized the minimum degree condition to a degree sum condition, and proved the following theorem.

\begin{theorem} [\cite{Badu, Chiba}] \label{DDCThma}
Let $r \ge 0$, $s \ge 0$ be two integers and let $G$ be a graph of order $n \ge 3r+4s$.  If $$\sigma_2(G) \ge 4r+6s-1,$$ then $G$ contains $r+s$ vertex disjoint cycles such that $s$ of them are chorded cycles.
\end{theorem}

Balister, Li and Schelp \cite{Balister} improved on Theorem \ref{DDCThma} under a minimum degree condition.

\begin{theorem}[\cite{Balister}] \label{DDCThmb}
For integers $r, s\ge 0$, let $G$ be a graph of order $n \ge 3r+4s$. If the minimum degree of $G$ $$\delta(G) \ge 2r+3s,$$ then $G$ contains $r+s$ vertex disjoint cycles, such that $s$ of them are either doubly chorded or $4$-cycles with one chord.
\end{theorem}

Qiao and Zhang \cite{Qiao} proved that $|V(G)| \ge 4k$ and $\delta(G) \ge \lceil 7k/2 \rceil $ can ensure $k$ vertex disjoint doubly chorded cycles in any graph $G$. Gould, Hirohata and Horn \cite{GHH} improved the degree condition in \cite{Qiao} to a degree sum condition and proved the following result.

\begin{theorem} [\cite{GHH}] \label{DDCThmc}
For an integer $k\ge 1$, let $G$ is a graph of order $|V(G)| \ge 6k$. If $$\sigma_2(G) \ge 6k-1,$$ then $G$ contains $k$ vertex disjoint doubly chorded cycles.
\end{theorem}

Using the aforementioned theorems as motivation, our goal for this chapter is to guarantee a collection of $r+s$ vertex disjoint cycles, such that $s$ of them are doubly chorded cycles. Specifically, we prove the following theorem.

\begin{theorem} \label{DDCThmd}
Let $r \ge 0$, $s \ge 0$ be two integers and let $G$ be a graph with $|V(G)| \ge 4r+6s$. If $$\sigma_2(G) \ge 4r+6s-1,$$then $G$ contains $r+s$ vertex disjoint cycles such that $s$ of them are doubly chorded cycles.
\end{theorem}



\section{Some Lemmas}

The following lemmas are useful to our main proof.\\
\vspace{.1in}

In \cite{GHH}, Gould, Hirohata, and Horn proved the following \emph{Exchange Lemma}.

\begin{lemma} [\cite{GHH}] \label{DDCLema}
Let $G$ be a graph containing a doubly chorded cycle $Q$. Suppose $x,y \in V(G-Q)$ are nonadjacent vertices with $\deg_Q(x) \ge 4$ and $\deg_Q(y) \ge 3$. Then there exist vertices $z_x, z_y \in V(Q)$ such that $z_x$ is adjacent to $x$ and $z_y$ is adjacent to $y$ and both $(Q-z_x) \cup \{y\}$  and $(Q-z_y) \cup \{x\}$ induce doubly chorded cycles.
\end{lemma}

Chiba et al. \cite{Chiba} proved the following lemma.

\begin{lemma} [\cite{Chiba}] \label{DDCLemaa}
For an integer $p \ge 4$, let $P=\langle x_1,x_2,\ldots,x_p \rangle$ be a path and let $C$ be a cycle of order at least four in $G$ such that $P$ and $C$ are vertex disjoint. Consider the vertex set $S=\{x_1,x_2,x_{p-1},x_p\}$. If $\sum_{x \in S} \deg_C(x) \ge 8$, then either $G[V(C) \cup V(P)]$ contains a cycle of length less than $|V(C)|$ or $G[V(C) \cup V(P)]$ contains two disjoint cycles.
\end{lemma}

There are two kinds of doubly chorded $5$-cycles, denoted by $C^{\land}_5$ and $C^{\times}_5$, see Figure 3a. Qiao and Zhang \cite{Qiao} proved the following lemma.


%\begin{figure}
%\renewcommand{\figurename}{Fig.}
\begin{center}
{\scalebox{.7}{ \includegraphics{C5.jpg} }}\\
%{\bf Figure 1.}

{\bf Figure 3a:} The two doubly chorded cycles of $C_5$.
\end{center}
%\end{figure}



\begin{lemma} [\cite{Qiao}] \label{DDCLemab}
Let $C$ be a cycle of a graph $G$ with at least two chords, and let $u$ be a vertex in $G-C$. If $\deg_C(u) \ge 4$, then either $G[V(C) \cup u]$ contains a cycle $C'$ with at least two chords and $|V(C')|<|V(C)|$, or $|V(C)| \le 5$ and $G[V(C) \cup u]$ contains $K_4$ or $C^{\land}_5$ as a subgraph.
\end{lemma}


We prove the following lemma.


\begin{lemma} \label{DDCLemc}
Let $C$ be a cycle. If $u,v \in V(G-C)$ and $\deg_C(u)+\deg_C(v) \ge 5$ and each vertex has at least one adjacent vertex on $C$, then there exists a vertex $z_u \in V(C)$ such that $z_u u \in E(G)$ and $G[V(C-z_u) \cup v]$ contains a cycle.
\end{lemma}

\begin{proof}
We only need to consider $\deg_C(u)+\deg_C(v)=5$. Let $C=\langle x_1, x_2, x_3, \ldots, x_{n-1}, x_n, x_1\rangle$. Consider the following cases according to the value of $n$.\\
\vspace{.1in}

\noindent
{\it Case 1:} Suppose $n=3$.\\
\vspace{.05in}

Since $\deg_C(u)+\deg_C(v)=5$, we see that $\deg_C(u)=3$ or $\deg_C(v)=3$. Without loss of generality, we may assume that $\deg_C(u)=3$, and so $N_C(u)=\{x_1,x_2,x_3\}$. By symmetry, we only need to consider $N_C(v)=\{x_2,x_3\}$. Then $z_u=x_1$ and $C'=\langle v,x_2,x_3,v \rangle$ is a cycle in $G[V(C-z_u) \cup v]$.\\
\vspace{.1in}

\noindent
{\it Case 2:} Suppose $n=4$.\\
\vspace{.1in}

\noindent
{\it Case 2.1:} Suppose $\deg_C(v)=4$ or $\deg_C(u)=4$.\\
\vspace{.05in}
Without loss of generality, we may assume that $\deg_C(v)=4$, then $\deg_C(u)=1$.  By symmetry, we only need to consider $N_C(u)=\{x_2\}$. Then $z_u=x_2$ and $C'=\langle v,x_1,x_4,v \rangle$ is a cycle in $G[V(C-z_u) \cup v]$.\\
\vspace{.1in}

\noindent
{\it Case 2.2:} Suppose $\deg_C(u)=3$ or $\deg_C(v)=3$.\\
\vspace{.05in}

Without loss of generality, assume that $\deg_C(u)=3$, then $\deg_C(v)=2$.  By symmetry, we only need to consider $N_C(u)=\{x_1,x_3,x_4\}$. Note that $N_C(v)=\{x_3,x_4\}$ is symmetric to $N_C(v)=\{x_1,x_4\}$; $N_C(v)=\{x_2,x_3\}$ is symmetric to $N_C(v)=\{x_1,x_2\}$. In both cases, we only need to consider the former case. The desired vertices and cycles can be found in Table \ref{tta}.

\begin{table}[htbp]
\caption{\label{tta}The desired edges and cycles in $C_4$.}
\begin{center}
\begin{small}
\begin{tabular}{lll}
\hline

 $N_C(v)$  & $z_u$  & $C'$\\

\hline

$\{x_3,x_4\}$ & $x_1$ & $\langle v,x_3,x_4,v \rangle $ \\

$\{x_1,x_3\}$ & $x_4$ & $\langle v,x_1,x_2,x_3,v \rangle $ \\

$\{x_2,x_3\}$ & $x_1$ & $\langle v,x_2,x_3,v \rangle $ \\

$\{x_2,x_4\}$ & $x_3$ & $\langle v,x_2,x_1,x_4,v \rangle $ \\

\hline

\end{tabular}
\end{small}
\end{center}
\end{table}

\noindent
{\it Case 3:} Suppose $n \ge 5$.\\
\vspace{.05in}
If $\deg_C(u)=4$ or $\deg_C(v)=4$, we may assume that $\deg_C(v)=4$, then $\deg_C(u)=1$. Assume that $N_C(u)=\{x\}$. Then $z_u=x$ and $G[V(C-z_u) \cup v]$ contains a cycle. Hence, we only need to consider $\deg_C(u)=3$ or $\deg_C(v)=3$. Without loss of generality, we may assume that $\deg_C(u)=3$. Let $N_C(u)=\{x_a,x_b,x_c\}$ and $N_C(v)=\{x_m,x_n\}$, where $x_i \in V(C)$ for $i \in \{a,b,c,m,n\}$. We consider the following cases according to the distribution of the vertices in $N_C(u)$ and $N_C(v)$.\\
\vspace{.1in}
Let the path between $x_m$ and $x_n$ on $C$ be denoted by $P_1$, and the path $C-P_1$ be denoted by $P_2$, where $m<n$. Now $\deg_C(u)=3$, so $u$ has an adjacent vertex, say $x_u$, on $C$ other than $x_m$ and $x_n$. It does not matter which path this adjacent vertex lies on, so without loss of generality, say $x_u \in P_2$, then $x_u=z_u$ and $v$ along with $P_1$ induces a cycle.\\
\vspace{.1in}

By the above cases, the proof is complete.
\end{proof}


\section{Proof of Theorem \ref{DDCThmd}}

In this section, we will prove our main result, Theorem \ref{DDCThmd}.

\begin{proof}
We prove the following stronger inductive statement.  Assume there exist $k+s$ vertex disjoint cycles, $s$ of them doubly chorded, $0 \le k<r$ and with at least $4(r-k) \ge 4$ vertices remaining off the cycles.  If $r=0$ and $s \ge 1$, then by Theorem \ref{DDCThmc} the result is true. If $s=0$ and $r \ge 1$, then by Theorem \ref{DDCThmaa} the result is also true.\\
\vspace{.1in}
Now suppose that $r \ge 1$ and $s>0$ and the result holds for $k<r$. Since $|V(G)| \ge 4r+6s>4k+6s$ and $\sigma_2(G) \ge 4r+6s-1>4k+6s-1$, by the induction hypothesis, $G$ contains $k+s$ vertex disjoint cycles such that $s$ of them are doubly chorded cycles. Without loss of generality, we let $\{C_1, C_2, \ldots, C_k\}$ be the $k$ vertex disjoint cycles and $\{Q_{1}$, $Q_{2},\ldots,Q_{s}\}$ be the $s$ vertex disjoint doubly chorded cycles. Let

$$H=G-\bigcup_{i=1}^k{C_i}-\bigcup_{j=1}^{s}Q_j.$$

Let $\mathcal H_1=\{C_1,C_2,\ldots,C_k\}$, $\mathcal H_2=\{Q_1,Q_2,\ldots,Q_s\}$. Obviously, $|H| \ge 4(r-k) \ge 4$ for $k<r$ and $H$ contains no cycles, or else we are done. Hence, $H$ is a forest.  We consider a tree $R \subseteq H$ as follows. Let $P=\langle u_1,u_2,u_3,\ldots,u_p \rangle$ be a longest path in $R$.  We assume that the cycles $C_1, C_2, \ldots, C_k, Q_{1}, Q_{2}, \ldots, Q_{s}$ are chosen in $G$ such that
\begin{quote}

$(i)$ $\sum_{i=1}^k|V(C_i)|+\sum_{j=1}^{s}|V(Q_j)|$ is as small as possible;\\
\vspace{.1in}

$(ii)$ the number of $C^{\land}_5$ in $\mathcal H_2$ is as large as possible, subject to $(i)$;\\
\vspace{.1in}

$(iii)$ $P$ is as long as possible, subject to $(i)$ and $(ii)$.

\end{quote}

First, we need the following lemma and claim.

\begin{lemma} \label{DDCLemd}
Let $P=\langle x_1,x_2,\ldots,x_{p-1},x_p \rangle$ be a path and $Q \in \mathcal H_2$ such that $P$ and $Q$ are vertex disjoint. Consider the vertex set $S=\{x_1,x_2,x_{p-1},x_p \}$. If $\sum_{x \in S}\deg_Q(x) \ge 13$, then either there are two vertex disjoint cycles such that one is a cycle and the other is a doubly chorded cycle in $G[V(P) \cup V(Q)]$, or there exists a doubly chorded cycle that is shorter than $Q$.
\end{lemma}

We postpone the proof of Lemma \ref{DDCLemd} until after the proof of Theorem \ref{DDCThmd}. First we will prove the following claim.\\
\vspace{.1in}

\noindent
\textbf{Claim 1.} $|V(P)| \ge 4$.\\
\vspace{.1in}
{\it Proof.}  For the sake of contradiction, assume that $|V(P)|<3$. Let $x$ and $y$ be the end-vertices of $P$, then $|N_H(x)|=1$ and $|N_H(y)|=1$. Hence, $$\deg_{G-H}(x)+\deg_{G-H}(y) \ge (4r+6s-1)-2=4r+6s-3=4(r-1)+6s+1.$$ Then there exists a cycle $C_i$ with $1 \le i \le k$ such that either $\deg_{C_i}(x)+\deg_{C_i}(y) \ge 5$, or there exists a doubly chorded cycle $Q_j$ with $1 \le j \le s$ such that $\deg_{Q_j}(x)+\deg_{Q_j}(y) \ge 7$.\\
\vspace{.1in}

We first consider the case where $\deg_{C_i}(x)+\deg_{C_i}(y) \ge 5$. If $\deg_{C_i}(x) \ge 4$ or $\deg_{C_i}(y) \ge 4$ (without loss of generality, we may assume that the former is true), then $|V(C_i)| \ge 4$ and the neighbors of $x$, say $x_1$, $x_2$, $x_3$ and $x_4$ in order, partition $C_i$ into four paths, , say $P_1'$, $P_2'$, $P_3'$ and $P_4'$, such that each path has one end-vertex which is a neighbor of $x$. Obviously, $G[V(P_j') \cup \{x,x_{j+1}\}]$ contains a cycle $C_j'$ for each $j \in \{1,2,3,4\}$ such that $|V(C_j')|=|V(P_j')|+2$. Since there is a cycle $C_k'$ for some $k \in \{1,2,3,4\}$ such that $|V(C_k')|=|V(P_k')|+2 \le \left\lceil \frac{|V(C_i)|}{4} \right\rceil+2 < |V(C_i)|$ for $|V(C_i)| \ge 4$, we can find a cycle $C_k'$ shorter than $C_i$ in $G[V(P) \cup V(C)]$, which is a contradiction to the choice of $(i)$. Hence $\deg_{C_i}(x) \ge 3$ or $\deg_{C_i}(y) \ge 3$. Without loss of generality, we may assume that $\deg_{C_i}(x) \ge 3$, then $\deg_{C_i}(y) \ge 2$. By Lemma \ref{DDCLemc}, there exists a vertex $z_x \in V(C_i)$ such that $z_x x \in E(G)$ and $G[(C-z_x) \cup y]$ contains a cycle. Then we can find a path longer than $P$, which is a contradiction to the choice of $P$.\\
\vspace{.1in}

We next consider the case where $\deg_{Q_j}(x)+deg~(y,Q_j) \ge 7$. If $\deg_{Q_j}(x) \ge 5$ or $\deg_{Q_j}(y) \ge 5$ (without loss of generality, we may assume that the former is true), then $|V(Q_j)| \ge 5$ and, similar to above, the neighbors of $x$ partition $Q_j$ into five paths, say $P_1''$, $P_2''$, $P_3''$, $P_4''$ and $P_5''$ in order. Then every four consecutive adjacent vertices of $x$ on $Q_j$ along with $x$ induce a doubly chorded cycle $Q_t'$ such that $|V(Q_t')|=|V(P_j'')|+|V(P_k'')|+|V(P_l'')|+2$ for three consecutive integers $j,k,l \in \{1,2,3,4,5\}$, where $t \in \{1,2,3,4,5\}$. If $|V(Q_j)|>5$, then there exists a doubly chorded cycle $Q_t'$ for some $t \in \{1,2,3,4,5\}$ such that $|V(Q_t')| \le \left\lceil \frac{3|V(Q_j)|}{5} \right\rceil+2<|V(Q_j)|$; if $|V(Q_j)|=5$, then we can find a $K_4$ in $G[V(Q_j) \cup \{x\}]$. In both cases, we can find a doubly chorded cycle shorter than $Q_j$, which is a contradiction to $(i)$. Hence, either $\deg_{Q_j}(x) \ge 3$ and $\deg_{Q_j}(y) \ge 4$, or $\deg_{Q_j}(x) \ge 4$ and $\deg_{Q_j}(y) \ge 3$. Without loss of generality, we may assume that the former is true. By Lemma \ref{DDCLema}, there exist vertices $z_x,z_y \in V(Q_j)$ such that $z_x$ is adjacent to $x$ and $z_y$ is adjacent to $y$ and $(Q_j-z_x) \cup y$ induces a doubly chorded cycle. Then $P \cup \{z_xx\}$ is a path longer than $P$, which is a contradiction to the choice of $P$. Thus, we conclude that $|V(P)| \ge 4$.\\
\vspace{.1in}

This completes the proof of the Claim.
\qed\\
\vspace{.2in}
By Claim 1, $|V(P)|=p \ge 4$. Obviously, $\deg_P(u_1)=\deg_P(u_p)=1$ and $u_1u_{p-1}, u_2u_p \not\in E(G)$, otherwise a cycle would result. We then have that
$$\sum_{(x,y) \in \{(1,p-1),(2,p)\} } deg~(u_x,H)+deg~(u_y,H) \le 6.$$ By the degree sum condition, we have

\begin{align*}
& \sum_{(x,y) \in \{(1,p-1),(2,p)\} } \deg_{G-H}(u_x)+\deg_{G-H}(u_y) \\
& \ge 2(4r+6s-1)-6 \\
& =8r+12s-8 \\
& =8(r-1)+12s.
\end{align*}

Recall that $s>0$ and $r>1$. If any cycle $C_i$ with $1 \le i \le k$ has
$$ \sum_{(x,y) \in \{(1,p-1),(2,p)\}} \deg_{C_i}(u_x)+\deg_{C_i}(u_y) \ge 8, $$ then by Lemma \ref{DDCLemaa} either there exists a cycle in $G[V(C) \cup V(P)]$ that is shorter than $C$, which is a contradiction; or $G[V(C) \cup V(P)]$ contains two disjoint cycles, in which case there are $(k+1)+s$ vertex disjoint cycles in $G$ such that $s$ of them are doubly chorded cycles. Then by induction, the result follows.\\
\vspace{.1in}

Therefore, $\{x_1,x_2,x_{p-1},x_p\}$ must send at most seven edges to each cycle $C_i$ for $1 \le i \le k$. However, now there must be a doubly chorded cycle $Q_j$ with $1 \le j \le s$ such that
$$ \sum_{(x,y) \in \{(1,p-1),(2,p)\} }\deg_{Q_j}(u_x)+\deg_{Q_j}(u_y) \ge 13. $$

Note that in this case, there is a vertex $x \in \{x_1,x_2,x_{p-1},x_p\}$ such that $\deg_{Q_j}(x) \ge 4$. By Lemma \ref{DDCLemab} and the choices of $(i)$ and $(ii)$, we must have $Q=K_4$ or $Q=C^{\land}_5$. Then by Lemma \ref{DDCLemd}, there exist two vertex disjoint cycles such that one is a cycle and the other is a doubly chorded cycle in $G[V(Q_j) \cup V(P)]$. Hence, there exist $(k+1)+s$ vertex disjoint cycles in $G$ such that $s$ of them are doubly chorded cycles, and again by induction, the result follows.
\end{proof}


\noindent
{\bf Proof of Lemma \ref{DDCLemd}}\\
\vspace{.1in}

{\it Proof.}  Since $\sum_{x \in S}\deg_Q(x) \ge 13$, there exists a vertex $x \in S$ such that $\deg_Q(x) \ge 4$. By Lemma \ref{DDCLemab}, either $G[V(C) \cup u]$ contains a doubly chorded cycle $Q'$ shorter than $Q$, then we are done; or we may assume that $Q=K_4$ or $Q=C^{\land}_5$. We need to examine the following two cases.\\
\vspace{.1in}

\noindent
{\bf Case 1:} Suppose $Q=K_4$ with $4$-cycle $\langle y_1,y_2,y_3,y_4,y_1 \rangle$ and two chords $y_1y_3$ and $y_2y_4$.  By symmetry, we need to consider the following two cases.\\
\vspace{.1in}

\noindent
{\bf Case 1.1:} Suppose $\deg_Q(x_1)=4$. (Note that the case where $\deg_Q(x_p)=4$ is symmetric to the $\deg_Q(x_1)=4$ case.)\\
\vspace{.05in}
Then $N_Q(x_1)=\{y_1,y_2,y_3,y_4\}$. Note that there is at most one vertex, say $x \in \{x_2,x_{p-1},x_p\}$, such that $|N_Q(x)| \le 2$. For $x', x'' \in \{x_2,x_{p-1},x_p\} \backslash \{x\}$, $|N_Q(x')| \ge 3$ and $|N_Q(x'')| \ge 3$. Let $P^*$ be the sub-path of $P$ from $x'$ to $x''$. (Note this path may be just one edge.) Without loss of generality, we may assume that $y_3 \in N_Q(x') \cap N_Q(x'')$. Then $C'=\langle y_3,x',P^*,x'',y_3 \rangle$ and $Q'=\langle x_1,y_2,y_1,y_4,x_1 \rangle $ with two chords $y_2y_4$ and $x_1y_1$ are the desired cycles.\\
\vspace{.1in}

\noindent
{\bf Case 1.2:} Suppose $\deg_Q(x_2)=4$. (Note that the case where $\deg_Q(x_{p-1})=4$ is symmetric to the $\deg_Q(x_2)=4$ case.)\\
\vspace{.05in}
Then $N_Q(x_2)=\{y_1,y_2,y_3,y_4\}$. Note that there is at most one vertex, say $x \in \{x_1,x_{p-1},x_p\}$, such that $|N(x,Q)| \le 2$. For $x',x'' \in \{x_1,x_{p-1},x_p\} \backslash \{x\}$, $|N_Q(x')| \ge 3$ and $|N_Q(x'')| \ge 3$. Hence, there exists a vertex $y \in V(Q)$ such that $y \in N_Q(x_{p-1}) \cap N_Q(x_p)$. It can be easily seen that $\langle y,x_{p-1},x_p,y \rangle$ is a cycle and $G[V(Q-y) \cup x_2]$ is a $K_4$.\\
\vspace{.1in}


\noindent
{\bf Case 2:} Suppose $Q=C^{\land}_5$ with cycle $\langle y_1,y_2,y_3,y_4,y_5,y_1 \rangle$ and with two chords $y_1y_3$ and $y_1y_4$.\\
\vspace{.05in}


For any vertex $x_i \in S$, if $\{y_1,y_4,y_5\} \subset N_Q(x_i)$ (respectively, $\{y_1,y_2,y_3\} \subset N_Q(x_i)$), then $G[\{ x_i,y_1,y_4,y_5\}]$ (respectively, $G[\{ x_i,y_1,y_2,y_3\}]$) induces a $K_4$, which is a contradiction to the choice of $(i)$. Hence, we only need to consider $N_Q(x_i)=\{y_2,y_3,y_4,y_5\}$. By symmetry, we need only to consider the following two cases.\\
\vspace{.1in}

\noindent
{\bf Case 2.1:} Suppose $\deg_Q(x_1)=4$. (Note that the case where $\deg_Q(x_p)=4$ is symmetric to the $\deg_Q(x_1)=4$ case.)
For any vertex $x \in \{x_2,x_{p-1},x_p\}$, we need to consider the following three cases.\\
\vspace{.1in}

\noindent
{\bf Case 2.1.1:} Suppose $N_Q(x)=N_Q(x_1)=\{y_2,y_3,y_4,y_5\}$.\\
\vspace{.05in}
If $x=x_2$, then $G[\{x_1,x,y_4,y_5\}]$ induces a $K_4$, which is a contradiction to (i).  Suppose $x=x_{p-1}$. Now if $x_p$ has a common neighbor, say $y$, with $x_{p-1}$ on $C^{\land}_5$, then these three vertices form a $K_3$ and $G[(C^{\land}_5-y) \cup x_1]$ contains a doubly chorded cycle. If $x_p$ is only adjacent to $y_1$ on $C^{\land}_5$, then $x_2$ must have $4$ neighbors and we are done by an argument similar to the case where $x=x_2$.\\
\vspace{.1in}
Now assume $x=x_p$. Now since $x_2$ or $x_{p-1}$ has a common neighbor, say $y$, with $x_p$, then $y$ and the path between $x_2$ (or $x_{p-1}$) and $x_p$ induce a cycle and again $G[(C^{\land}_5-y) \cup x_1]$ contains a doubly chorded cycle.\\
\vspace{.1in}

\noindent
{\bf Case 2.1.2:} Suppose $\deg_Q(x)=4$ and $N_Q(x) \neq N_Q(x_1)$ for $x \in \{x_2,x_p,x_{p-1}\}$.\\
\vspace{.05in}
In this case, $y_1 \in N_Q(x)$ and three other vertices from $\{y_2,y_3,y_4,y_5\}$. No matter which three vertices are chosen, a $K_4$ exists, which is a contradiction.\\
\vspace{.1in}

\noindent
{\bf Case 2.1.3:} Suppose $|N_Q(x)|=3$.\\
\vspace{.05in}

In this case, any two vertices of $\{x_2,x_{p-1},x_p\}$, say $x'$ and $x''$, have a common neighbor, say $y$.  If $y=y_1$, then $C'=\langle y_1,x',x'',y_1 \rangle$ and $Q'=\langle x_1,y_2,y_3,y_4,y_5,x_1 \rangle$ with two chords $x_1y_4$ and $x_1y_3$ are the desired cycles. If $y=y_2$, then $C'=\langle y_2,x',x'',y_2 \rangle$ and $Q'=\langle x_1,y_4,y_3,y_1,y_5,x_1 \rangle$ with two chords $y_1y_4$ and $y_5y_4$ are the desired cycles. If $y=y_3$, then $C'=\langle y_3,x',x'',y_3 \rangle$ and $Q'=\langle x_1,y_5,y_4,y_1,y_2,x_1 \rangle$ with two chords $y_1y_5$ and $x_1y_4$ are the desired cycles. If $y=y_4$, then $C'=\langle y_1,y_2,y_3,y_1 \rangle$ and $Q'=\langle x_1,y_5,y_4,x'',x',x_1 \rangle$ with two chords $x_1y_4$ and $x'y_4$ are the desired cycles. If $y=y_5$, then $C'=\langle y_1,y_2,y_3,y_1 \rangle$ and $Q'=\langle x_1,y_4,y_5,x'',x',x_1 \rangle$ with two chords $x_1y_5$ and $x'y_5$ are the desired cycles. See Figure 3b.\\

\vspace{.1in}

%\begin{figure}
%\renewcommand{\figurename}{Fig.}
%\begin{center}
%\centering
%\includegraphics{C5d}
%\end{center}
%\caption{\label{C5d} $|N(x,Q)|=3$.}
%\end{figure}


%\begin{figure}
%\renewcommand{\figurename}{Fig.}
\begin{center}
{\scalebox{.5}{ \includegraphics{C5d.jpg} }}\\
{\bf Figure 3b:} $|N(x,Q)|=3$
\end{center}
%\caption{ $|N(x,Q)|=3$.}
%\end{figure}

\newpage



\noindent
{\bf Case 2.2:} Suppose $\deg_Q(x_2)=4$. (Note that the case where $\deg_Q(x_{p-1})=4$ is symmetric to the $\deg_Q(x_2)=4$ case.)\\
\vspace{.05in}

By substituting $x_2$ for $x_1$ in Case 2.1, it can be checked that this case also follows.\\
\vspace{.1in}

This completes the proof.

\qed\\
\vspace{.1in}


By Lemma \ref{DDCLemd}, we directly obtain the following corollary.

\begin{corollary}
Let $P$ be a path with $|V(P)|=3$ and $Q \in \mathcal H_2$ such that $P$ and $Q$ are vertex disjoint. If $\sum_{x \in V(P)}\deg_Q(x) \ge 10$, then there are two vertex disjoint cycles such that one is a cycle and the other is a doubly chorded cycle in $G[V(P) \cup V(Q)]$.
\end{corollary}























