\mychapter{Vertex Disjoint Chorded Cycles Containing Specified Graph Elements}

\noindent 


This chapter explores minimum degree and degree sum conditions for graphs sufficient to imply that the graph contains $k$ vertex disjoint chorded (or sometimes doubly chorded) cycles which contain specific elements of the graph.  In particular, sets of specific chords, sets of specific edges, and sets
of specific vertices are all considered.  We also investigate degree sum  and minimum degree conditions sufficient to imply that a set of independent edges are the chords of vertex disjoint cycles.  The results in this chapter are joint with Ralph Faudree, Ron Gould, and Kazuhide Hirohata. 


\section{Introduction}

The study of cycles and systems of vertex disjoint cycles in graphs is well established.   Recently, there have been numerous papers considering cycles with additional properties such as containing
a specific set of vertices, or containing a specific set of edges, or even containing a set of vertex disjoint paths (for a good overview, see the survey \cite{G2}). Another natural property for cycles is that of containing at least one chord or at least some number $t \geq 1$ of chords.   The study of chorded cycles has been
increasing recently (see for example \cite{BFG}, \cite{F}, \cite{Kazu} and \cite{GHM}).
In this chapter, we extend several well-known results on sets of vertex disjoint
cycles containing specific elements such as edges or vertices to results on sets of vertex disjoint chorded cycles containing these elements.

As described in $\S1.2$, we consider only finite simple graphs.  Again, we let $G$ be a graph and $P_t$ be a path on $t$ vertices.   
%For $S \subseteq V(G)$, let $G[S]$ denote the subgraph of $G$ induced by $S$.  Let $N(u)$ denote the set of neighbors of the vertex $u$, that is, the vertices adjacent to $u$ in the graph.  For a set of vertices $\{u_1, u_2, \ldots, u_k\}$ and a subgraph $H$ of $G$, let $\deg_H(u_1, u_2, \ldots, u_k)$ be the sum of the degrees of the vertices $u_i$ (for $1\le i\le k$) to the subgraph $H$.   
In particular, we will focus on minimum degree and degree sum conditions in this chapter.  Recall that $\delta(G)$ is the minimum degree of a graph $G$, and for a non-complete graph $G$, we define the following degree sum condition:
$$\sigma_2 (G) = ~\mbox{min}~ \{ deg_G(u )+ deg_G(v )~|~ u~ \mbox{and}~v~ \mbox{are~nonadjacent} \}.$$
By convention we say $\sigma_2(G)=2$ if $G$ is a complete graph.  
For terms not defined here see \cite{G}.  

As one source of inspiration, we note the following well-known result on cycles containing independent, or vertex disjoint, edges from a given set.
 
\begin{theorem} {\rm \cite{EFG} }
Let $\{e_1, e_2,\ldots, e_k\}$ be a set of independent edges in $G$, a graph 
of order $n\ge 4k$ such that $$\delta(G)\ge \left\lceil{\frac{n}{2}}\right\rceil +k-1,$$ 
for $2\le k\le \frac{n}{3}$, then $G$ contains a set of $k$ vertex 
disjoint cycles $\{C_1, C_2, \ldots, C_k\}$, such 
that $3\le|V(C_i)|\le 4$ and $e_i\in E(C_i)$ for all $1\le i\le k$. 
Further, there exists a set of $k$ vertex disjoint cycles $\{D_1, D_2, \dots, D_k\}$ 
such that $e_i\in E(D_i)$ for all $1\le i\le k$, and $V(G)=\bigcup_{i=1}^k V(D_i)$.
\label{thm:Egawa+} 
\end{theorem}

We also note a similar known result about placing vertices on cycles.

\begin{theorem} {\rm \cite{EEF} }
Let $G$ be a graph of order $n\ge 6k-3$ for some integer $k\ge1$.  
If $$\delta(G)\ge \frac{n}{2},$$ then for any set of $k$ vertices 
$\{v_1, v_2, \ldots, v_k\}$ there exists a set of $k$ vertex disjoint 
cycles $\{C_1, C_2, \ldots, C_k\}$ such that $v_i\in V(C_i)$ and 
$|V(C_i)|\le 5$ for all $1\le i\le k$. 
\label{thm:kvertsoncyc}
\end{theorem}

In this chapter, we extend each of the last two results to chorded cycles, and in one case, doubly chorded cycles.   In addition, we consider the basic question of when a set of $k$ independent edges can be chords for $k$ vertex disjoint cycles, one per cycle. We also show when the $k$ vertex disjoint cycles can be extended to span the entire vertex set of the graph.  

\section{Results}

\subsection{Placing Edges as Chords on Cycles}
We begin with a natural question:  When can a set of $k$ independent edges 
be the set of chords for $k$ vertex disjoint cycles of a graph, one per cycle?

\begin{theorem}
Let $G$ be a graph of order $n\ge 6k+1$ %we had n\ge 6k+2 for some reason
for an integer $k\ge2$.  
If $$\sigma_2(G)\ge n+3k-2 \text{ and }~\delta(G)\ge 6k-3,$$ then for any $k$ independent edges 
$\{e_1, e_2, \ldots, e_k\}$ there exists a set of $k$ vertex disjoint 
cycles $\{C_1, C_2, \ldots, C_k\}$ such that $e_i$ is a chord of $C_i$ and 
$4\le|V(C_i)|\le 6$ for all $1\le i\le k$. 
\label{thm:main}
\end{theorem}

\flushleft{\bf Sharpness:} To see that $\sigma_2(G)\ge n+3k-2$ is needed, consider
the following graph, $G$: place the chosen set of edges 
$E=\{e_1, e_2, \ldots, e_k\}$ in a clique, which is completely adjacent to
a clique on $2k-1$ vertices, which is completely adjacent to a clique on the
remaining $n-4k+1$ vertices.  In addition, exactly one end-vertex from each edge of $E$ 
is adjacent to every vertex in the $K_{n-4k+1}$ (See Figure 2a below). \\

\begin{center}
{\scalebox{.55}{ \includegraphics{sharp2k5.jpg} }}\\
{\bf Figure 2a.}
\end{center}

To find $\sigma_2(G)$ we must consider all pairs of non-adjacent vertices in $G$.  The only type of non-adjacent pair of vertices in $G$ is an end-vertex of an edge in $E$, say $x$, and a vertex in the $K_{n-4k+1}$, say $y$, as illustrated above in Figure 2a. Then 

\begin{align*}
\sigma_2(G)&=deg_G(x)+deg_G(y)\\
&= (2k-1+2k-1)+(n-4k+2k-1+k)\\
&= n+3k-3. 
\end{align*}

For any $e_i\in E$ to be a chord of a cycle requires using two neighbors in the $K_{2k-1}$, so there are at most $k-1$ vertex disjoint cycles with the desired edges as chords.  This proves the necessity of $\sigma_2(G)\ge n+3k-2$. \\
\vspace{.1in}

Before proving Theorem \ref{thm:main}, we first prove the following lemma and theorem. 

\begin{lemma} Let $G$ be a graph of order $n\ge 4$ with $\sigma_2(G)\ge n+1$.  Then any edge of $G$ lies either on a triangle or on a 4-cycle.  
\label{lem:3or4cycle}
\end{lemma}

\begin{proof}
Let $e=ab$ be any edge of $G$. If $e$ lies on a triangle we are done, so assume $e$ does not lie on any triangle.  Since $\sigma_2(G)\ge n+1$, we know $G$ is 2-connected.  Let $x$ be any vertex adjacent to an end-vertex of $e$.  Without loss of generality, say $x$ is adjacent to $a$.  Then $b$ is not adjacent to $x$, otherwise $e$ would lie on a triangle.  Now $\deg_G(x) + \deg_G(b)\ge n+1$, which implies that $b$ and $x$ have at least three common neighbors.  Thus there is a vertex $y\neq a$ such that $by$ and $xy\in E(G)$.  Then the cycle $a, x, y, b, a$ is a 4-cycle containing $e$ as an edge.
\end{proof}

{\bf Example:} Consider the graph $G$ on $n$ vertices that is a copy of $K_{n-2}$ together with another edge $e=xz$.  Let $x$ be adjacent to exactly two vertices of $K_{n-2}$ and let $z$ be adjacent to all of the vertices in $V(G)-N_G(x)$.  Then $\sigma_2(G)\ge \deg_G(x)+\deg_G(y)=3+n-2=n+1$, and the shortest cycle to have $e$ as a chord in $G$ is a 6-cycle.  Thus, 6-cycles are necessary in the following result: the $k=1$ case of Theorem \ref{thm:main}.  

\begin{theorem} Let $G$ be a graph of order $n\ge 6$ with $\sigma_2(G)\ge n+1$,  Then any edge of $G$ is the chord of a cycle $C$ with $4\le|V(C)|\le 6$.  
\label{thm:k=1}
\end{theorem} 

\begin{proof} Let $e$ be any edge in the graph $G$. Then by Lemma \ref{lem:3or4cycle}, we know that $e$ lies on either a triangle or a 4-cycle. \\
\vspace{.1in}
{\it Case 1.} Suppose $e$ lies on a triangle, say $T=\{a, b, c\}$.  \\Let $e=ab$.  Note that the degree-sum condition implies that $G$ is at least 2-connected, thus at least two of the vertices in the set $\{a, b, c\}$ must have neighbors outside of $T$.  Without loss of generality, assume $a$ has such a neighbor.  Let $R=G-\{a, b, c\}$ and consider some $x\in V(R)$ such that $ax\in E(G)$. If $xb\in E(G)$, then $c, a, x, b, c$ is a 4-cycle with $e$ as a chord, so suppose $xb\not\in E(G)$.  Then $\deg_T(b)=2$ and $\deg_T(x)\le 2,$ so from the degree-sum condition, $x$ and $b$ share at least three neighbors.  Thus, there exists some $y\in V(R)$ with $y\neq x$ such that both $b$ and $x$ are adjacent to $y$.  Now $c, a, x, y, b, c$ is a 5-cycle with $e$ as a chord.\\
\vspace{.1in}
{\it Case 2.} Suppose $e$ lies on a 4-cycle, $F=a, b, c, d, a$, but lies on no triangle.\\ Let $e=ab$.  Since no vertex in $R=G-F$ can be adjacent to both $a$ and $b$, consider the following disjoint sets of vertices: $R_a$, the neighborhood of $a$ in $R$ and $R_b$, the neighborhood of $b$ in $R$. If $\delta(G)=2$ then by the degree-sum condition, there is a vertex in $R$ of degree $n-1$ which implies that $e$ is on a triangle.  Since $\delta(G)\ge 3$, the neighborhoods $R_a$ and $R_b$ are both non-empty.  If there are no edges between $R_a$ and $R_b$ then for any $x\in R_a$, the degree sum of the non-adjacent pair of vertices $x$ and $b$ is at most $$\deg_G(x)+\deg_G(b)\le |V(R)|-|R_b|-1+3+|R_b|+2=|V(R)|+4=(n-4)+4=n$$ a contradiction of the assumed $\sigma_2(G)$.  Thus there is an edge from some $x\in R_a$ to some $y\in R_b$ and hence $d, a, x, y, b, c, d$ is a 6-cycle containing $e$ as a chord, as desired.

