\mychapter{Forbidden Subgraphs for Chorded Pancyclicity}

\noindent 




We call a graph $G$ {\it pancyclic} if it contains at least one cycle of every possible length $m$, for $3\le m\le |V(G)|$.  In this chapter, we focus on a new property we call {\it chorded pancyclicity}.  We explore both an edge-density condition and forbidden subgraphs in claw-free graphs
sufficient to imply that the graph contains at least one chorded cycle of every possible length $4, 5, \ldots, |V(G)|$.  In particular, certain paths and triangles with pendant paths are forbidden along with $K_{1,3}$.  The results in this chapter are joint work with Ron Gould. 


\section{Introduction}

In the past, forbidden subgraphs for hamiltonian properties in graphs have been widely studied (for an overview, see \cite{FG}).  A graph containing a cycle of every possible length from three to the order of the graph is called pancyclic and it is one of the well-studied cycle properties in graphs.  In this chapter, we define the notion of chorded pancyclicity, and study the density necessary to guarantee this property in a graph.  We also extend some forbidden subgraph results for pancyclicity to analogous results for chorded pancyclicity.   We consider only $K_{1, 3}$-free (or {\it claw}-free) graphs, and we forbid certain paths and triangles with pendant paths. 

In this chapter, we extend the following theorem to analogous results on chorded pancyclicity.  Recall these results stated earlier in $\S1.5$.  

 \begin{theorem} Let $R, S$ be connected graphs and let $G$ ($G\neq C_n$) be a 2-connected graph of order $n\ge10$.  Then if $G$ is $\{R,S\}$-free then $G$ is pancyclic for $R=K_{1,3}$ and $S$ is either $P_4, P_5, P_6, Z_1,$ or $Z_2$.  
\label{thm:pan}
 \end{theorem}


The proof of a theorem in \cite{GH} yields the following result.

\begin{theorem}{\rm\cite{GH}}
If $G$ is a 2-connected graph of order $n\ge 10$ that contains no induced subgraph isomorphic to $K_{1,3}$ or $Z_1$, then $G$ is either a cycle or $G$ is pancyclic.  
\label{thm:z1}
\end{theorem}


Gould and Jacobson proved a similar result for $Z_2$ in \cite{GJ}.  

\begin{theorem}{\rm\cite{GJ}}
If $G$ is a 2-connected graph of order $n\ge 10$ that contains no induced subgraph isomorphic to $K_{1,3}$ or $Z_2$, then $G$ is either a cycle or $G$ is pancyclic. 
\label{thm:z2} 
\end{theorem}

Faudree, Gould, Ryjacek, and Schiermeyer proved a similar result for certain paths in \cite{FRS}. 


\begin{theorem} {\rm\cite{FRS}}
If $G$ is a 2-connected graph of order $n\ge 6$ that is $\{K_{1,3}, P_5\}$-free, then $G$ is either a cycle or $G$ is pancyclic. 
\label{thm:p5} 
\end{theorem}

\begin{theorem} {\rm\cite{FRS}}
If $G$ is a 2-connected graph of order $n\ge 10$ that is $\{K_{1,3}, P_6\}$-free, then $G$ is either a cycle or $G$ is pancyclic. 
\label{thm:p6} 
\end{theorem}

Theorem \ref{thm:p5} implies the following result for $P_4$.   

\begin{theorem} {\rm\cite{FRS}}
If $G$ is a 2-connected graph of order $n\ge 6$ that is $\{K_{1,3}, P_4\}$-free, then $G$ is either a cycle or $G$ is pancyclic. 
\label{thm:p4} 
\end{theorem}


In this chapter, we extend each of these results to chorded pancyclicity.   

\section{Results}
\subsection{Introduction to Chorded Pancyclicity}

\begin{definition} A graph $G$ of order $n$ is called {\bf chorded pancyclic} if it contains a chorded cycle of every length $i$, $4\le i\le n$.   
\end{definition}

\noindent {\bf Note:} not all pancyclic graphs are chorded pancyclic.  The graph in Figure 4a below is pancyclic, but contains no chorded $5$-cycle. Further, the graph in Figure 4b represents an infinite family of pancyclic graphs that do not contain a chorded $4$-cycle.   


\begin{center}
{\scalebox{.7}{ \includegraphics{nonpan.jpg} }}\\
{\bf Figure 4a.}
\end{center} 

\begin{center}
{\scalebox{.7}{ \includegraphics{inffamily.jpg} }}\\
{\bf Figure 4b.}
\end{center}

 
Before stating our results, we note particular notation that will be used throughout the proofs.  For vertices $v_1, v_2, v_3, v_4$, the notation $v_1$--$v_2, v_3, v_4$ represents the $K_{1,3}$ graph where $v_1$ is adjacent to the three other vertices and the set $\{v_2, v_3, v_4\}$ is an independent set. To represent $Z_1$, we will use the notation $v_1v_2v_3$--$v_4$, where $v_1, v_2, v_3$ is a triangle and $v_4$ is adjacent to $v_3$.  Similarly, $v_1v_2v_3$--$v_4v_5$ will be used to represent $Z_2$.  The graphs$K_{1,3}$, $Z_1$, and $Z_2$ with the aforementioned notations are shown below (Figure 4c).   
 \begin{center}
{\scalebox{.75}{ \includegraphics{clawz1z2.jpg} }}\\
{\bf Figure 4c.}
\end{center}

\subsection{Edge Density and Chorded Pancyclicity}

Following a similar idea from Chapters 2 and 3, it is natural to expect enough density in a graph will imply chorded pancyclicity.  We show that this is true in the following theorem.  

 \begin{theorem} Let $G$ is a graph on $n\ge 5$ vertices.  If $\sigma_2(G)\ge n+1$, then $G$ is chorded pancyclic and further, this degree sum condition is best possible.
 \label{thm:density}
 \end{theorem}