%\vspace{.1in}
%{\it Case 2.1.} Without loss of generality, suppose that $R_a\neq\O$ and $R_b=\O$.\\
 %Then $\deg_G b=2$, as any chord in $F$ would result in a triangle containing the edge $e$. Consider $x\in N(a, R)$, then $\deg_G x\le n-5+3=n-2$.  So the degree sum of the non-adjacent pair of vertices $x$ and $b$ is $\deg_G x+\deg_G b\le n-2+2=n$, a contradiction of the assumed $\sigma_2(G)$.    \\

\end{proof}


\begin{proof} (of Theorem \ref{thm:main}). 
Assume the result fails and let $G$ be an edge maximal counterexample.  Then adding any new edge $e$ to $G$ will yield the desired set of $k$ chorded cycles with $e_i$ a chord of $C_i$ for $i=1, 2, \ldots, k$.  Therefore, there must be at least one set of $k-1$ cycles $\mathcal{C}=\{C_1, C_2, \ldots, C_{k-1}\}$ with $e_i$ as a chord of $C_i$ and $4\le |V(C_i)|\le 6$ for $1\le i\le k-1$. Further, note that in $G-\mathcal{C}$ there is a 3, 4, or 5-cycle, $C$, containing the edge $e_k$ and with an adjacency to a vertex not in $C$ or $\mathcal{C}$ from at least one end-vertex of $e_k$. This follows as $G+e$ contains the desired cycle system of chorded 4, 5, and two different types of chorded 6-cycles, which are defined and shown below in Figure 2b. No matter where $e$ falls on these cycles, we obtain $C$ as described.

\begin{center}
{\scalebox{.7}{\includegraphics{sixcycletypes.jpg} }}\\
{\bf Figure 2b.}
\end{center}


Over all possible edge maximal counterexamples and over all possible such cycles sets $\mathcal{C}$, choose $\mathcal{C}$ such that:
\begin{enumerate}
\item $\displaystyle\cup_{i=1}^{k-1}|V(C_i)|$ is a minimum. 
\item Subject to (1), $|V(C)|$ is a minimum.
\item Subject to (1) and (2), the number of Type I chorded 6-cycles is a maximum.  
\end{enumerate}

In $\mathcal{C}$ assume there are $r$ 4-cycles, $s$ 5-cycles, and $t$ 6-cycles as shown in Figure 2c. Let $e_k=ab$ be an edge of $C$ and let $R=G-\mathcal{C}-C$. Now we place some bounds on degrees of nonadjacent vertices.  Without loss of generality, we assume $a$ is the end-vertex of $e_k$ with an adjacency, say $x$, 

off of $C$ and not in $\mathcal{C}$ (i.e. $x\in V(R)$). Note that $b$ is not adjacent to $x$, otherwise we would complete the desired cycle system, a contradiction.\\

\begin{center}
{\scalebox{.61}{ \includegraphics{CCFig2.jpg} }}\\
{\bf Figure 2c.}
\end{center}

Note that $b$ has at most two adjacencies in the cycle $C$, otherwise there would be a contradiction to (2). Also, since $b$ has at most $6(k-1)$ adjacencies to $\mathcal{C}$, by the minimum degree condition $b$ must have at least one neighbor in $R$. Thus, there is some $y\in V(R)$ such that $b$ is adjacent to $y$ and $a$ is not adjacent to $y$ (or the desired cycle system would be completed).  Consider the nonadjacent pairs  of vertices $(a,y)$ and $(b,x)$.  Once again, we examine the adjacencies from these pairs to the cycles of $\mathcal{C}$.  \\
\vspace{.1in}
{\bf Claim 1.} For a 3-cycle $C=a, b, c, a$, the nonadjacent pairs $(a, y)$ and $(b, x)$ may have at most 14 edges to any chorded 4-cycle $C_i\in \mathcal{C}$, 16 edges to any chorded 5-cycle $C_i\in \mathcal{C}$, and 18 edges to any chorded 6-cycle $C_i\in \mathcal{C}$.  
\begin{proof}
If $a$ and $b$ have a common neighbor on $C_i$, a 4-cycle, other than the end-vertices of the chord $e_i$, then both $x$ and $y$ cannot be adjacent to both ends of the chord $e_i$ otherwise there are two cycles containing the desired chords, a contradiction.  Thus, in this case the total number of edges to $C_i$ is at most 8 from $a$ and $b$, and at most 6 from $x$ and $y$.  If $a$ and $b$ have no such common neighbor in $C_i$, then they send at most 6 edges to $C_i$ and $x$ and $y$ can both be adjacent to every vertex in $C_i$.  Therefore, in either case we have $deg_{C_i}(a, b, x, y)\le 14$.\\  
\vspace{.25cm}

If $a$ and $b$ have a common neighbor in $C_i$, a 5-cycle, that is not an end-vertex of the chord $e_i$, then there exists a chorded 4-cycle containing the chord $e_k$, contradicting the minimality of $\mathcal{C}$.  Therefore, $a$ and $b$ have at most 7 edges to $C_i$.  If either $x$ or $y$ is adjacent to both end-vertices of the chord of $C_i$, then there exists a chorded 4-cycle containing that same chord, which contradicts the minimality of the cycle set $\mathcal{C}$.  Thus, $x$ and $y$ can have at most 8 edges to the chorded 5-cycle, $C_i$. In total, we have $deg_{C_i}(a, b, x, y)\le7+8\le 16.$\\ 
\vspace{.25cm}
 
If $a$ and $b$ have a common neighbor in $C_i$, a 6-cycle, other than the end-vertices of $e_i$, then there exists a 4-cycle with $e_k$ as a chord, a contradiction of the minimality of $\mathcal{C}$.  Thus, together $a$ and $b$ can send at most 8 edges to $C_i$.  If $x$ or $y$ are adjacent to both end-vertices of the chord $e_i$ then there exists a 4 or 5-cycle (depending on where the chord of $C_i$ is) containing $e_i$ as a chord, again contradicting the minimality of $\mathcal{C}$.  Thus, together $x$ and $y$ can send at most 10 edges to $C_i$.  So in total, we have $deg_{C_i}(a, b, x, y)\le 18$.  
\end{proof}

Suppose $C$ is a 3-cycle.  Note that $a$ and $b$ cannot share any neighbors in $R$, otherwise there would be a 4-cycle containing $e_k$ as a chord, which would complete the desired cycle set, a contradiction. Thus, the maximum possible number of edges from $a$ and $b$ together to $R$ is $|V(R)|$.  Note that $x$ cannot be adjacent to $y$ or any neighbor of $y$ in $R$, otherwise there exists a 5-cycle or a 6-cycle, respectively, containing $e_k$ as a chord, again a contradiction.  So together $x$ and $y$ can have at most $|V(R)|-2$ adjacencies in $R$. By Claim 1, we can bound the number of adjacencies from $\{a,b,x,y\}$ to $\mathcal{C}$.  These bounds together with the maximum number of possible adjacencies from $\{a,b,x,y\}$ to the vertices of the triangle $\{a,b,c\}$ yield

\begin{align*}
2(n+3k-2)\le 2\sigma_2(G)&\le deg_G(a)+deg_G(b)+deg_G(x)+deg_G(y)\\
&\le |V(R)|+(|V(R)|-2)+14r+16s+18t+8\\
&= 2(n-4r-5s-6t-3-1)+14r+16s+18t+8\\
&= 2n+6r+6s+6t\\
\Longrightarrow 6k-4&\le 6r+6s+6t=6(k-1)= 6k-6, \text{ a contradiction.}
\end{align*}  


{\bf Claim 2.} For a 4-cycle $C=a, b, c, d, a$, the nonadjacent pairs $(a, y)$ and $(b, x)$ have at most 14 edges to any chorded 4-cycle $C_i \in \mathcal{C}$, 16 edges to any chorded 5-cycle $C_i\in \mathcal{C}$, and 18 edges to any chorded 6-cycle $C_i\in \mathcal{C}$.  
\begin{proof}
First suppose $C_i$ is a chorded 4-cycle. Without loss of generality, if either $\deg_{C_i}(x)\le 2$ or $\deg_{C_i}(y)\le2$, or if $\deg_{C_i}(x)\le 3$ and $\deg_{C_i}(y)\le 3$ then we are done. So assume $x$ (or $y$) is adjacent to all of $C_i$.  If $a$ and $b$ have a common neighbor on $C_i$ other than an end-vertex of the chord $e_i$, say $v_i$, then $v_i$ completes a 5-cycle with $e_k$ as a chord and $x$ can replace $v_i$ on $C_i$, which completes the desired cycle set, a contradiction.  Therefore, $\deg_{C_i}(a,b)\le  6$ and $\deg_{C_i}(a, b, x, y)\le 14$. \\
\vspace{.25cm}

If $C_i$ is a 5-cycle, note that $x$ (and similarly, $y$) is not adjacent to both $a_i$ and $b_i$ otherwise a 4-cycle with $e_i$ as a chord would exist, contradicting (1).  Thus, $\deg_{C_i}(x, y)\le 8$.  Also note that if $a$ and $b$ have a common neighbor $w_i$ (or $v_i$), then there exists a 5-cycle with $e_k$ as a chord and $e_i$ is left on a triangle, contradicting (2).  Thus $\deg_{C_i}(a,b)\le 8$, which implies $\deg_{C_i}(a, b, x, y)\le 16$.\\
\vspace{.25cm}

If $C_i$ is a 6-cycle (of either type), then again $x$ (and similarly, $y$) cannot be adjacent to both $a_i$ and $b_i$ otherwise there would exist a 4 or 5-cycle (depending on the Type of $C_i$) containing $e_i$ as a chord, contradicting (1).  Therefore we have $\deg_{C_i}(x,y)\le 10$.  Also, if $a$ and $b$ have a common neighbor in $\{v_i, w_i, y_i, z_i\}$ then a chorded 5-cycle with $e_k$ as a chord exists, contradicting (1).  Thus, $\deg_{C_i}(a, b, x, y)\le 18$.