\noindent {\bf Example:}  The complete bipartite graph on $n$ vertices $G=K_{\frac{n}{2}, \frac{n}{2}}$, has $\sigma_2(G)=n$ and only contains cycles of even length.  Therefore $G$ is not pancyclic and hence clearly not chorded pancyclic either. Thus, the bound in Theorem \ref{thm:density} is sharp.  

\begin{proof} Consider a graph $G$ of order $n\ge 4$ with $\sigma_2(G)\ge n+1$.  By Ore's Theorem, $G$ is hamiltonian and by $\sigma_2(G)$, any cycle of order $n$ in $G$ must be chorded.   According to a result of Bondy in \cite{B}, if $|E(G)|\ge n^2/4$ then $G$ is either pancyclic or $G$ is the balanced complete bipartite graph $K_{\frac{n}{2},\frac{n}{2}}$. Since $\sigma_2(G)\ge n+1$, $|E(G)|>n^2/4$ and thus $G$ must be pancyclic. Let $m$ be the largest number with $4\le m<n$ such that all of the $m$-cycles in $G$ are nonchorded.  \\ 


\noindent {\bf Claim 1.} $G$ contains a chorded $4$-cycle. 
\begin{proof}Let $x$ and $y$ be a pair of nonadjacent vertices chosen to have the smallest number $m\ge 3$ of common neighbors in $G$.  Partition $V(G)$ into the following sets:
\begin{align*}
\displaystyle N &=\{\text{common neighbors of $x$ and $y$}\},\\
\displaystyle N^*(x) &=\{\text{vertices adjacent to $x$ but not $y$}\},\\
\displaystyle N^*(y) &=\{\text{vertices adjacent to $y$ but not $x$}\},\\
\displaystyle D&=\{\text{vertices not adjacent to both $x$ and $y$}\}.
\end{align*}

Let $|N^*(x)|=X$, $|N^*(y)|=Y$, and $|D|=d$.  \\

\noindent {\bf Claim 1.1.} If $|N|=m\ge 3+r$, then $|D|\le r$.
\begin{proof}
Suppose not, say $|D|=r+t$ for some $t\ge 1$.  Then from the partition of $V(G)$, we have 
\begin{align*}
X+Y+m+d&=n-2, {\text{ or}}\\
X+Y+m&=n-2-d.\\
{\text{Then }}\sigma_2(G)&\le n-2-(r+t)+r+3.\\
{\text{Hence, }}\sigma_2(G)&\le n+1-t<n+1, {\text{ a contradiction.}}
\end{align*}
\end{proof}
Now consider $a, b\in N$.  If $ab\in E(G)$, then $x, a, y, b, x$ is a chorded $4$-cycle with chord $ab$.  If $ab\not\in E(G)$, then $a$ and $b$ must have at least $m$ common neighbors (with $x$ and $y$ being two of them).  Now $a$ and $b$ must send no edges into $N$, otherwise we would have a chorded $4$-cycle.  But now the common neighbors of $a$ and $b$ (other than $x$ and $y$) cannot all lie in $D$, otherwise $a$ and $b$ would have at most $2+r<m$ common neighbors, a contradiction.  Hence, $a$ and $b$ have at least one common neighbor in either $N^*(x)$ or $N^*(y)$.  Without loss of generality, suppose $a$ and $b$ share a neighbor $z\in N^*(X)$.  Then $a, z, b, x, a$ is a $4$-cycle with chord $x z$.  Thus $G$ must contain a chorded $4$-cycle.  

\end{proof}


\noindent {\bf Claim 2.} If $G$ contains a chorded $4$-cycle, then $G$ also contains a chorded $5$-cycle.  
\begin{proof} Consider a chorded $4$-cycle in $G$, say $C=v_1, v_2, v_3, v_4, v_1$ with chord $v_1 v_3$.  If $v_2 v_4\not\in E(G)$ then since $\sigma_2(G)\ge n+1$, $v_2$ and $v_4$ must have a common neighbor $x\not\in V(C)$  and then $v_1, v_3, v_2, x, v_4, v_1$ is a $5$-cycle with chord $v_1 v_2$.  Now suppose $C$ is the complete graph $K_4$. Without loss of generality, if $x\not\in V(C)$ is adjacent to $v_1$ but not to $v_2$, then $x$ and $v_2$ must share a common neighbor, $y\neq v_1$. If $y$ is any vertex in $C$ then there clearly exists a chorded $5$-cycle. %If y=v_3, then $v_1, x, v_3, v_2, v_4, v_1$ is a $5$-cycle with chord $v_1v_2$ . If $y= v_4$ then $v_1, x, v_4, v_3, v_2, v_1$ is a $5$-cycle with chord $v_1, v_3 $.  
If $y\not\in V(C)$, then $v_1, x, y, v_2, v_4, v_1$ is a $5$-cycle with chord $v_1 v_2$. Thus, when $n\ge4$ the existence of a chorded $4$-cycle implies the existence of a chorded $5$-cycle in $G$.  
\end{proof}


\noindent{\bf Claim 3.} $G$ contains a chorded $k$-cycle, for all $k\ge 6$.

\begin{proof} Suppose $m\ge 6$. Consider a chordless m-cycle $C=v_1, v_2, \ldots, v_m, v_1$ in $G$. Since $C$ is chordless, $v_1$ and $v_3$ are nonadjacent and must have a common neighbor $x\not\in V(C)$.  Similarly $v_2$ and $v_6$ are nonadjacent and must have a neighbor $y\not\in V(C)$ such that $x\neq y$.  Now $v_1, x, v_3, v_2, y, v_6, \dots, v_m, v_1$ is an $m$-cycle with chord $v_1 v_2$, a contradiction.  
\end{proof}

\noindent Claims 1, 2, and 3 imply that there must be at least one chorded $4$-cycle in $G$, and thus at least one chorded $5$-cycle in $G$, as well as at least one chorded $m$-cycle in $G$ for $6\le m\le n$.  Therefore, $G$ is chorded pancyclic.


\end{proof}

\subsection{Forbidden Subgraphs} 
 
We now turn our attention to forbidden subgraphs for chorded pancyclicity.  We will use Theorem \ref{thm:pan} as a guide for the following results. 

% \begin{theorem} Let $R, S$ be connected graphs and let $G$ ($G\neq C_n$) be a 2-connected graph of order $n\ge10$.  Then if $G$ is $\{R,S\}$-free then $G$ is chorded pancyclic for $R=K_{1,3}$ and $S$ is either $P_4, P_5, Z_1,$ or $Z_2$.  
% \end{theorem}
  
\begin{theorem} Let $G$ be a 2-connected graph of order $n\ge 10$.  If $G$ is $\{K_{1,3}, Z_1\}$-free, then if $G\neq C_n$, $G$ is chorded pancyclic. 
\label{thm:z1cc}
\end{theorem}

\begin{proof}
From Theorem \ref{thm:z1}, we know that $G$ must be pancyclic.  Now suppose $G$ is not chorded pancyclic.  Then there exists at least one $i$ with $4\le i< n$, such that every $i$-cycle in $G$ does not contain a chord. Consider the largest such $i$, and let $G$ be such a pancyclic graph with no chorded $i$-cycles.  Note that $i\neq n$, otherwise $G=C_n$, a contradiction.  Consider an $i$-cycle, $C= v_1, v_2, \dots, v_{i-1}, v_i, v_1$.  Since $i<n$, there exists some vertex $x\not\in V(C)$.  By our assumption, $G$ is 2-connected, so there must be an edge $xy$ in $E(G)$ such that $y\in V(C)$.  Without loss of generality, suppose $v_1 x\in E(G)$.  Then $v_1-x,v_2, v_i$ is a claw, so one of $\{v_i v_2, v_ix, v_2x\}$ must be an edge in $G$. \\

If $v_i v_2\in E(G)$ then $v_iv_2$ is a chord of $C$ and thus $G$ contains a chorded $i$-cycle, a contradiction.  By symmetry, the case where $v_ix\in E(G)$ and the case where $v_2x\in E(G)$ are equivalent, so without loss of generality, suppose $v_2x$ is an edge in $G$.  Then $xv_1 v_2$--$ v_3$ is a $Z_1$ subgraph of $G$, therefore either $v_1 v_3$ or $xv_3$ must be an edge in $G$.  If $v_1v_3\in E(G)$ then $C$ is a chorded $i$-cycle with chord $v_1 v_3$, a contradiction.  If $xv_3\in E(G)$ then $x$ can replace $v_1$ on $C$ and $C$ becomes a chorded $i$-cycle with chord $xv_3$, again a contradiction. Therefore, $G$ always contains a chorded $i$-cycle, so $G$ must be chorded pancyclic.      
\end{proof}

%We will need a  results for our upcoming proofs.   

%\begin{lemma} Let $G$ be a claw-free graph and let $v\in V(G)$ be a vertex that is part of at least two triangles that are disjoint except for $v$.  If $v$ is adjacent to any other vertex off of the triangles, then $G$ contains a chorded $C_4$.   
%\end{lemma}

%\begin{proof} Suppose $a, b, v, a$ and $c, d, v, c$ are two triangles in a claw-free graph $G$.  If $vx\in E(G)$ for some $x\in V(G)-\{a, b, c, d\}$, then $v$--$acx$ is an induced claw subgraph of $G$.  Adding any one of the edges $ac$, $ax$, or $cx$ to eliminate the induced claw results in a chorded $4$-cycle in $G$. 
%\end{proof}

To prove our next lemma, we will use the following theorem from Duffus, Gould, and Jacobson, on net-free graphs.  The net graph is shown below.   

 \begin{center}
{\scalebox{.7}{ \includegraphics{net.jpg} }}\\
{\bf Figure 4d.}
\end{center}

\begin{theorem}{\rm\cite{DGJ}} Any connected, net-free, claw-free graph $G$ contains a Hamiltonian path $($i.e. is \it{traceable}$)$. 
\label{thm:hampath}
\end{theorem}

\begin{lemma} Let $G$ be claw-free.  For any $x\in V(G)$, the neighborhood of $x$, $N_G(x)$ is either connected and traceable, or two disjoint cliques.  
\label{lem:clique}
\end{lemma}
\begin{proof} First note that he independence number of the neighborhood of any vertex in a claw-free graph must be at most two, otherwise $G$ contains a claw.  Let $G$ be a claw-free graph and consider a vertex $x\in V(G)$.  If $N_G(x)$ is disconnected, then it must be two cliques in order to have independence number two.  If the neighborhood of a vertex contains an induced net, then it has independence number at least three (the independence number of the net graph).  Therefore, the neighborhood of any vertex in a claw-free graph cannot contain an induced net.  So if $N_G(x)$ is connected, then it is also net-free, claw-free and therefore, by Theorem \ref{thm:hampath}, must be traceable. 
\end{proof}

\noindent {\bf Example:} The graph shown below is 2-connected, $\{K_{1,3}, Z_2\}$-free, pancyclic, and has maximum degree $\Delta(G)=4$, but it does not contain a chorded $4$-cycle so it is not chorded pancyclic.  However, adding any edge yields a chorded $4$-cycle, thus making the graph chorded pancyclic.  


\begin{center}
{\scalebox{.7}{ \includegraphics{maxdeg4.jpg} }}\\
{\bf Figure 4e.}
\end{center}


\begin{theorem} Let $G$ be a 2-connected graph of order $n\ge 10$ with $\Delta(G)\ge 5$.  If $G$ is $\{K_{1,3}, Z_2\}$-free, then if $G\neq C_n$, $G$ is chorded pancyclic. 
\end{theorem}


\begin{proof}
\flushleft
By Theorem \ref{thm:z2}, we know such a graph $G$ must be pancyclic.  For the sake of contradiction, suppose there is some $m$ with $4\le m<n$ such that every $m$-cycle in $G$ does not contain a chord.\\
\vspace{.1in}  