\end{proof}


Now suppose $C$ is a 4-cycle.  Note that $a$ and $b$ cannot share any neighbors in $R$, otherwise there would be a 5-cycle containing $e_k$ as a chord, which would complete the desired cycle set, a contradiction.  So the neighborhoods $N_R(a)$ and $N_R(b)$ must be disjoint sets.  Further, note that no neighbor of $a$ in $R$ can be adjacent to any neighbor $b$ in $R$, otherwise there exists a 6-cycle with $e_k$ as a chord, which is a contradiction as it completes the desired cycle set.  Therefore, since $x$ cannot be adjacent to itself nor any vertex in $N_R(b)$, we have $\deg_R(x)\le |V(R)|-1-|N_R(b)|$. Similarly, $\deg_R(y)\le |V(R)|-1-|N_R(a)|$.  Now we have 
\begin{align*}
\deg_R(a, b, x, y)&\le |N_R(a)|+|N_R(b)|+(|V(R)|-1-|N_R(b)|)\\&~~~~~~~~~~~~~~+(|V(R)|-1-|N_R(a)|)\\
&=2|V(R)|-2.
\end{align*}
By Claim 2, we can bound the number of adjacencies from $\{a,b,x,y\}$ to $\mathcal{C}$.  These bounds together with the maximum number of possible adjacencies from $\{a,b,x,y\}$ to the vertices of the 4-cycle $\{a,b,c,d\}$ yield

\begin{align*}
2(n+3k-2)&\le2\sigma_2(G)\\&\le deg_G(a)+deg_G(b)+deg_G(x)+deg_G(y)\\
&\le 2|V(R)|-2+14r+16s+18t+10\\
&= 2(n-4r-5s-6t-4-1)+14r+16s+18t+10\\
&= 2n+6r+6s+6t\\
\Longrightarrow 6k-4&\le 6r+6s+6t=6(k-1)= 6k-6, \text{ a contradiction.}
\end{align*}  


{\bf Claim 3.} For a 5-cycle $C=a, b, c, d, e, a$, the nonadjacent pairs $(a,y)$ and $(b,x)$ have at most 14 edges to any chorded 4-cycle in $\mathcal{C}$, 16 edges to any chorded 5-cycle in $\mathcal{C}$, and 18 edges to any chorded 6-cycle in $\mathcal{C}$.  

\begin{proof} 
First assume $C_i$ is a 4-cycle. If either $x$ or $y$ is adjacent to both ends of $e_i$, then we can rebuild $C_i$, again a 4-cycle, by replacing either $w_i$ or $y_i$ with either $x$ or $y$.   Further, if $a$ and $b$ have a common neighbor in $\{w_i, y_i\}$, then there exists a triangle with $e_k$ as an edge, contradicting (2). Therefore either $\deg_{C_i}(a, b)\le 6$ or $\deg_{C_i}(x,y)\le 6$, and in either case, we have $\deg_{C_i}(a, b, x, y)\le 14$.\\
\vspace{.25cm}

Now suppose $C_i$ is a 5-cycle.  Neither $x$ nor $y$ can be adjacent to both end-vertices of $e_i$, otherwise there exists a 4-cycle containing $e_i$ as a chord, contradicting (1), so $\deg_{C_i}(x)\le4$ and $\deg_{C_i}(y)\le 4$.  If $\deg_{C_i}(x)\le 3$ and $\deg_{C_i} (y)\le 3$, then we are done.  So without loss of generality, suppose $\deg_{C_i}(x)=4$ and $\deg_{C_i}(y)\le3$.  Again without loss of generality, assume $x$ is not adjacent to $a_i$.  If $a$ and $b$ are both adjacent to $v_i$ then $v_i$ can be used to complete a 6-cycle with $e_k$ as a chord, and $x$ can replace $v_i$ on the 5-cycle $C_i$ with chord $e_i$, thus completing the desired cycle set, a contradiction.  Therefore $\deg_{C_i}(a, b)\le 9$, so $\deg_{C_i}(a, b, x, y)\le 16$. Now suppose $\deg_{C_i}(x)=4=\deg_{C_i}(y)$.  If $x$ and $y$ each are adjacent to a different end-vertex of $e_i$, then either $w_i$ or $v_i$ can be replaced (by $x$ or $y$) on $C_i$ and thus $a$ and $b$ cannot both be adjacent to either $w_i$ or $v_i$.  Therefore $\deg_{C_i}(a, b)\le 8$, so $\deg_{C_i}(a, b, x, y)\le 16$. Instead suppose $x$ and $y$ are adjacent to the same end-vertex of $e_i$, without loss of generality, say $b_i$.  Then $v_i$ can be replaced by either $x$ or $y$ on the 5-cycle $C_i$ with chord $e_i$. Note that if both $a$ and $b$ are adjacent to $v_i$, then there exists a 6-cycle containing $e_k$ as a chord, thus completing the desired cycle set, a contradiction.  If both $a$ and $b$ are not adjacent to $v_i$ then we are done.  So suppose, without loss of generality, that $a$ is adjacent to $v_i$.  Now if $a$ and $b$ are both adjacent to $w_i$ then $a, v_i, y, b, w_i, a$ is a 5-cycle containing $e_k$ as a chord and $e_i$ is left on a triangle, contradicting (2).  Therefore, $a$ and $b$ cannot both be adjacent to $w_i$, so $\deg_{C_i}(a, b)\le 8$ and thus $\deg_{C_i}(a, b, x, y)\le 16$.\\
\vspace{.25cm}

Now assume $C_i$ is a Type I 6-cycle.  If $a$ and $b$ have a common neighbor in $\{v_i, w_i, y_i, z_i\}$, then a new chorded 6-cycle with chord $e_k$ is formed, which leaves $e_i$ on a 4-cycle, contradicting (2).  Thus, $\deg_{C_i}(a, b)\le 8$.  As above, $x$ and $y$ each must be nonadjacent to one of $\{a_i, b_i\}$, otherwise there is a shorter cycle with $e_i$ as a chord (which contradicts (1)), so $\deg_{C_i}(x, y)\le 10$ and therefore $\deg_{C_i}(a, b, x, y)\le 18$ holds.\\
\vspace{.25cm}

Lastly, instead suppose $C_i$ is a Type II 6-cycle.  If $a$ and $b$ have a common neighbor in $\{v_i, w_i, z_i\}$ then there exists a new 6-cycle with $e_k$ as a chord, and $e_i$ is left on a 3-cycle, contradicting (2).  Therefore, $\deg_{C_i}(a,b)\le 9$.  Neither $x$ nor $y$ can be adjacent to both end-vertices of $e_i$, otherwise there exists a 4-cycle with $e_i$ as a chord, contradicting (1).  If $\deg_{C_i}(x,y)=10$ then either $x$ and $y$ are adjacent to the same end-vertex of $e_i$, or $x$ and $y$ are adjacent to different end-vertices of $e_i$.  First, without loss of generality, suppose both $x$ and $y$ are adjacent to all of $C_i$ except for $b_i$.  Then $a_i, y, y_i, b_i, z_i, x, a_i$ is a Type I 6-cycle with $e_i$ as a chord, which contradicts (3).  Now, without loss of generality, assume $x$ is adjacent to all of $C_i$ except $b_i$ and $y$ is adjacent to all of $C_i$ except $a_i$.  Then $b_i, y_i, x, a_i, w_i, y, b_i$ is a Type II 6-cycle with $e_i$ as a chord, again contradicting (3).  Thus $\deg_{C_i}(a, b, x, y)\le 9+9=18$. 
\end{proof}

Now suppose $C$ is a 5-cycle.  Note that $a$ and $b$ cannot share any neighbors in $R$, otherwise there would be a 6-cycle containing $e_k$ as a chord, which would complete the desired cycle set, a contradiction. So the neighborhoods $N_R(a)$ and $N_R(b)$ must be disjoint sets.  Further, note that no neighbor of $a$ in $R$ can be adjacent to any neighbor $b$ in $R$, otherwise there exists a 4-cycle containing $e_k$, contradicting (2).  Therefore, since $x$ cannot be adjacent to itself nor any vertex in $N_R(b)$, we have $\deg_R(x)\le |V(R)|-1-|N_R(b)|$. Similarly, $\deg_R(y)\le |V(R)|-1-|N_R(a)|$.  Now we have 
\begin{align*}
\deg_R(a, b, x, y)&\le |N_R(a)|+|N_R(b)|+(|V(R)|-1-|N_R(b)|)\\&~~~~~~~~~~~~~~+(|V(R)|-1-|N_R(a)|)\\&=2|V(R)|-2.
\end{align*}

By Claim 3, we can bound the number of adjacencies from $\{a,b,x,y\}$ to $\mathcal{C}$.  These bounds together with the maximum number of possible adjacencies from $\{a,b,x,y\}$ to the vertices of the 5-cycle $\{a,b,c,d,e\}$ yield

\begin{align*}
2(n+3k-2)&\le2\sigma_2(G)\\&\le deg_G(a)+deg_G(b)+deg_G(x)+deg_G(y)\\
&\le 2|V(R)|-2+14r+16s+18t+12\\
&= 2(n-4r-5s-6t-5-1)+14r+16s+18t+12\\
&= 2n+6r+6s+6t\\
\Longrightarrow 6k-4&\le 6r+6s+6t=6(k-1)= 6k-6, \text{ a contradiction.}
\end{align*}   

This completes the proof. 
\end{proof}

\begin{corollary} Let $G$ be a graph of order $n\ge 9k-4$ for an integer $k\ge2$.  
If $$\delta(G)\ge \frac{n+3k-2}{2}$$ then for any $k$ independent edges 
$\{e_1, e_2, \ldots, e_k\}$ there exists a set of $k$ vertex disjoint 
cycles $\{C_1, C_2, \ldots, C_k\}$ such that $e_i$ is a chord of $C_i$ and 
$4\le|V(C_i)|\le 6$ for all $1\le i\le k$. 
\label{cor:del}
\end{corollary}

Based on Theorem \ref{thm:main} and Corollary \ref{for:del}, we make the following stronger conjecture.  