{\it Case 1.} Suppose $m\ge 5$. \\
~~~Consider an $m$-cycle $C=v_1, v_2, v_3, \ldots, v_m, v_1$ in $G$.  Since $G$ is 2-connected and of order at least 10, there exists a vertex $x\in V(G)-V(C)$ such that $xv\in E(G)$ for some $v\in V(C)$.  Without loss of generality, suppose $xv_1\in E(G)$.  Then $v_1$--$xv_2v_m$ is an induced claw in $G$. To eliminate this induced claw, either $xv_2$, $xv_m$ or $v_2v_m$ must be added as an edge.  If $v_2v_m$ is added then $C$ is a chorded $m$-cycle and we are done.  By symmetry, adding either $xv_2$ or $xv_m$ as an edge is equivalent, so without loss of generality, suppose $xv_2\in E(G)$.  Then $xv_1v_2$--$v_3v_4$ is an induced $Z_2$ in $G$.  The only two edges that would eliminate this induced $Z_2$ and would not add a chord to the $m$-cycle $C$ are $xv_3$ and $xv_4$. \\
~~~First suppose $xv_3\in E(G)$.  Then $xv_2v_3$--$v_4v_5$ is an induced $Z_2$ in $G$.   The only edges that will eliminate the induced $Z_2$, but will not yield a chorded $m$-cycle are $xv_4$ and $xv_5$.  If $xv_4\in E(G)$ then $v_1, v_2, x, v_4, v_5, \dots, v_m, v_1$ is an $m$-cycle with chord $xv_1$.  If instead $xv_5\in E(G)$, then $v_1, v_2, v_3, x, v_5, \ldots, v_m, v_1$ is an $m$-cycle with chord $xv_1$.  This completes the case where $xv_3\in E(G)$. Now suppose instead that $xv_4\in E(G)$.  Then $v_1, v_2, x, v_4, v_5, \ldots, v_m, v_1$ is an $m$-cycle with chord $v_1x$.  This completes the case where $xv_4\in E(G)$ and thus completes the proof of Case 1. \\
\vspace{.1in}

{\it Case 2.} Suppose $m=4$.\\
~~~Since $\Delta(G)\ge 5$ there must be some vertex $x\in V(G)$ such that $|N_G(x)|\ge 5$.  Consider such a vertex $x$ and let $|N_G(x)|=l\ge5$.  By Lemma \ref{lem:clique}, $N_G(x)$ is either connected and traceable, or two disjoint cliques.  If $N_G(x)$ is connected and traceable, say $v_1, v_2, \ldots, v_l$ is a hamiltonian path in $N_G(x)$.  Then $x, v_1, v_2, v_3, x$ is a $4$-cycle with $xv_2$ as a chord.  If $N_G(x)$ is two disjoint cliques, then the one of the cliques is of order at least three.  Three vertices from this clique together with the vertex $x$ yield a chorded $4$-cycle.  So no matter what the neighborhood of $x$ looks like, there is always a chorded $4$-cycle in $G$.  This completes the proof of Case 2 and we are done.   
\end{proof}

\begin{conjecture} Let $G$ be a 2-connected graph of order $n\ge 10$.  If $G$ is $\{K_{1,3}, Z_2\}$-free, then if $G\neq C_n$, $G$ is chorded pancyclic. 
\end{conjecture}

A proof of this conjecture was done using a straightforward case analysis, similar to the proof of Theorem \ref{thm:z1cc}, but resulted in very, very many cases.  Consequently, the proof has been omitted here.  

\begin{theorem} Let $G$ be a 2-connected graph of order $n\ge 10$.  If $G$ is $\{K_{1,3}, P_4\}$-free, then if $G\neq C_n$, $G$ is chorded pancyclic. 
\label{thm:p4ch}
\end{theorem}

\begin{proof}
\flushleft
By Theorem \ref{thm:p4}, we know that $G$ is pancyclic.  Suppose, for the sake of contradiction, that $G$ is not chorded pancyclic.  Let $m$ be the largest number with $4\le m\le n$ such that every $m$-cycle in $G$ is chordless.\\
\vspace{.1in}

{\it Case 1.} Suppose $m=4$.  \\
~~~Consider a $4$-cycle $C=v_1, v_2, v_3, v_4, v_1$ in $G$.  Since $n\ge 10$ and $G$ is 2-connected, there exists a vertex $x\not \in V(C)$ such that $xv\in E(G)$ for some $v\in V(G)$.  Without loss of generality suppose $v_1 x\in E(G)$.  Then $x, v_1, v_2, v_3$ is an induced $P_4$ in $G$.  Since $G$ must be $P_4$-free, $v_1v_3$, $v_2x$, or $v_3x$ must be in $E(G)$.  If $v_1v_3\in E(G)$ then the cycle $C$ is a chorded $4$-cycle, a contradiction.

~~~If $v_2x\in E(G)$ then $x, v_1, v_4, v_3$ is an induced $P_4$ subgraph of $G$, therefore $G$ must contain either $v_1 v_3$, $v_3x$, or $v_4x$ as an edge. The edge $v_1 v_3$ creates a chord of the $4$-cycle $C$, a contradiction.  The edge $v_3x$ yields the $4$-cycle $v_1, x, v_3, v_2, v_1$ with chord $v_2x$, a contradiction. Similarly, the edge $v_4x$ yields the $4$-cycle $v_1, v_2, x, v_4, v_1$ with chord $v_1x$, again a contradiction.

~~~If $v_3x\in E(G)$ then $v_1$--$xv_2v_4$ is an induced claw in $G$, therefore $G$ must contain either $xv_2$, $xv_4$, or $v_2v_4$ as an edge.  The edge $xv_2$ forms the $4$-cycle $v_1, v_2, v_3, x, v_1$ with chord $xv_2$, a contradiction.  The edge $xv_4$ yields the $4$-cycle $v_1, v_4, v_3, x, v_1$ with chord $xv_4$, a contradiction. The edge $v_2v_4$ is a chord of the $4$-cycle $C$, again a contradiction.  Thus, every $4$-cycle in $G$ must be chorded.\\
\vspace{.1in}

{\it Case 2.} Suppose $m>4$. \\
~~~Any chordless $m$-cycle contains at least one induced $P_4$ subgraph, for $m>4$.  Therefore, all $m$-cycles must contain at least one chord to ensure that $G$ is $P_4$-free, for $4<m\le n$.  Now we can conclude that $G$ is chorded pancyclic.  
\end{proof}

\begin{theorem} Let $G$ be a 2-connected graph of order $n\ge 10$.  If $G\neq C_n$ is $\{K_{1,3}, P_5\}$-free, then $G$ is chorded pancyclic. 
\label{thm:p5ch}
\end{theorem}
\flushleft
\begin{proof} From Theorem \ref{thm:p5} we know $G$ must be pancyclic.  Suppose, for the sake of contradiction, that $G$ is not chorded pancyclic.  Let $m$ be the largest number with $4\le m\le n$ such that every $m$-cycle in $G$ is not chorded. \\
\vspace{.25cm}
{\it Case 1.} Suppose $m=4$.\\
\vspace{.2cm}

~~~Consider a $4$-cycle $C=a, b, c, d, a$ in $G$.  Since $G$ is 2-connected and of order at least 10, there is a vertex $x_1\not\in V(C)$ such that $x_1v\in E(G)$ for some $v\in V(C)$.  Without loss of generality, suppose $x_1a\in E(G)$.  Then $a$--$x_1bd$ is an induced claw in $G$, so either $x_1b$, $x_1d$, or $bd$ must be an edge in $G$.  Adding the edge $bd$ makes $C$ into a chorded $4$-cycle.  By symmetry, adding $x_1b$ or $x_1d$ is equivalent, so without loss of generality, suppose $x_1 b\in E(G)$.  \\
\vspace{.2cm}

~~~Now there are no induced $P_5$ or $K_{1,3}$ subgraphs in $G$, but again since $G$ is 2-connected and of order at least 10, there must be some vertex $x_2\not \in V(C)$ such that $x_1\neq x_2$ and $x_2v\in E(G)$ for some $v\in V(C)$.  \\
\vspace{.2cm}

~~~If $x_2a$ (or, by symmetry, $x_2b$) is an edge in $G$, then $a$--$x_2bd$ is an induced claw.  Then either $x_2b$, $x_2d$, or $bd$ must be an edge.  If either $bd$ or $x_2b$ is an edge, then there exists a chorded $4$-cycle in $G$.  So suppose $x_2d\in E(G)$.
 % Then $x_1, b, c, d, x_2$ is an induced $P_5$ in $G$.  The addition of any edge among these vertices creates a chorded $4$-cycle. This completes the case when $x_2a\in E(G)$.
%~~~Thus, we may assume $x_2$ is adjacent to both $c$ and $d$ or $x_2$ is adjacent to $x_1$. First suppose $x_2$ is adjacent to $x_1$.  Now $x_2, x_1, a, d, c$ is an induced $P_5$ in $G$.  
There is some vertex $x_3\not\in V(C)$ such that $x_3\neq x_2$ or $x_1$ and $x_3v\in E(G)$ for some $v\in V(C)\cup \{x_1\}$. \\
\vspace{.2cm}

~~~Now we must consider all of the possible adjacencies of $x_3$: $a$, $b$ (same case as $d$), $c$, and $x_1$.  If $x_3a\in E(G)$ then $a$--$x_3bd$ is an induced claw.  Any edge added to eliminate the claw will result in a chorded $4$-cycle.  \\
\vspace{.2cm}

~~~If $x_3b$ (or similarly $x_3d$) $\in E(G)$ then $b$--$x_3ac$ is a claw.  Adding either one of the edges $ac$ or $x_3a$ to eliminate the claw, will result in a chorded $4$-cycle.  Adding $x_3c$ to eliminate the claw does not yield a chorded $4$-cycle or any induced $P_5$ or $K_{1,3}$ subgraphs.  However, following an earlier argument, there is a vertex $x_4\not \in V(C)\cup \{x_1, x_2, x_3\}$ such that $x_4v\in E(G)$ for some $v\in V(C)\cup \{x_1, x_2\}$.  Now we must consider all of the possible adjacencies of $x_4$.  \\
\vspace{.2cm}

~~~If $x_4a$ (or similarly $x_4b$) $\in E(G)$ then $a$-$x_4bd$ is an induced claw.  Adding any edge to eliminate the claw yields a chorded $4$-cycle.  If $x_4c$ (or similarly $x_4d$) $\in E(G)$ then $c$--$x_4bd$ is an induced claw.  Adding either $bd$ or $x_4b$ to eliminate the claw, yields a chorded $4$-cycle.  Adding $x_4d$ to eliminate the claw does not result in any chorded $4$-cycles or induced $P_5$ or $K_{1,3}$ subgraphs.  There must exist another vertex $x_5\not \in V(C)\cup \{x_1, x_2, x_3, x_4\}$ such that $x_5v\in E(G)$ for some $v\in V(C)\cup\{x_1, x_2, x_3\}$.  \\
\vspace{.2cm}

~~~If $x_5$ is adjacent to any of the original vertices in $C$, then an induced claw in each of those cases will yield a chorded $4$-cycle. The remaining possible adjacencies to $x_5$ are all symmetric: $x_1$, $x_2$, and $x_3$.  So without loss of generality suppose $x_1x_5\in E(G)$.  Then $x_5, x_1, a, d, c$ is an induced $P_5$.  Adding any edge that eliminates the induced $P_5$ will either yield a chorded $4$-cycle or an induced claw that will yield a chorded $4$-cycle. \\
\vspace{.2cm}