\begin{conjecture} 
Let $G$ be a graph of order $n\ge 6k+1$ for some integer $k\ge1$.  
If $$\sigma_2(G)\ge n+3k-2$$ then for any $k$ independent edges 
$\{e_1, e_2, \ldots, e_k\}$ there exists a set of $k$ vertex disjoint 
cycles $\{C_1, C_2, \ldots, C_k\}$ such that $e_i$ is a chord of $C_i$ and 
$4\le|V(C_i)|\le 6$ for all $1\le i\le k$. 
\end{conjecture}

Now we will focus on a minimum degree condition that will allow us to place edges along chorded cycles.

\subsection{Placing Edges on Chorded Cycles}

Before stating our next result, we describe a notation used in upcoming theorems.  


\vspace{1cm}
{\bf Notation:} If $c$ is a chord of the cycle $C_i$ then we denote this cycle with a chord as $C_i^c$.  Further, note that $E(C_i^c)=E(C_i)\cup \{c\}$. We will also use the notation $C_i^*$ to denote a cycle $C_i$ with two chords.\\
\vspace{.1in}

Next we establish a useful lemma.\\

\begin{lemma}
Let $G$ be a graph of order $n \geq 18k - 2$ (or $n\ge 18k+1$) for an integer $k\ge 1$ with minimum degree $$\delta(G)\ge \frac{n+2k-2}{2}.$$

If $G$ contains a set of $k$ vertex disjoint cycles ${\mathcal C}=\{C_1, C_2, \ldots, C_k\}$ containing a total of at 
most $6k-1$ (or $6k$) vertices, then for any triple of vertices $\{v_1, v_2, v_3 \}$ on any cycle
$C\in \mathcal{C}$, at least one pair of these vertices has a common neighbor 
in $A = G - \mathcal{C}$.
\label{lem:bigenough}
\end{lemma}

\begin{proof}  
We have that 
$b = | V ({\mathcal C}) | \leq 6k-1$.
Suppose for the vertices $v_1, v_2$ and $v_3$ in some cycle $C$ of $\mathcal{C}$, no pair of them has a common neighbor in $A$.  Then


\begin{align*}
3\left(\frac{n+2k-2}{2}\right)-3(b-1)&\le 3\delta(G)-3(b-1)\\&\le \deg_A(v_1)+\deg_A(v_2)+\deg_A(v_3)\le n-b,\\
n&\le 4b-6k\\
&\le 4(6k-1)-6k\\
&=18k-4, \text{ a contradiction.}
\end{align*}

%\begin{align*}
%d(v_1)+d(v_2)+d(v_3)\ge 3\delta(G)=3\left(\frac{n+2k-2}{2}\right)-3(b-1)&\ge n-b+1,\\
%\frac{n}{2}&\ge 2b-3k+4-3,\\
%n&\ge 4b-6k+2\\n &\ge 4(6k-1)-6k+2,\\
%n&\ge 18k-2.  
%\end{align*}  

Hence, some pair of the set $\{v_1, v_2, v_3\}$ has a common neighbor in $A$.  A similar argument holds when $n\ge 18k+1$ and $|V(\mathcal{C})|\le 6k$.  

\end{proof}


We are now ready to extend Theorem {\ref{thm:Egawa+}} to chorded cycles. In our first such result, the specified edges are either chords or cycle-edges on the vertex disjoint chorded cycles.  

\begin{theorem}
Let $G$ be a graph of order $n\ge18k-2$ for an integer  
$k\ge2$ and let $\{e_1, e_2, \ldots, e_k\}$ be a set of $k$ independent edges 
in $G$.  If $$\delta(G)\ge\frac{n+2k-2}{2},$$ then there exists a system 
of $k$ vertex disjoint chorded cycles 
$\{C_1^{c_1}, C_2^{c_2}, \ldots, C_k^{c_k}\}$ such that 
$e_i\in E(C_i^{c_i})$ and $|V(C_i^{c_i})|\le6$ for all $1\le i\le k$. 
\label{thm:kedgesomewhere}
\end{theorem}

\begin{proof}
Theorem \ref{thm:Egawa+} implies that in $G$ there is a set of $k$ 
vertex disjoint cycles $\mathcal{C}=\{C_1, C_2, \ldots, C_k\}$, such that 
$e_i\in E(C_i)$ and $|C_i|\le 4$ for all $1\le i\le k$.  %Say there are $t$ 
%disjoint 3-cycles and $r=k-t$ disjoint 4-cycles in $\mathcal{C}$.  
Let $\displaystyle A=G-\mathcal{C}$. Note that for any three vertices of $C_i$, some pair of these vertices must have a common neighbor in $A$ by Lemma \ref{lem:bigenough}.\\
\vspace{.1in}
{\it Case 1:} Suppose $e_i=v_1 v_3$ is an edge of a 3-cycle 
$C_i=v_1, v_2, v_3, v_1$. If $v_2$ and $v_3$ or $v_1$ and $v_2$ share a 
common neighbor in $A$ then there exists a chorded 4-cycle $C_i^*$ with 
$e_i\in E(C_i^{c_i})$ such that $C_i^{c_i}$ has a chord, 
$c_i = v_2v_3$ or $v_1v_2$.  
If $v_1$ and $v_3$ have a common neighbor in $A$ then $e_i$ is the 
chord of a 4-cycle.  \\
\vspace{.1in}
{\it Case 2:} Now suppose $e_j=v_1 v_2$ is an edge of a 4-cycle 
$C_j=v_1, v_2, v_3, v_4, v_1$. Consider the vertex set $\{v_1, v_3, v_4\}$.  By Lemma \ref{lem:bigenough}, the set of 
vertices $\{v_1, v_3, v_4\}$ contains a pair of vertices with a common neighbor in $A$.  
If $v_1$ and $v_4$ or $v_3$ and $v_4$ have a common neighbor in $A$ then 
there is a chorded 5-cycle $C_j^*$ with $e_j\in E(C_j^*)$.  
If $v_1, v_3$ is the pair with a common neighbor in $A$, say $u$, 
then we repeat the argument using the set of vertices $\{v_2, v_3, v_4\}$: 
if either $v_2, v_3$ or $v_3, v_4$ is the pair that has a common adjacency 
in $A$ then we have a chorded 5-cycle with $e_j$ as an edge of the cycle.  
If $v_2, v_4$ is the pair with the common neighbor in $A$, say $v$, 
then $v_1, v_4, v, v_2, v_3, u, v_1$ is a 6-cycle with $e_j$ as a chord. \\
\vspace{.1in}
%To show that at the last possible step there are still enough vertices to guarantee a pair of vertices must have a common neighbor in $A$, first let $\mathcal{C}=C_1^{c_1}, \ldots C_k^{c_k}$ be the set of cycles that has been built so far.  Let $\mathcal{A}=G-\mathcal{C}$ and $b=|C_1^{c_1}|+\ldots +|C_k^{c_k}|$.   Note that at this stage of construction, given $v_1, v_2, v_3\in V(C_k)$, we have that $b \leq 6k-1$.   
By applying Lemma \ref{lem:bigenough} repeatedly for each $C_i$, we obtain the desired system of $k$ vertex disjoint chorded cycles with $e_i$ as an edge or chord of $C_i$ for all $1\le i\le k$. 

\end{proof}

Using a similar technique, we obtain a stronger result where each $e_i$ is a cycle-edge, not a chord.    

\begin{theorem}
Let $G$ be a graph of order $n\ge 18k-2$ for an integer $k\ge2$ and let $\{e_1, e_2, \ldots, e_k\}$ be a set of independent edges in $G$.  If $$\delta(G)\ge\frac{n+2k-2}{2},$$ then there exists a set of $k$ vertex disjoint chorded cycles $\{C_1^{c_1}, C_2^{c_2}, \ldots, C_k^{c_k}\}$ with $e_i\in E(C_i)$, $ e_i\neq c_i$, and $|V(C_i)|\le 6$ for all $1\le i\le k$.
\label{thm:kedgeson}
\end{theorem}


\begin{proof}
Again Theorem \ref{thm:Egawa+}  implies that there exists a set of 
$k$ vertex disjoint cycles $\{C_1, C_2, \ldots, C_k\}$ in $G$ with $|V(C_i)|\le 4$ and $e_i\in E(C_i)$ 
for all $1\le i\le k$.  
Let $A=G-\bigcup_{i=1}^k V(C_i)$.\\
\vspace{.1in}
{\it Case 1}: Suppose $C_i=v_1, v_2, v_3, v_1$ and $e_i=v_1 v_3$. 
By Lemma \ref{lem:bigenough}, we know that either the pair 
$\{v_1, v_2\}$,$ \{v_2, v_3\}$, or $\{v_1, v_3\}$ must share a common 
neighbor in $A$, say $x$.  
If $v_1$ and $v_2$ or $v_2$ and $v_3$ have a common neighbor in $A$ 
then there is a chorded 4-cycle with $e_i$ as an edge on the cycle. 
If $v_1$ and $v_3$ share the common neighbor $x\in A$, then $x, v_1, v_2, v_3, x$ is a chorded 4-cycle with $e_i$ as a chord.  
Now consider the triple $\{x, v_2, v_3\}$.  Again by Lemma \ref{lem:bigenough},
either $x$ and $v_2$, $x$ and $v_3$, or $v_2$ and $v_3$ must share a common 
neighbor, say $y\in A$.  
If $x$ and $v_2$ are both adjacent to $y\in A$ 
then $x, v_1, v_3, v_2, y, x$ is a chorded 5-cycle with $e_i$ as an 
edge of the cycle and $v_1 v_2$ as a chord.  
Either of the remaining pairs yields the same case, so without loss of 
generality if $x$ and $v_3$ are both adjacent to some $y\in A$ then 
$x, y, v_3, v_1, x$ is a chorded 4-cycle with $e_i$ as an edge of the cycle
and $x v_3$ as a chord. 
So if $C_i$ is a 3-cycle, we can always find a chorded 4 or 5-cycle with 
$e_i$ as an edge of the cycle, provided the common neighbor exists in $A$. \\
\vspace{.1in}
{\it Case 2}:  Suppose $C_j=v_1, v_2, v_3, v_4, v_1$ and $e_j=v_1 v_2$.  
Consider the triple $\{v_2, v_3, v_4\}$.  
By Lemma \ref{lem:bigenough},  one of the pairs in the triple shares a 
common neighbor, say $x\in A$. If $v_2$ and $v_3$ are both adjacent to $x$ 
then $v_1, v_2, x, v_3, v_4, v_1$ is a chorded 5-cycle with $e_j$ as an 
edge of the cycle and $v_2 v_3$ as a chord.   
If $v_3$ and $v_4$ are both adjacent to $x\in A$ then 
$v_1, v_2, v_3, x, v_4, v_1$ is a chorded 5-cycle with $e_j$ as a cycle edge
and $v_3 v_4$ as a chord.  
If $v_2$ and $v_4$ share a neighbor $x\in A$ then we need to consider 
the pairs of another triple: $\{x, v_2, v_3\}$.  
We have already checked the case where $v_2$ and $v_3$ share a neighbor in $A$.
If $x$ and $v_2$ are both adjacent to some $y\in A$ then 
$v_1, v_2, y, x, v_4, v_1$ is a chorded 5-cycle with $e_j$ as a cycle edge
and $x v_2$ as a chord.  
If instead $x$ and $v_3$ share a neighbor $y\in A$ then 
$v_1, v_2, v_3, y, x, v_4, v_1$ is a chorded 6-cycle with $e_j$ as a cycle 
edge and $v_3 v_4$ as a chord.
So if $C_j$ is a 4-cycle then there exists a chorded 5 or 6-cycle with $e_j$ 
as a cycle edge, provided the common neighbor exists in $A$. \\
\vspace{.1in}
By applying Lemma \ref{lem:bigenough} repeatedly to each $C_i$, we have the desired system of vertex disjoint chorded cycles.