~~~If $x_4x_1\in E(G)$, then $x_4, x_1, a, d, c$ is an induced $P_5$.  Adding any one of four of the six edges that eliminate the induced $P_5$ results in a chorded $4$-cycle.  However, adding either $x_4d$ or $x_4c$ will not produce a chorded $4$-cycle.  By symmetry, adding either edge is equivalent so without loss of generality suppose $x_4d\in E(G)$.  Then $d$--$x_4ac$ is an induced claw and $x_4c$ is the only claw-eliminating edge whose addition will not yield a chorded $4$-cycle.  In fact, adding $x_4c$ does not yield any induced $P_5$ or $K_{1,3}$ subgraphs either.  There exists a vertex $x_5\not \in V(C)\cup\{x_1, x_2, x_3, x_4\}$ such that $v_5v\in E(G)$ for some $v\in V(C)\cup\{x_1, x_2, x_3\}$.  The addition of either $x_5a$ or $x_5b$ yields an induced claw that results in a chorded $4$-cycle.  The addition of $x_5c$ or $x_5d$ results in an induced claw that yields either a chorded $4$-cycle or a previously considered case, depending on which edge is added to eliminate the induced claw.  \\
\vspace{.2cm}

~~~If $x_5x_1\in E(G)$, then $x_1$--$x_5x_4a$ is an induced claw and adding either $x_5a$ or $x_4a$ to eliminate the claw, yields a chorded $4$-cycle.  If $x_5x_4$ is added to eliminate the claw then $x_5, x_1, a, d, c$ is an induced $P_5$ and any edge added to eliminate the induced $P_5$ results in a chorded $4$-cycle. \\
\vspace{.2cm}

~~~ If $x_5x_2\in E(G)$ then $x_5, x_2, a, b, c$ is an induced $P_5$.  To eliminate the induced $P_5$, adding either $x_5a$, $x_1d$, $x_1c$, or $ac$ yields a chorded $4$-cycle.  Adding $x_5b$ to eliminate the induced $P_5$ produces the induced $b$--$x_5ac$ claw.  The only claw-eliminating edge that will not yield a chorded $4$-cycle is $x_5c$, so suppose $x_5c\in E(G)$.  Now $b$--$x_5x_3a$ is an induced claw and the addition of any claw-eliminating edge yields a chorded $4$-cycle. If $x_5c\in E(G)$ (and $x_5b\not\in E(G)$) then $c$--$x_5bd$ is an induced claw and any added claw-eliminating edge results in either a chorded $4$-cycle or a previously checked case.  If $x_2x_4\in E(G)$ (and $x_1x_4\not\in E(G)$) then $x_4, x_2, a, b, c$ is an induced $P_5$ and any induced-$P_5$-eliminating edge yields a chorded $4$-cycle, except the edge $x_4c$.  If $x_4c\in E(G)$ then $c$--$x_4bd$ is an induced claw and the addition of any induced-claw-eliminating edge will yield a chorded $4$-cycle.   If $x_1, x_3\in E(G)$ (and  $x_3c\not\in E(G)$) then  $x_3, x_1, b, c, d$ is an induced $P_5$ and any edge that will eliminate the induced $P_5$ except for $x_3c$ or $x_3d$ will result in a chorded $4$-cycle.\\  
\vspace{.2cm}

~~~If $x_3c\in E(G)$ then $c$--$x_3bd$ is an induced claw.  To eliminate the induced claw, the addition of either $x_3b$ or $bd$ yields a chorded $4$-cycle, but the addition of $x_3d$ does not.  There exists a vertex $x_4\not \in V(C)\cup\{v_1, x_2, x_3\}$ such that $x_4v\in E(G)$ for some $v\in V(C)\cup\{x_1, x_2\}$.  Considering the possible adjacencies of $x_4$, if $x_4a$, $x_4b$, $x_4c$, or $x_4d\in E(G)$ then an induced claw forces the existence of a chorded $4$-cycle or a previously checked case. If $x_4x_1$ is added to eliminate the induced $P_5$ then $x_1$--$x_4x_3b$ is an induced claw and the only induced claw-eliminating edge that does not yield a chorded $4$-cycle is $x_3x_4$.  So if $x_3x_4\in E(G)$, then $x_4, x_1, a, d, c$ is an induced $P_5$ and adding any edge to eliminate this induced $P_5$ yields a chorded $4$-cycle.  If $x_4x_2\in E(G)$ (and $x_1x_4\not\in E(G)$) then $x_4, x_2, a, b, c$ is an induced $P_5$.  Adding any edge to eliminate this induced $P_5$ results in a chorded $4$-cycle, except for the addition of either $x_4b$ or $x_4c$.  If $x_4b\in E(G)$ then $b$--$x_4ac$ is an induced claw.  Adding any edge except for $x_4c$ to eliminate this induced claw will result in a chorded $4$-cycle.  If $x_4c$ is added to eliminate the claw, then $x_4, x_2, , x_1, x_3$ is an induced $P_5$ and adding any edge to eliminate this induced $P_5$ yields a chorded $4$-cycle. If $x_4c$ was added first instead of $x_4b$, then $c$--$x_4x_3b$ is an induced claw.  To eliminate the claw, adding the edge $x_3b$ yields a chorded $4$-cycle and adding the edge $x_4b$ results in a previously checked case.  Adding $x_3x_4$ results in a $x_3$--$x_1x_4d$ induced claw.  Any edge added to eliminate this claw yields a chorded $4$-cycle.  This completes the case where $x_2a\in E(G)$. \\ 
\vspace{.2cm}



~~~If $x_2c$ (or, by symmetry, $x_2d$) is an edge in $G$, then $c$--$x_2bd$ is an induced claw, which can be eliminated by adding $x_2b$, $x_2d$, or $bd$ as an edge.  If $bd$ is added then $C$ is a chorded $4$-cycle. Adding $x_2b$ as an edge yields a previously considered structure.  So suppose $x_2d\in E(G)$.  There are no chorded $4$-cycles or induced claws or $P_5$ subgraphs.  There exists a vertex $x_3\not \in V(C)\cup\{x_1, x_2\}$ such that $x_3v\in E(G)$ for some $v\in V(C)\cup\{x_1\}$.   Now consider all of the possible adjacencies of $x_3$.  By symmetry, adding the edge $x_3a$ is equivalent to adding any one of the edges $x_3b$, $x_3c$, or $x_3d$.  Without loss of generality, suppose $x_3a\in E(G)$.  Then $a$--$x_3bd$ is an induced claw.  The addition of any one of the edges needed to eliminate this induced claw results in either a previously checked case, or a chorded $4$-cycle.  So instead suppose $x_3$ is adjacent to $x_1$ (the only other possibly adjacency of $x_3$).  Then $x_3, x_1, a, d, c$ is an induced $P_5$ in $G$.  If any one of the edges needed to eliminate the induced $P_5$ is added, then there is a chorded $4$-cycle, except when $x_3d$ (or by symmetry, $x_3c$ is added.  Without loss of generality, suppose $x_3d\in E(G)$.  Then $d$--$x_3ac$ is an induced claw in $G$.  Adding any one of the edges needed to eliminate the induced claw, results in a chorded $4$-cycle. This completes the case where $x_2c\in E(G)$.  \\
\vspace{.25cm}







{\it Case 2.} Suppose $m=5$. \\
\vspace{.2cm}

~~~Consider a $5$-cycle $C=a, b, c, d, e, a$ in $G$.  Since $n\ge 10$ and $G$ is 2-connected, there exists a vertex $x_1\not\in V(C)$ such that $x_1v\in E(G)$ for some $v\in V(C)$.  Without loss of generality, say $ax_1\in E(G)$.  Then $a$--$x_1, b, e$ is an induced claw in $G$, thus either $x_1b$, $x_1e$, or $be$ must be an edge in $G$.  If $be$ is an edge then $C$ is a chorded $5$-cycle and we are done with this case.  By symmetry, adding $x_1b$ or $x_1e$ as an edge is equivalent, so without loss of generality assume $x_1b\in E(G)$.  \\
\vspace{.2cm}

~~~Now $x_1, b, c, d, e$ is an induced $P_5$, so either $x_1c$, $x_1d$, $x_1e$, $bd$, $be$, or $ce$ must be an edge in $G$.  The edges $bd$, $be$, and $ce$ make $C$ a chorded $5$-cycle, and we are done. If $x_1d\in E(G)$ then $x_1, b, a, e, d, x_1$ is a $5$-cycle with chord $x_1a$ and we are done.  By symmetry, adding the edge $x_1c$ or adding $x_1e$ is equivalent, so assume $x_1c\in E(G)$.There are no chorded $C_5$'s nor induced $P_5$'s or $K_{1, 3}$'s, but since $n\ge 10$ and $G$ is 2-connected there must be some vertex $x_2\not \in V(C)$ such that $x_2\neq x_1$ and $x_2v\in E(G)$ for some $v\in V(C)$. \\ 
\vspace{.2cm}

~~~If $x_2 a$ (or $x_2c$, by symmetry) $\in E(G)$, then $a$--$x_2be$ is an induced claw subgraph in $G$ so $x_2b$, $x_2e$, or $be$ must be an edge of $G$.  Adding $be$ as an edge makes $C$ a chorded $5$-cycle. If $x_2b\in E(G)$, then $b, c, x_1, a, x_2, b$ is a $5$-cycle with chord $ab$. If $x_2e\in E(G)$ then $x_2, a, b, c, d$ is an induced $P_5$, so either $x_2b$, $x_2c$, $x_2d$, $ac$, $ad$, or $bd$ must be an edge in $G$.  Adding any of the edges except $x_2d$ will yield a chorded $5$-cycle.  So suppose $x_2d\in E(G)$.  There are no induced $P_5$ or $K_{1,3}$ subgraphs, but since $G$ is 2-connected and of order at least 10, there must be some vertex $x_3\not\in V(C)$ such that $x_3\neq x_1$ or $x_2$ and $x_3v\in E(G)$ for some $v\in V(C)\cup \{x_1\}$.  If $x_3a\in E(G)$, then $a$--$x_3be$ is an induced claw so $x_3b$, $x_3e$, or $be$ must be an edge in $G$. Adding any of these edges yields a chorded $5$-cycle.  If $x_3b$ (or, similarly $x_3e$) is an edge, then $b$--$x_3ac$ is an induced claw so either $x_3a$, $x_3c$, or $ac\in E(G)$.  Adding any of these edges yields a chorded $5$-cycle.   If $x_3c$ (or, similarly $x_3d$) is an edge then $c$--$x_3bd$ is an induced claw so either $x_3b$, $x_3d$, or $bd\in E(G)$.  Adding $x_3b$ or $bd$ yields a chorded $5$-cycle.  If $x_3d\in E(G)$ then $x_3, d, e, a, b$ is an induced $P_5$.  Adding any of the edges to eliminate this $P_5$ either creates a chorded $5$-cycle or results in a previously considered case (which all yielded chorded $5$-cycles).  If $x_1 x_3\in E(G)$, then $x_1$--$x_3ac$ is an induced claw so either $x_3a$, $x_3c$, or $ac\in E(G)$.  Adding any of these edges yields a chorded $5$-cycle in $G$.  This completes the case where $x_2a\in E(G)$.\\   
\vspace{.2cm}

~~~If $x_2b\in E(G)$, then $b$--$x_2ac$ is an induced claw so either $x_2 a$, $x_2c$ or $ac\in E(G)$.  Adding any of these edge will create a chorded $5$-cycle in $G$.  This completes the case where $x_2b\in E(G)$.\\
\vspace{.2cm}

~~~If $x_2d$ (or $x_2e$, by symmetry) $\in E(G)$, then $d$--$x_2ce$ is an induced claw so either $x_2c$, $x_2e$, or $ce\in E(G)$.  The edge $ce$ is a chord of $C$.  If $x_2c\in E(G)$, then $x_2, c, b, a, e$ is an induced $P_5$.  To eliminate this $P_5$, adding either $x_2a$, $x_2b$, $ca$, $be$, or $ce$ creates a chorded $5$-cycle.  The final edge that would eliminate the $P_5$ is $x_2e$.  Adding $x_2e$ creates a structure symmetric to $L$, which has been previously considered.  If $x_2e$ is an edge instead of $x_2c$ then $x_2, e, a, b, c$ is an induced $P_5$ in $G$.  Adding either edge $x_2a$ or $x_2c$ yields a structure symmetric to $L$.  Adding any one of the remaining edges to eliminate the $P_5$ yields a chorded $5$-cycle.  This completes the case where $x_2d\in E(G)$ and thus concludes the $m=5$ case. \\
\vspace{.25cm}







{\it Case 3.} Suppose $m\ge 6$. \\
\vspace{.2cm}
~~~There is an induced $P_5$ subgraph in every non-chorded $m$-cycle for $m\ge 6$, so every such $m$-cycle must contain at least one chord.  The three cases together show that there is a chorded cycle of every possible length $m$, for $4\le m\le n$, in $G$.  
\end{proof}
\vspace{.1in}

Unlike the straightforward case analysis method used to prove Theorems \ref{thm:p4ch} and \ref{thm:p5ch}, we took a different approach when forbidding $P_6$ from claw-free graphs, as otherwise the number of cases was problematic.  We use Lemma \ref{lem:clique} along with the following results to prove the $P_6$ result for sufficiently large graphs.   


\begin{lemma} Let $G$ be a $K_{1,3}$-free graph.  For any $x\in V(G)$ and any $k>2\in\mathbb{Z}$, if $deg_G(x)\ge 2k-1$ then there is a chorded $(k+1)$-cycle in $G$. 
\label{lem:k+1cc}
\end{lemma}

\begin{proof}
\flushleft
Consider a vertex $x\in V(G)$ such that $deg_G(x)\ge2k-1$.  Lemma \ref{lem:clique} implies that $N_G(x)$ is either connected and traceable, or two disjoint cliques. \\
\vspace{.1in}
{\it Case 1:} Suppose $N_G(x)$ is connected and traceable. \\Let $v_1, v_2, \ldots, v_{2k-1}$ be a Hamiltonian path in $N_G(x)$. Then $x, v_1, v_2, \ldots, v_k, x$ is a chorded $(k+1)$-cycle in $G$ with chord $xv_2$ (in fact, there are $k-2$ chords in this $(k+1)$-cycle). \\
\vspace{.1in}
{\it Case 2:} $N_G(x)$ is two disjoint cliques.\\ Partitioning the $2k-1$ vertices into two cliques, the smallest order that the larger of the two sets can be is $k$ (the $k$ and $k-1$ case).  Say the vertices  $\{v_1, v_2, \ldots, v_k\}$ form a clique in $N_G(x)$, then $x, v_1, v_2\dots, v_k, x$ is a chorded $(k+1)$ cycle in $G$ with chord $xv_2$. 
\end{proof}


\begin{theorem} {\rm\cite{ERS}} Let $f=F_d(p,\Delta)$ be the smallest integer such that every graph on $p$ vertices with at least $f$ edges has maximum degree $\Delta$ and diameter at most $d$.  Then:\\
$$f=F_d(p,\Delta)\ge {p\choose 2}\frac{\Delta-2}{(\Delta-1)^d-1}.$$
\label{thm:ers}
\end{theorem}





\begin{theorem} Let $G$ be a 2-connected graph of order $n> 3201$.  If $G$ is $\{K_{1,3}, P_6\}$-free and $G\neq C_n$, then $G$ is chorded pancyclic. 
\label{thm:p6cpan}
\end{theorem}
\begin{proof}
By Theorem \ref{thm:p6}, $G$ must be pancyclic, so now we must show $G$ contains a chorded cycle of every possible length $m$ for $4\le m\le n$. Note that for $m\ge 7$, every $m$-cycle must be chorded, otherwise it contains an induced $P_6$ subgraph.  Now we need to show there exists a chorded $4$-cycle, chorded $5$-cycle, and chorded $6$-cycle in $G$.  \\

~~~For some $x\in V(G)$, if $d_G(x)\ge 5$ then there exists a chorded $4$-cycle by Lemma \ref{lem:k+1cc} ($k=3$ case).  If $d_G(x)\ge 7$ then there exists a chorded $5$-cycle in $G$ by Lemma \ref{lem:k+1cc} ($k=4$ case). If $d_G(x)\ge 9$ then there exists a chorded $6$-cycle in $G$ by Lemma \ref{lem:k+1cc} ($k=5$ case).  Therefore, if $G$ contains a vertex of degree at least nine, then $G$ contains at least one chorded $4$-cycle, chorded $5$-cycle, and chorded $6$-cycle by Lemma \ref{lem:k+1cc} and is thus chorded pancyclic.  \\

~~~Suppose that $G$ is 8-regular (i.e. adding any edge will yield a vertex of degree nine and hence the desired result).  Then $G$ has maximum degree $\Delta=8$ and $G$ contains $\frac{8n}{2}=4n$ edges.  Note that $d$ is the diameter of $G$ if and only if $G$ is $P_l$-free for $l>d+2$. So since $G$ is $P_6$-free, the diameter of $G$ is $d\ge 4$.  By Theorem \ref{thm:ers}, we have

\begin{align*}
4n &\ge {n\choose 2}\frac{8-2}{(8-1)^4-1}\\
4n &\ge \frac{6n(n-1)}{2(7^4-1)}\\
4 &\ge \frac{3(n-1)}{2400},\\
{\text{Hence, }} n&\le 3201.
\end{align*}

Therefore, if $G$ is a 2-connected $\{K_{1,3}, P_6\}$-free graph of order $n>3201$, then $G$ contains a vertex of degree at least nine and thus is chorded pancyclic.  
\end{proof}
\vspace{.1in}

We feel the bound given on $n$ in Theorem \ref{thm:p6cpan} is sufficient but not necessary, so we make the following conjecture.   

\begin{conjecture} Let $G$ be a 2-connected graph of order $n\ge 10$.  If $G$ is $\{K_{1,3},P_6\}$-free and $G\neq C_n$, then $G$ is chorded pancyclic.  
\end{conjecture}















 