\end{proof}

{\bf Note:} If $n$ is even, the two preceding results are sharp.  To see this, 
consider the graph $G$, of the set of edges $E=\{e_1, \ldots, e_{k-1}\}$ and 
two $K_{\frac{n-2k+2}{2}}$ cliques, each of which is completely adjacent to 
all vertices $V(E)$ and the edge $e_k$ has one end-vertex in each of the 
cliques.  
In this graph, the minimum degree 
$\delta(G)=\frac{n-2k+2}{2}-1+2(k-1)=\frac{n}{2}+k-2$.  However, $e_k$ lies on no chorded cycle disjoint from the edges of $E$.  \\

\vspace{.1in}

We can extend the process used in the proofs of 
Theorems \ref{thm:kedgesomewhere} and \ref{thm:kedgeson} to 
prove the following result.  

\begin{theorem} 
Let $G$ be a graph of order $n\ge 18k-2$ for  an integer $k\ge2$ and let 
$\{e_1, e_2, \ldots, e_k\}$ be a set of independent edges in $G$.  
If $$\delta(G)\ge \frac{n+2k-2}{2},$$ then there exists a set of $k$ 
vertex disjoint doubly chorded cycles $C_1^*, C_2^*, \ldots, C_k^*$ with 
$e_i\in E(C_i)$ and $|V(C_i)|\le 6$ for all $i$.  
\label{thm:dccedgeson}
\end{theorem}

\begin{proof} From Theorem \ref{thm:Egawa+}, we know we can place each 
edge $e_i$ on a 3-cycle or 4-cycle.   By the degree condition, for any 
set of three vertices we know from Lemma \ref{lem:bigenough} that at least 
one pair of vertices in that set must have a common neighbor not in any 
other cycle.  We must consider the following three cases: 
$e_i$ is a cycle-edge of a chorded 4-cycle, a chord of a 4-cycle, 
or an edge of a chordless 4-cycle. Let $\mathcal{C}=\{C_1, C_2, \ldots, C_k\}$ be this collection of cycles, and let $A=G-\mathcal{C}$. \\
\vspace{.2in}

{\it Case 1:} Suppose $e_i\in E(G)$ is a non-chord of the chorded 4-cycle $v_1, v_2, v_3, v_4, v_1$.  Without loss of generality, assume $e_i=v_1 v_2$ and $v_1 v_3$ is a chord.  Now consider the set of vertices $\{v_2, v_3, v_4\}$.  Some pair in this set must have a common neighbor in $A$, say $x$.  If $x$ is a common neighbor of $v_2$ and $v_3$ then $v_1, v_2, x, v_3, v_4, v_1$ is a doubly chorded 5-cycle with $e_i$ as an edge and $v_1 v_3$ and $v_2 v_3$ as chords.  If instead $v_3$ and $v_4$ have a common neighbor $x$, then $v_1, v_2, v_3, x, v_4, v_1$ is a 5-cycle with $e_i$ as an edge and $v_1v_3$ and $v_3 v_4$ as chords.  If $v_2$ and $v_4$ have the common neighbor $x$, then $x, v_2, v_1, v_3, v_4, x$ is a 5-cycle containing $e_i$ as a cycle edge and $v_2 v_3$ and $v_1 v_4$ as chords. \\

\vspace{.2in}

{\it Case 2:} Suppose $e_i=v_1 v_3$ is the chord of a 4-cycle, 
$v_1, v_2, v_3, v_4, v_1$.  Again consider the set of vertices $\{v_2, v_3, v_4\}$.  
One pair of this set must share a common neighbor in $A$, say $x$. \\
\vspace{.1in} 

{\it Case 2a:}  If $x$ is a common neighbor of $v_2$ and $v_3$ (or, by symmetry, $v_3$ and $v_4$), then 
$v_1, v_2, x, v_3, v_4, v_1$ is a $C_5$ containing $e_i=v_1 v_3$ and $v_2 v_3$ 
as chords. Since there is no doubly chorded cycle with $e_i$ as a cycle edge, 
consider the set $\{v_1, v_2, x\}$.  If $v_1$ and $v_2$ have a common 
neighbor $y$, then $v_1, y, v_2, x, v_3, v_1$ is a 5-cycle containing $e_i$ as a 
cycle edge and $v_1 v_2$ and $v_2 v_3$ as chords.  
If $v_2$ and $x$ share $y$ as a neighbor, then $v_1, v_2, y, x, v_3, v_1$ is 
a 5-cycle with $e_i$ as a cycle edge and $v_2 x$ and $v_2 v_3$ as chords. 
If $v_1$ and $x$ share $y$ as a neighbor, then $v_1, y, x, v_2, v_3, v_1$ 
is a 5-cycle with $e_i$ as an edge and $v_1 v_2$ and $v_3 x$ as chords. \\
\vspace{.1in} 


%{\it Case 2b:}  If instead $v_3$ and $v_4$ share $x$ as a common neighbor then $v_1, v_2, v_3, x, v_4, v_1$ is a 5-cycle containing $e_i$ and $v_3 v_4$ as chords.  Again since there is no doubly chorded cycle with $e_i$ as a non-chord edge, consider the set $\{v_1, v_4, x\}$.  If $v_1$ and $v_4$ share $y$ as a neighbor, then $v_1, v_3, x, v_4, y, v_1$ is a 5-cycle with $e_i$ as an edge and $v_1 v_4$ and $v_3v_4$ as chords.  If $v_4$ and $x$ share $y$ as a neighbor, then $v_1, v_3, x, y, v_4, v_1$ is a 5-cycle containing $e_i$ as an edge and $v_3 v_4$ and $v_4 x$ as chords.  If $v_1$ and $x$ have $y$ as a common neighbor, then $v_1, v_3, v_4, x, y, v_1$ is a 5-cycle containing $e_i$ as an edge and $v_1 v_4$ and $v_3 x$ as chords. \\
%\vspace{.1in} 

{\it Case 2b:}  If instead $v_2$ and $v_4$ have a common neighbor $x$, then 
$x, v_2, v_3, v_1, v_4, x$ is a doubly chorded 5-cycle with $e_i$ as an edge 
and $v_1 v_2$ and $v_3 v_4$ as chords.  
This completes the cases when $e_i$ is the chord of a chorded 4-cycle.  \\
\vspace{.2in}
Next we suppose we start with $e_i$ as an edge of a 4-cycle without a chord. \\

\vspace{.2in}
{\it Case 3:} Suppose $e_i=v_1 v_2$ is initially an edge of the chordless 4-cycle
$v_1, v_2, v_3, v_4, v_1$.  Consider the set $\{v_2, v_3, v_4\}$.  
Then one of the following must occur: $v_2$ and $v_3$ share a common neighbor 
$x$ in $A$ or $v_3$ and $v_4$ share a common neighbor $x$, or $v_2$ and $v_4$ 
share $x$ as a neighbor.   \\

\vspace{.1in}

{\it Case 3a:} Suppose $v_2$ and $v_3$ share $x$ as a neighbor.  There is 
no doubly chorded cycle, so consider the set $\{v_3, v_4, x\}$. 
At least one pair in that set must have a common neighbor in $A$, say $y$. 
If $v_3$ and $v_4$ share $y$ as a common neighbor, then 
$v_1, v_2, x, v_3, y, v_4, v_1$ is a 6-cycle containing $e_i$ as an edge and 
$v_2 v_3$ and $v_3 v_4$ as chords.  If $v_4$ and $x$ share $y$ as a neighbor, 
then $v_1, v_2, v_3, x, y, v_4, v_1$ is a 6-cycle containing $e_i$ as an edge 
and $v_2 x$ and $v_3 v_4$ as chords.  If $v_3$ and $x$ have $y$ as a 
common neighbor, then $v_1, v_2, x, y, v_3, v_4, v_1$ is a 6-cycle 
containing $e_i$ as an edge and $v_2 v_3$ and $v_3 x$ as chords.  

\vspace{.1in}

{\it Case 3b:} Suppose $v_3$ and $v_4$ share $x$ as a neighbor.  Again
there is no doubly chorded cycle yet.   Consider the set of vertices 
$\{v_2, v_3, x\}$.  By Lemma \ref{lem:bigenough}, at least one pair in the 
set must have a common neighbor in $A$, say $y$.  If $v_2$ and $v_3$ have $y$ as a 
common neighbor, then $v_1, v_2, y, v_3, x, v_4, v_1$ is a 6-cycle with 
$e_i$ as an edge and $v_2 v_3$ and $v_3 v_4$ as chords.  
If $v_3$ and $x$ share $y$ as a common neighbor, then 
$v_1, v_2, v_3, y, x, v_4, v_1$ is a 6-cycle containing $e_i$ as an edge 
and $v_3 v_4$ and $v_3 x$ as chords.  
If $v_2$ and $x$ share $y$ as a neighbor, then $v_1, v_2, y, x, v_3, v_4, v_1$
is a 6-cycle containing $e_i$ as an edge and $v_2 v_3$ and $v_4 x$ as chords.  
 
 \vspace{.1in}
 
{\it Case 3c:} Suppose $v_2$ and $v_4$ share $x$ as a neighbor.  
Since there are no doubly chorded cycles, consider the vertex set 
$\{v_2, v_3, x\}$.  Again, at least one pair in this triple must have a 
common neighbor in $A$, say $y$. \\
 
\vspace{.1in}
 
If $v_2$ and $v_3$ share $y$ as a neighbor, there are still no doubly chorded 
cycles, so consider the set $\{v_3, v_4, y\}$.  If $v_3$ and $v_4$ have a 
common neighbor $z$ in $A$, then, $v_1, v_2, y, v_3, z, v_4, v_1$ is a 6-cycle 
with $e_i$ as an edge and $v_2 v_3$ and $v_3 v_4$ as chords.  
If $v_4$ and $y$ share $z$ as a neighbor, then $v_1, v_2, v_3, y, z, v_4, v_1$
is a 6-cycle containing $e_i$ as an edge and $v_2 y$ and $v_3 v_4$ as chords.  
If $z$ is a common neighbor of $v_3$ and $y$ then $v_1, v_2, y, z, v_3, v_4, v_1$
is a 6-cycle with $e_i$ as an edge and $v_2 v_3$ and $v_3 y$ as chords.  This completes the case when $v_2$ and $v_3$ are adjacent to $y$.\\

\vspace{.1in}

If $v_3$ and $x$ share $y$ as a neighbor, then $v_1, v_2, x, y, v_3, v_4, v_1$
is a 6-cycle with $e_i$ as en edge and $v_2 v_3$ and $v_4 x$ as chords.\\

\vspace{.1in}

If instead $v_2$ and $x$ share $y$ as a neighbor, then there are still 
no doubly chorded cycles containing $e_i$ as an edge, so consider the set 
of vertices $\{v_1, v_4, x\}$.  
At least one pair of these vertices must have a common neighbor, say $z$ in $A$.  
If $z$ is a common neighbor of $v_1$ and $v_4$, then 
$v_1, v_2, y, x, v_4, z, v_1$ is a 6-cycle with $e_i$ as an edge and 
$v_1 v_4$ and $v_2 x$ as chords.  
If $v_4$ and $x$ have $z$ as a common neighbor, then 
$v_1, v_2, y, x, z, v_4, v_1$ is a 6-cycle containing $e_i$ as an edge 
and $v_2 x$ and $v_4 x$ as chords.  
If $v_1$ and $x$ share $z$ as a neighbor, then $v_1, v_2, v_3, v_4, x, z, v_1$
is a 6-cycle containing $e_i$ as a cycle edge and $v_1 v_4$ and $v_2 x$ 
as chords.  
 
\vspace{.1in}
 
By applying Lemma \ref{lem:bigenough} repeatedly to each $C_i$, we have the desired system of vertex disjoint doubly chorded cycles.  This completes the proof.  
\end{proof}

This concludes our results on placing edges on chorded cycles.  In the following section, we place vertices on chorded cycles instead of edges. 

\subsection{Placing Vertices on Chorded Cycles}

Next, we extend Theorem \ref{thm:kvertsoncyc}  to chorded cycles.
 
\begin{theorem}
Let $G$ be a graph of order $n\ge 16k-12$ for an integer $k\ge 1$.  
If $$\delta(G)\ge\frac{n}{2},$$ then for any set of $k$ vertices in $G$, 
$\{v_1, v_2, \ldots, v_k\}$, there exists a collection of $k$ vertex disjoint 
chorded cycles $\{C_1, C_2, \ldots, C_k\}$ such that $v_i\in V(C_i)$ 
and $|V(C_i)|\le 6$ for $1\le i\le k$. 
\label{thm:kvertsonchcyc}
\end{theorem}

\begin{proof} For the sake of contradiction, suppose not.  
Let $\{v_1, v_2, \ldots, v_k\}$ be a set of vertices in the graph $G$, 
a maximal counterexample.  Choose an admissible collection of $k-1$ vertex disjoint chorded cycles in $G$, $\mathcal{C}=\{C_1, C_2, \ldots, C_{k-1}\}$, such that $v_k\not\in\cup_{i=1}^{k-1}V(C_i)$ with: 

\begin{enumerate}
\item $\displaystyle\sum_{i=1}^{k-1}|V(C_i)|$ is a minimum, and
\item $\displaystyle v_i\in V(C_i)$, for $i=1, 2, \ldots, k-1$. 
\end{enumerate}

Let $H=G-\mathcal{C}$.\\
Note: 
\vspace*{-.2in}
\begin{align*}
           |H| & =|G|-|\mathcal{C}|\\
                 & \ge n-6(k-1), \hspace{.1cm}\text{since each cycle is at most a 6-cycle}\\
                 & \ge(16k-12)-6k+6 \\
                 & =10k-6\\
                 & \ge 4, \hspace{.1cm}\text{since $k\ge 1$.}
              \end{align*}
            
Thus there are at least 4 vertices in $H$. 
\begin{lemma} For any $h\in V(H)$, $deg_{C_i}(h)\le 4$ for all $i$. 
\label{lem:atmostfour}
\end{lemma}
\begin{proof} For the sake of contradiction, suppose $deg_{C_i}(h)=5$ for some $i$ and some $h\in V(H)$.\\
\vspace{.1in}

{\it Case 1:} Suppose $C_i=w_1, w_2, w_3, w_4, w_5, w_6, w_1$  is a 6-cycle and $h\in V(H)$ such that $h \neq v_k$.  Without loss of generality, let $h$ be adjacent to $w_1, w_2, w_3, w_4,$ and $w_5$.  First suppose $v_{i}=w_j$ for some $j\in \{1,2,3,4,5\}$.  If $j=1$, then the 5-cycle $h, w_1, w_2, w_3, w_4, h$ contains $v_{i}=w_1$ and has the chord $h w_2$, contradicting the choice of $\mathcal{C}$, specifically the minimality of $\sum_{i=1}^{k-1} |V(C_i)|$.  Similarly, if $j=2, 3, 4,$ or $5$ then the 5-cycle $h, w_2, w_3, w_4, w_5, h$ contains $v_{i}=w_j$ and has the chord $h w_3$, again contradicting the choice of $\mathcal{C}$.  Now suppose $j=6$, that is, $v_{i}= w_6$.  Then $h, w_5, w_6, w_1, w_2, h$ is a 5-cycle containing $v_{i}$ with the chord $h w_1$, contradicting the choice of $\mathcal{C}$.\\
%\vspace{2in} 
%\begin{center}
%\begin{figure}[ht!]
%\includegraphics[width=50mm]{L13.jpg}
%\label{overflow}
%\end{figure}
%\hspace{.2in}
%\begin{center}
%{\bf Figure 2.}
%\end{center}
%\end{figure}

%\begin{figure}[ht!]
%\includegraphics[width=50mm]{L14.jpg}
%\caption{A simple caption}
%\label{overflow}
%\hspace{.2in}
%\begin{center}
%{\bf Figure 3.}
%\end{center}
%\end{figure}
%\end{center}

%\begin{figure}[ht!]
%\includegraphics[width=50mm]{L15.jpg}
%\caption{A simple caption}
%\label{overflow}
%\end{figure}
%\hspace{.2in}
%\begin{center}
%{\bf Figure 4.}
%\end{center}
%\end{figure}


%\begin{figure}[ht!]
%\includegraphics[width=50mm]{L16.jpg}
%\caption{A simple caption}
%\label{overflow}
%\hspace{.2in}
%\begin{center}
%{\bf Figure 5.}
%\end{center}
%\end{figure}

\vspace{.1in}

{\it Case 2:} Again suppose $C_i=w_1, w_2, w_3, w_4, w_5, w_6, w_1$ is a 6-cycle, but now suppose $h= v_k$. Without loss of generality, assume $h=v_k$ is adjacent to $w_1, w_2, w_3, w_4,$ and $w_5$.  If $v_i=w_1, w_2,$ or $w_6$, then $h, w_3, w_4, w_5, h$ is a 4-cycle containing $v_k$ with $w_4h$ as a chord.  This contradicts the minimality of the size of the cycles in $\mathcal{C}$.  If $v_i=w_4$ or $w_5$ then $h, w_1, w_2, w_3, h$ is a 4-cycle containing $v_k$ with $w_2h$ as a chord.  Again, this contradicts the choice of $\mathcal{C}$.  If $v_i=w_3$, then $h, w_4, w_5, w_6,w_1, h$ is a 5-cycle containing $v_k$ and not containing $v_i$, with $w_5h$ as a chord, again contradicting the choice of $\mathcal{C}$. 


%\begin{figure}[ht!]
%\includegraphics[width=80mm]{Lhvk.jpg}
%\caption{A simple caption}
%\label{overflow}
%\end{figure}


\vspace{.1in}
{\it Case 3:} Suppose $C_i=w_1, w_2, w_3, w_4, w_5, w_1$ is a 5-cycle and $h\neq v_k$.  Then $h$ must be adjacent to all of $V(C_i)$.  Without loss of generality, assume $v_i=w_1$.  Then $h, w_5, w_1, w_2, h$ is a 4-cycle containing $v_i$ that has $w_1 h$ as a chord.  This chorded 4-cycle contradicts the minimality of the order of the chosen collection of cycles, $\mathcal{C}$.  





%\begin{center}
%\begin{tikzpicture}
 % [scale=.8,auto=left,every node/.style={circle,fill=blue!20}]
 % \node (n1) at (10,10) {$v_i$};
 % \node (n2) at (13,8)  {$v_i^+$};
 % \node (n3) at (11.5,5)  {};
 % \node (n4) at (8.5,5) {};
 % \node (n5) at (7,8)  {$v_i^-$};
  
 % \node (n6) at (18,9) {h};
 % \node (n7) at (18,8)  {};
 % \node (n8) at (18,7)  {};
 % \node (n9) at (18,5) {$v_k$};
  
 % \node at (10, 7){Chord};
  
 % \draw [dotted, thick] (18, 6.5) -- (18,5.8);

 % \foreach \from/\to in {n1/n2,n2/n3,n3/n4,n4/n5,n5/n1,n6/n1,n6/n2,n6/n3,n6/n4,n6/n5}
  %  \draw (\from) -- (\to);
    
    

%\end{tikzpicture}
%\end{center}
%vspace{.3in}

%\begin{figure}[ht!]
%\includegraphics[width=80mm]{L5.jpg}
%\caption{A simple caption}
%\label{overflow}

%\end{figure}


\vspace{.1in}
{\it Case 4:} Suppose $C_i=w_1, w_2, w_3, w_4, w_5, w_1$ is a 5-cycle and $h=v_k$.  Again, $h$ must be adjacent to all of $V(C_i)$.  Without loss of generality, assume $v_i=w_1$.  Then $h, w_2, w_3, w_4, h$ is a 4-cycle containing the vertex $v_k$ and the chord $w_3h$.  This chorded 4-cycle contradicts the minimality of the order of the chosen collection of cycles, $\mathcal{C}$. \\

\vspace{.1in}

%\begin{center}
%\begin{figure}[ht!]
%\includegraphics[width=80mm]{L5hvk.jpg}
%\caption{A simple caption}
%\label{overflow}
%\end{figure}
%\end{center}


This completes the proof of the lemma.  

\end{proof}

Now, $\delta(G)\ge\frac{n}{2}\ge8k-1$ and $\deg_{\mathcal{C}}(v_k)\le4(k-1)$, so $\deg_H(v_k)\ge 4k+3>3$ for all $k\ge 1$.  
Consider $u_1, u_2, u_3\in N_H(v_k)$. Then Lemma \ref{lem:atmostfour} implies 

\begin{center}
 $\displaystyle\sum_{m=1}^3 \deg_{C_i}(u_m)\le12$, for $1\le i\le k-1,$\\
 \end{center}
 which implies
 $$ \displaystyle\sum_{m=1}^3 \deg_L(u_m)\le 12(k-1).$$

 
 Let $r_j$ be the number of cycles, $C_i$, such that $\deg_{C_i}(v_k)=j$.  Then $r_0+r_1+r_2+r_3+r_4=k-1.$ 
 \begin{align*}
 \deg_L(v_k)&= 4r_4+3r_3+2r_2+r_1\\
                 &=(k-1)+3r_4+2r_3+r_2-r_0.
 \end{align*}
 
 We know that \begin{equation}
 \deg_H(v_k)\ge \delta(G)-[(k-1)+3r_4+2r_3+r_2-r_0].
 \end{equation}
 
 For any $u\in V(H)$, $\deg_L(u)\le 4(k-1)$. So on average, \begin{equation}
 \bar{d}_H(u)\ge \delta(G)-4(k-1).
 \end{equation}


Now consider $u_1, u_2, u_3\in N_H(v_k)$.  There is at most one edge among these vertices, otherwise there is a chorded 4-cycle containing $v_k$ in $H$ and we're done.  So we will consider the different possible neighborhoods of $\{u_1, u_2, u_3\}$ in $H-\{v_k\}$.\\

\vspace{.1in}


 {\it Case 1:} Suppose $v_k$ has at least two neighbors in $\{u_1, u_2, u_3\}$ with disjoint neighborhoods in $H-\{v_k\}$. Therefore Equations (1) and (2) yield that the order of $H$ is\begin{align*}
|V(H)|&\ge \deg_H(v_k)+1+2(\delta(G)-4(k-1))-2\\
	 &\ge \delta(G)-k+1-3r_4+2r_3-r_2+r_0+1+2\delta(G)-8k+8-2\\
	 &=3\delta(G)-9k+8-3r_4-2r_3-r_2+r_0\\
	 &\ge3\delta(G)-9k+8-3r_4-2r_3-r_2\\
	 &\ge3\delta(G)-9k+8-3(r_4+r_3+r_2+r_1+r_0)\\
	 &=3\delta(G)-9k+8-3(k-1).\\
	\text{Hence, }  |V(H)|&\ge3\delta(G)-12k+11.
\end{align*}
Similarly, we have that the order of $G$ is\begin{align*}
 n&=|V(H)|+|V(L)|\\
  &\ge 3\delta(G)-12k+11+4(k-1)\\ %\text{since each of the chorded cycles must be at least a 4-cycle}\\
  &\displaystyle\ge 3\left(\frac{n}{2}\right)+12k+11+4k-4\\
  &=\left(\frac{3}{2}\right)n-8k+7.\\
 \text{Thus, } 0 &\ge \left(\frac{1}{2}\right)n-8k+7, \text{ and hence,}\\
  n &\le 16k-14,\hspace{.1cm} \text{a contradiction of the order of $G$.}
\end{align*}

{\it Case 2:} Suppose there is one edge in the graph induced by $\{u_1, u_2, u_3\}$ and at least two pairs from $\{u_1, u_2\}$, $\{u_2, u_3\}$,  and $\{u_1, u_3\}$ share a distinct common neighbor in $H-\{v_k\}$. Without loss of generality, one of the following scenarios must occur. There is either a chorded 4-cycle or a chorded 5-cycle in $H$ containing $v_k$, and we're done. \\

\vspace{.1in}

{\it Case 3:} Suppose the pairs $\{u_1, u_2\}$, $\{u_2, u_3\}$,  and $\{u_1, u_3\}$ each have at least one distinct common neighbor in $H-\{v_k\}$.  Then we have\\

There is a chorded 6-cycle in $H$ containing $v_k$, and we're done.\\
\vspace{.1in}

 {\it Case 4:} Suppose the vertices $u_1, u_2$, and $u_3$ all share exactly one common neighbor in $H-\{v_k\}$. Then the order of $H$ is \begin{align*}
 |V(H)|&\ge \deg_H(v_k)+1+3(\delta(G)-4(k-1))-1-3\\
                                                               		    &=\delta(G)-k+1-3r_4-2r_3-r_2+r_0+3\delta(G)-12k+12-1+3\\
		         						    &=4\delta(G)-13k+9-3r_4-2r_3-r_2+r_0\\
								    &\ge 4\delta(G)-13k+9-3r_4-2r_3-r_2\\
								    &\ge4\delta(G)-13k+9-3(r_4+r_3+r_2+r_1+r_0)\\
								    &=4\delta(G)-13k+9-3(k-1)\\
								    &=4\delta(G)-16k+12.		    
\end{align*}
Similarly, the order of $G$ is \begin{align*}
n&=|V(H)|+|V(L)|\\
          						     &\ge 4\delta(G)-16k+12+4(k-1)\\
						              &\ge 4\left(\frac{n}{2}\right)-16k+12+4k-4.\\
						             \text{Hence } n&=2n-12k+8, \text{ and thus,}\\
						              n&\le 12k-8,
						              \hspace{.1cm}\text{a contradiction of the order of $G$.}			 \end{align*}
						     
						             
			 

This completes the proof of the theorem.





\end{proof} 




%\begin{corollary}
%The above set of doubly chorded independent cycles can be extended 
%to span $V(G)$.
%\end{corollary}

%\begin{proof}   Apply the Theorem to get the doubly chorded cycles and
%apply Theorem \ref{thm:span} to show they can be extended to span. 
%\end{proof}

Next we will show that under sufficient minimum degree conditions, the disjoint
cycle systems in some of the previous theorems can be extended to a 2-factor of the graph, that is, a 
set of vertex disjoint cycles that spans $V(G)$.  First, we need the following lemma.

\begin{lemma} If $G$ is a graph of order $n\ge 2k+2$ for an integer $k\ge1$, and $\displaystyle\delta(G)\ge\frac{n+2k-2}{2}$, then $G$ is at least $2k$-connected.  
\end{lemma}
\label{lem:2kconn}

\begin{proof}  Consider two vertices $x$ and $y\in V(G)$ and let $H=G-\{x, y\}$.  If $x$ and $y$ are nonadjacent, then by the minimum degree condition we have

%\begin{align*}
$$|N_H(x)\cap N_H(y)|\ge\left(\frac{n+2k-2}{2}\right) + \left(\frac{n+2k-2}{2}\right)-(n-2)=2k.$$
%\end{align*}


So there are at least $2k$ paths of length two between $x$ and $y$ in $G$.  If instead, $x$ and $y$ are adjacent, then 

\begin{align*}
|N_H(x)\cap N_H(y)|&\ge\left(\frac{n+2k-2}{2}-1\right) + \left(\frac{n+2k-2}{2}-1\right)-(n-2)\\
&=2k-2.
\end{align*}

So there are at least $2k-2$ paths of length two between $x$ and $y$ in $G$.  Consider the following vertex sets in $H$
$$X=\{v\in N_H(x)| v\not\in v_H(y)\}$$
$$Y=\{v\in N_H(y)| v\not\in v_H(x)\}.$$

If $X$ or $Y=\emptyset$ then $|N_H(x)\cap N_H(y)|\ge \frac{n+2k-2}{2}\ge \frac{(2k+2)+2k-2}{2}=2k$ and we are done.  So consider $x'\in X$ and $y'\in Y$.  If $x'y'\in E(G)$ then $\kappa(G)\ge (2k-2)+2=2k$ and if $x'y'\not\in E(G)$ then we are in the same case as the case where $xy\not \in E(G)$.  Therefore, $\kappa(G)\ge 2k$.  
\end{proof}

\begin{theorem}
Let $G$ be a graph of order $n \geq 18k-2$ for an integer $k\ge 2$, such that
$$\delta (G) \ge \frac{n + 2k -2}{2},$$ and $G$ contains a set of $k$ vertex disjoint chorded cycles $\mathcal{C}=\{C_1, C_2, \ldots, C_k\}$.   
Then the cycle system 
can be extended to span the vertices of $G$.
\label{thm:sAlbie Manzopan}
\end{theorem}

\begin{proof} Let $\mathcal{C}$ be the set of $k$ vertex disjoint cycles and let $R=G-\mathcal{C}$.  Assume $\mathcal{C}$ has been chosen with $|V(\mathcal{C})|$ as large as possible.  If $|V(\mathcal{C})|=n$, we are done, so assume not.\\

\vspace{.1in}
First suppose $|V(R)|<k$.  Then for any $v\in R$, $deg_{\mathcal{C}}~v\ge \frac{n+2k-2}{2}-(k-2)=\frac{n+2}{2}$.  Also note that $|\mathcal{C}|=n-|V(R)|\ge n-(k-1)=n-k+1$.  However, since $k\ge 2$, $n-k+1< n$. This implies that $deg_{\mathcal{C}}~v\ge \frac{|\mathcal{C|}}{2}$.  Thus, on some cycle $C\in\mathcal{C}$ there must be at least two consecutive vertices that are both neighbors of $v$.  By adding $v$ between its two such neighbors, we can extend $C$, a contradiction of the maximality of $\mathcal{C}$. 
%First suppose $|V(R)|<2k$.  Then for any $v\in R$, $\deg_R(v)\le 2k-2$, and by the minimum degree condition, we have $$deg_{\mathcal{C}}(v)\ge \frac{n+2k-2}{2}-(2k-2)\ge\frac{n-2k+2}{2}.$$
%But $|V(\mathcal{C})|=n-|V(R)|\le n-(2k-1)=n-2k+1$, thus $$deg_{\mathcal{C}}(v)>\frac{|V(\mathcal{C})|}{2}.$$  This implies that $v$ must have two neighbors in $\mathcal{C}$ that are consecutive vertices on some cycle $C_i$.  Then $\mathcal{C}$ can be extended by adding $v$ to $C_i$, contradicting the maximality of $|V(\mathcal{C}|$.  \\
\vspace{.1in}

Now suppose $|V(R)|\ge k.$  Since $\mathcal{C}$ is as large as possible, no vertex of $R$ can be adjacent to any two consecutive vertices in any cycle of $\mathcal{C}$.  Thus, for any vertex $v\in R$, we know $deg_{\mathcal{C}}~v \le\frac{|\mathcal{C}|}{2}$.  Since $n=|\mathcal{C}|+|V(R)|$ and for $k\ge 2$, $\delta(G)>\frac{n}{2}$,  $deg_R~v>\frac{|V(R)|}{2}$ and hence $R$ is hamiltonian connected.
%by Ore's theorem (for dissertation). 
Thus, for any adjacency of a vertex in $R$, to a vertex in a cycle $C_i\in\mathcal{C}$ there cannot be any adjacencies to the next $|V(R)|$ vertices from any other vertex in $R$, otherwise we could insert all of $R$ and extend the cycle, thus extending $\mathcal{C}$, a contradiction.  

\vspace{.4cm}

By Lemma \ref{lem:2kconn}, $\kappa(G)\ge 2k$, there is a $2k$ matching between $R$ and $\mathcal{C}$.  Therefore, the cycles can be broken up into at least $2k$ intervals with separate end-vertices.  Out of all of these intervals, $k$ of them could contain the specified edges $e_i$ for $1\le i\le k$.  Therefore, there are at least $k$ other intervals, each as large as $R$, otherwise we could insert $R$ and get a larger cycle system, contradicting the maximality of $|V\mathcal({C})|$. Hence 
\begin{align*}
|V(R)|(k+1)&\le n, \text{ thus,}\\
|V(R)|&\le \frac{n}{k+1}.
\end{align*}

So each vertex in $R$ has at least $\frac{n+2k-2}{2}-\frac{n}{k+1}$ adjacencies into $\mathcal{C}$.  However, 
$$\frac{n+2k-2}{2}-\frac{n}{k+1}=\frac{n}{2}-\frac{n}{k+1}+k-1=\frac{k-1}{2(k+1)} n+k-1.$$

Hence, a pair of vertices in $V(R)$ will form at least $\left(\frac{k-1}{2k+2}\right)n+k$ intervals in the cycles of $\mathcal{C}$.  Therefore, there are  $\frac{k-1}{2k+2}$ intervals that do not contain any edge $e_i$ for $1\le i\le k$. Thus we have
\begin{align*}
|V(R)|\left(\frac{k-1}{2k+2}\right)n &\le |\mathcal{C}|=n-|V(R)|.\\
 \text{Therefore, } |V(R)|&\le \frac{2k+2}{k-1}.
\end{align*}


\vspace{.1in}
So we have $k\le|V(R)|\le\frac{2k+2}{k-1}$, and this inequality holds for $2\le k\le3$.  Now suppose $k=3$ and assume we cannot extend $\mathcal{C}$.  Then $\delta(G)\ge \frac{n+4}{2}$ and $|V(R)|\le 4$.  If $|V(R)|=1$, then $|\mathcal{C}|=n-1$ and the vertex $v\in R$ must have $\frac{n+4}{2}$ edges to $\mathcal{C}$. Since $v$ is  adjacent to more than half of vertices in $\mathcal{C}$, it must be adjacent to at least two consecutive vertices on some cycle $C\in\mathcal{C}$.  The cycle set $\mathcal{C}$ can be extended by adding $v$ between its two neighbors on $C$, a contradiction.  \\

%If $|V(R)|=2$, then for $v\in R$, $\deg_{\mathcal{C}~}v \ge \frac{n+4}{2}-1=\frac{n+2}{2}$.  Since $|\mathcal{C}|=n-2$, again we are done. \\

%If $|V(R)|=3$, then for $v\in R$, $|\mathcal{C}|=n-3$ and $\deg_{\mathcal{C}}~v \ge \frac{n+4}{2}-2=\frac{n}{2}$, and we are done. \\
 
%If $|V(R)|=4$, then for $v\in R$, $|\mathcal{C}|=n-4$ and $\deg_{\mathcal{C}}~v \ge \frac{n+4}{2}-3=\frac{n-2}{2}$, and again we are done.\\
If $R=2, 3,$ or $4$, then for any $v\in R$ $\deg_{\mathcal{C}}~v\ge\frac{n-2}{2}$ and $|\mathcal{C}|\ge n-4$. 
Thus for $1\le|V(R)|\le4$, we have $n-4\le |\mathcal{C}|\le n-1$ and $\delta(G)\ge\frac{n+4}{2}-(|V(R)|-1)=\frac{n+6}{2}-|V(R)|>\frac{|\mathcal{C}|}{2}$, so we can always extend $\mathcal{C}$ by inserting a vertex, a contradiction.  \\

\vspace{.1in}
Suppose $k=2$.  Then $\delta(G)\ge\frac{n+2}{2}$ and $|V(R)|\le 6$.  If $|V(R)|=1$, $|\mathcal{C}|=n-1$ and $\delta(G)\ge\frac{n+2}{2}>\frac{|\mathcal{C}|}{2}$, and we are done.  If $|V(R)|=2$, then $|\mathcal{C}|=n-2$ and for any $v\in R$, $\deg_G ~v \ge1+\frac{n+2}{2}=\frac{n}{2}>\frac{\mathcal{C}}{2}$. %,a contradiction of the minimum degree condition when $k\ge2$.  
If $|V(R)|=3$, then $|\mathcal{C}|=n-3$ and for any $v\in R$,  $\deg_G~v\ge \frac{n+2}{2}-2=\frac{n-2}{2}>\frac{\mathcal{C}}{2}=\frac{n-3}{2}$, a contradiction.  
When $|V(R)|\ge 4$, $\deg_R~ v \ge\frac{n+2}{2}-(|V(R)|-1)$, and we can no longer guarantee this is strictly larger than $\frac{|\mathcal{C}|}{2}$.  However, $\deg_G~v=\deg_{\mathcal{C}}~v+\deg_R~v>\frac{n}{2}$, so if $\deg_G~v\le\frac{\mathcal{C}}{2}$ then $\deg_R~v>\frac{|V(R)|}{2}$.  Therefore, $R$ is hamiltonian connected.\\
\vspace{.1in} 




Let $v_1, v_2, \ldots, v_m, v_1$ be a cycle in $R$, where $m=|V(R)|$.  Further, every vertex in $R$ is adjacent to at most every other vertex on each cycle of $\mathcal{C}$, otherwise we could extend at least one of the cycles, a contradiction.   If $v_1$ and $v_2$ are adjacent vertices in $R$ that are adjacent to different sets of alternating vertices on some $C_i$, then if $v_1$ is adjacent to $x$ on $C_i$ and $v_2$ is adjacent to $y$ on $C_i$ such that $x$ is adjacent to $y$, then clearly $C_i$ may be extended, a contradiction. Therefore, $v_1$ and $v_2$ must have essentially the same neighbors in $\mathcal{C}$.  But then, by the degree condition, on some $C_i$ there will exist vertices $x, a,$ and $y$ such that $a$ is between $x$ and $y$ on the cycle, with $v_1$ adjacent to $x$ and $v_2$ adjacent to $y$.  Then by deleting $a$ and adding $v_1$ and $v_2$ we can extend $C_i$, a contradiction.  \\
\vspace{.1in}
This completes the proof. 


\end{proof}

\begin{corollary}  The sets of vertex disjoint cycles in Theorems \ref{thm:main} and \ref{thm:kvertsonchcyc} can be extended to span $V(G)$.  
\end{corollary}

\begin{proof} Theorem \ref{thm:main} follows directly.  For Theorem \ref{thm:kvertsonchcyc}, when $k=1$ note that $\delta(G)\ge\frac{n}{2}$ so $G$ is hamiltonian and the hamiltonian cycle must be chorded and must include the specified vertex, as desired. 
\end{proof}

\begin{definition} A {\bf linear forest} is a set of vertex disjoint paths. \end{definition}

\vspace{.1in}
Given a set of vertex disjoint paths $\{P_{r_1}, P_{r_2}, \ldots, P_{r_k}\}$ where $r_i\ge 2$ is the order of the path $P_{r_i}$, let $r=\sum_{i=1}^k r_i$.  Then the number of interior vertices in the path system is given by $r-2k$. \\
\vspace{.1in}



\begin{theorem}
Let $P_{r_1}, P_{r_2}, \ldots, P_{r_k}$ be a linear forest in a  $G$ of order $n\ge 16k+r-2$.  If the minimum degree $$\delta(G)\ge \frac{n}{2}+r-1-k,$$
then there exists a system of $k$ chorded cycles $\{C_1, C_2, \ldots, C_k\}$ such that the path $P_{r_i}$ lies on the cycle $C_i$ and $|V(C_i)|\le r_i+4$ for all $1\le i\le k$. 
\end{theorem}

\begin{proof}
Consider the graph $G'$ produced by replacing each path $P_{r_i}$ in $G$ by an edge $e_i$. Then the order of $G'$ is

$$|V(G')|=n-(r-2k)\ge 16k+r-2-r+2k=18k-2.$$

  Also, the minimum degree 
  
  $$\delta(G')\ge\frac{n}{2}+r-1-k-(r-2k)=\frac{n}{2}+k-1.$$  
  
  
  Then by Theorem \ref{thm:kedgeson}, there exists a set of $k$ vertex disjoint chorded cycles $C_1^{c_1}, C_2^{c_2}, \ldots, C_k^{c_k}$ such that $e_i\in E(C_i)$ and $e_i\neq c_i$ for all $i$.  Now replace the edge $e_i$ by the path $P_{r_i}$ for all $i$, i.e. insert the set of interior vertices of each path back into $G'$ to form the original graph $G$. Then the path $P_{r_i}$ now lies on the cycle $C_i$ and each $C_i$ is still a chorded cycle since the addition of the interior vertices of $P_{r_i}$ does not affect the end-vertices of any chord.  
\end{proof}























