



















\section{Introduction}
\noindent For any two graphs $G$ and $H$, the \textit{Ramsey number} $r(G,H)$ is the smallest positive integer $n$ such that $K_n\rightarrow (G,H)$.   The \textit{classical Ramsey number} $r(s, t)$ is defined as $r(K_s,K_t)$ and the \textit{diagonal Ramsey number} is defined as  $r(K_n,K_n)$.  These numbers have been studied extensively in the last five decades. The difficulty in exact determination of \textit{diagonal Ramsey number} $r(n, n)$, swifts expeditiously from the apparent $r(3,3)=6$ to the unmanageable $r(5,5)$. Currently, the best known lower and upper bounds for $r(5,5)$ are  43 and 48 (see \cite{Ra}). Many interesting variations of the basic problem of finding  classical Ramsey numbers have emerged. One such variation  is the calculation of the number of \textit{Ramsey critical  $(G,H)$ graphs}, for any pair of graphs $(G,H)$. In this paper,  we show that there are exactly 68  Ramsey critical $r(C_n, K_6)$   graphs, for all $n$ exceeding fourteen.  


\vspace{14pt}

\section{Notation}
\noindent The \textit{complete graph} on $n$ vertices, a \textit{cycle} on  $n$ vertices and a \textit{Star} on $n+1$ (see \cite{JaSa}) vertices are denoted by $K_n$, $C_n$  and $K_{1,n}$ respectively. Given a graph $G$ and a vertex $v \in V(G)$, we define the \textit{neighbourhood of $v$ in $G$},  $\Gamma(v)$, as the set of vertices adjacent to $v$ in $G$. The \textit{degree} of a vertex $v$, $d(v)$, is defined as the cardinality of  $ $ $\Gamma(v)$, $ $ i.e. $d(v)=| \Gamma(v)|$. The minimum degree of a graph $G(V,E)$ denoted by $\delta(G)$ is defined as  $ $ $ \min\{ d(v) | v\in V  \}$. 

\vspace{8pt}




\noindent Given a graph $G$, we say $I \subseteq V(G)$ is an \textit{independent set}, if no pair  of  vertices of $I$ is adjacent to each other in $G$. Equivalently, $I$ forms a clique in $G^c$.  Given a graph $G=(V,E)$, we define \textit{the independence number}, $\alpha(G)$, as the size of the largest independent set. Thus, $\alpha(G)=\max \{ \left| I\right| : I$ is an independent set of $G \}$. In the special case of $H=K_m$, alternatively $r(G,K_m)$ can be viewed as the smallest positive integer $n$ such that every graph  of order $n$ either contains $G$ as a subgraph or else satisfies $\alpha(G) \geq m$. For a non-empty subset $S$ of $V$, \textit{the induced subgraph of $S$ in $G$} denoted by $G[S]$ is defined as the  subgraph obtained by deleting all the vertices of $S^c$ from $G$. For two disjoint subgraphs $H$ and $K$ of $G$, we denote the set of edges between $H$ and $K$ by $E(H,K)$.  



\vspace{10pt}


\section{Lemmas used to generate  Ramsey critical $(C_n,K_6)$  graphs for $n \geq 15$}

In an attempt to prove Bondy and Erd{\"o}s conjecture  $r(C_n,K_m) = (n-1)(m-1)+1$, for all $(n,m)\neq(3,3)$ satisfying $n \geq m \geq 3$ under certain restrictions, Schiermeyer has proved that  $r(C_n,K_6) = 5(n - 1)+1$, for $n \geq 6$  (see \cite{Ra,Sc}). Characterizing all  Ramsey critical $(C_n,K_6)$ graphs boils down to  finding all (red/blue) colorings of $K_{r(C_n,K_6)-1}$ such that there is no red $C_n$ or a blue $K_6$. This is achieved by finding all $C_n$-free graphs on $K_{r(C_n,K_6)-1}$ vertices such that $\alpha(G)<6$. We first  prove that any $C_n$ -free graph (where $n \geq 15$) of order $5(n-1)$ with $\alpha(G) \leq 5$  contains a $5K_{n-1}$. To prove this, we use seven lemmas of which the first three are already proven results. For ease of reference, we reiterate Lemma \ref{l1a} from \cite{JaRo1}, Lemma  \ref{l1b} from \cite{Ja} and Lemma  \ref{l2}  by Bollob{\'a}s et al from \cite{BoJaSh}.
\vspace{10pt}


\begin{lemma}
\label{l1a}
\noindent (\cite{JaRo1}, Lemma 2; \cite{JaRo1}). A $C_n$- free graph $G$ of order $N$  with independent number  less than or equal to $m$ has minimal degree  greater than or equal to $N-r(C_n,K_{m})$.
\end{lemma}

\vspace{2pt}

\begin{lemma}
\label{l1b}
\noindent (\cite{Ja}, Lemma 8).  A $C_n$- free graph (where $n \geq 7$) of order $4(n-1)$ with no independent set of 5 vertices  contains a  $4K_{n-1}$.
\end{lemma}



\vspace{2pt}

\begin{lemma} (\cite{BoJaSh}, Lemma 5)
\label{l2}
\noindent Suppose $G$ contains the cycle $(u_1, u_2, ... , u_{n-1}, u_1)$ of length $n - 1$ but
no cycle of length $n$. Let $Y = V(G) \setminus \{u_1, u_2, ... , u_{n-1}\}$. Then,

\vspace{8pt}
\noindent \textbf{(a)} No vertex $x \in Y$ is adjacent to two consecutive vertices on the cycle.

\vspace{8pt}
\noindent \textbf{(b)} If $x \in Y$ is adjacent to $u_i$ and $u_j$ then $u_{i+1}u_{j+1} \notin E(G)$.

\vspace{8pt}
\noindent \textbf{(c)} If $x \in Y$ is adjacent to $u_i$ and $u_j$ then no vertex $x' \in Y$ is adjacent to both
$u_{i+1}$ and $u_{j+2}$.

\vspace{8pt}
\noindent \textbf{(d)} Suppose $\alpha(G) = m - 1$ where $m \leq  \frac {n + 2}{2}$ and $\{x_1, x_2, ... ,x_{m -1} \} \subseteq Y$ is an $(m - 1)$-element independent set. Then, no member of this set is adjacent to $m -2$ or more vertices on the cycle (We have taken the liberty of making a slight correction to the inequality $m \leq \frac {n + 2}{2}$ of the original \cite{BoJaSh}, Lemma 5(d)).
\end{lemma}

\vspace{12pt}




\noindent The next lemma plays a pivotal role in proving the main results of this paper. 

\vspace{4pt}
\begin{lemma}
\label{l3}
\noindent A $C_n$ -free graph (where $n \geq 15$) of order $5(n-1)$ with no independent set of 6 vertices contains a $5K_{n-1}$.
\end{lemma}

\noindent {\bf Proof.} We shall assume that in each of the three cases  $n = 15$, $n = 16$ and $n \geq 17$ we consider,  $G$ as a  graph on $5(n-1)$ vertices  satisfying $C_n \not \subseteq G$ and $\alpha(G) \leq 5$. Since  $r(C_{n-1}, K_6)=5n-9 \leq 5(n-1)$ (see \cite{BoJaSh,Ra}), there exists a cycle $C=(u_1, u_2, ... , u_{n-1}, u_1)$ of length $n - 1$ in $G$. In consistent with the notation of \cite{BoJaSh}, define $H$  as the induced subgraph of $G$ not containing the vertices of the cycle $C$. Then, $|V(C)|=n-1$ and $|V(H)|=4(n-1)$. 

\vspace{6pt}




\noindent Suppose  there exists an independent set $Y=\{y_1, y_2,y_3, y_4, y_5 \}$ of size 5 in $H$, so that $\alpha(G)=5$. From  Lemma \ref{l2} (as $5\leq \frac{n+2}{2}$), it follows that no vertex of $Y$ is adjacent to four or more vertices of the $C_{n-1}$. Thus, $\left| E(Y,V(C)) \right| \le 15$.  For ease of reference, we define such a graph structure as a  \textbf{Standard Configuration ($n$)}.

\vspace{10pt}


\noindent \textbf{Case 1: $n \geq 17$}

\vspace{6pt}
\noindent  Now, $\left| E(Y,V(C)) \right| \le 15 < n-1$. Thus, there exists a vertex $x\in V(C)$ adjacent to no vertex of $Y$. This gives, an independent set $Y \cup \{x\}$ of size 6, a contradiction. 



\vspace{10pt}
\noindent \textbf{Case 2: $n = 16$}

\vspace{6pt}  
\noindent In this case as $n-1=15$, in order to avoid an independent set of size 6, each vertex of $V(C)$ must be adjacent to at least one vertex of $Y$. Thus, we get that for each  $1\leq i\leq 5$,  $\left|\Gamma (y_i) \cap V(C) \right|=3$ and for each $1\leq j  < j' \leq 5$, $\Gamma (y_j) \cap \Gamma (y_{j'}) \cap V(C)=\phi$.

\vspace{10pt}

\noindent By Lemma \ref{l1a}, as $\delta(G) \geq 14$,  $\left|\Gamma (y_i) \cap V(H \setminus Y)\right| \geq 11$ for  $i=1,2$. Since $r(P_3,K_6)=11$ and $\alpha(G) < 6$, each of $G[\Gamma (y_1) \cap V(H \setminus Y)]$ and  $G[\Gamma (y_2) \cap V(H \setminus Y)]$ contains a copy of $P_3$. Thus, $P_3 \subseteq \Gamma (y_1) \cap V(H \setminus Y)$, where the $P_3$ is induced by  $\{x,y,z\}$ such that $(x,y), (y,z) \in E(G)$ and $P_3 \subseteq \Gamma (y_2) \cap V(H \setminus Y)$,  where this $P_3$ is induced by  $\{p,q,r\}$ such that $(p,q), (q,r) \in E(G)$.

\vspace{10pt}

\noindent Suppose that $x$ is not adjacent to any vertex of $\{y_2,y_3,y_4,y_5\}$ and $p$ is not adjacent to any vertex of $\{y_1,y_3,y_4,y_5\}$. Re-order the vertices of the cycle such that $y_1\in Y$ is adjacent to $u_1$. In this ordering, let $y_1$ be also adjacent to $u_t$ where $2 \leq t \leq 15$. 



\begin{center}
\input{graph1.tex}
\end{center}
\begin{center}
Figure 1. Configuration for $n=16$
\end{center}



\noindent By Lemma \ref{l2}(a), $t \neq 2$. In order to avoid an independent set of size 6, induced by $\{x,u_t,y_2,y_3,y_4,y_5\}$, we get that $(x,u_t) \in E(G)$. However, $t \neq 3$, in order to avoid a  $C_{16}$ comprising $(u_1,y_1,x, u_3,...,u_{15},u_1)$. Also, $t \neq 4$ in order to avoid a $C_{16}$ comprising  $(u_1,y_1,y,x,u_4,...,u_{15},u_1)$  and $t \neq 5$ in order to avoid a $C_{16}$ comprising  $(u_1,y_1,z,y,x, u_5,...,u_{15},u_1)$.


\vspace{8pt}
\noindent Thus, any pair of vertices adjacent to $y_1$ in $C$ cannot be separated by a path of length 1, 2, 3 or 4  along $C$. Thus, $\Gamma (y_1) \cap C =\{u_1,u_6,u_{11}\}$. In this scenario, we use the prerogative that $(y_2,u_2)\in E(G)$. Then,  by the previous argument $\Gamma (y_2) \cap C =\{u_2,u_7,u_{12}\}$. But by Lemma \ref{l2}(b),  $(u_2,u_7)\notin E(G)$. Henceforth, we will get that $\{u_2,u_7,y_1,y_3,y_4,y_6\}$  is an independent set of size 6, a contradiction. 
\vspace{10pt}


\noindent This implies that there is a vertex of $X=\{x,y,z\}$ adjacent to some vertex of $\{y_2,y_3,y_4,y_5\}$ or there is a vertex of $\{p,q,r\}$ adjacent to some vertex of $\{y_1,y_3,y_4,y_5\}$. Therefore, without loss of generality, we may assume that $y_1$ is adjacent to $X=\{x,y,z\} \subseteq V(H \setminus Y)$ and $y_1$ is adjacent to $X'=\{x',y',z'\} \subseteq V(C)$ where $X'$ induces a  $P_3$  and $y_2$ is adjacent to $x$. Next since $C$ has 15 points without loss of generality, $\{x',y',z'\}=\{u_1,u_3,u_5\}$ or $\{x',y',z'\}=\{u_1,u_3,u_6\}$ or $\{x',y',z'\}=\{u_1,u_3,u_7\}$  or  $\{x',y',z'\}=\{u_1,u_3,u_8\}$ or  $\{x',y',z'\}=\{u_1,u_3,u_9\}$ or $\{x',y',z'\}=\{u_1,u_4,u_7\}$ or $\{x',y',z'\}=\{u_1,u_4,u_8\}$ or $\{x',y',z'\}=\{u_1,u_4,u_9\}$ or $\{x',y',z'\}=\{u_1,u_4,u_{10}\}$ or $\{x',y',z'\}=\{u_1,u_5,u_9\}$ or $\{x',y',z'\}=\{u_1,u_5,u_{10}\}$ or $\{x',y',z'\}=\{u_1,u_6,u_{11}\}$. Moreover, as $y_1$ and $y_2$ are connected by paths of lengths 2, 3 and 4 in $H$, no pair of vertices selected from  $\Gamma (y_1) \cap V(C)$ and  $\Gamma (y_2) \cap V(C)$ can be separated by a path of length 3, 4 or 5 along the cycle $C$. Using this  we argue that when $\{x',y',z'\}=\{u_1,u_3,u_5\}$, $\Gamma (y_2) \cap V(C) = \phi$,  when $\{x',y',z'\}=\{u_1,u_3,u_6\}$, $\Gamma (y_2) \cap V(C) = \phi$ and when  $\{x',y',z'\}=\{u_1,u_3,u_7\}$, $\Gamma (y_2) \cap V(C) \subseteq \{u_9\}$.  Similarly, when $\{x',y',z'\}=\{u_1,u_3,u_8\}$, $\Gamma (y_2) \cap V(C) \subseteq \{u_2,u_9,u_{10}\}$, when $\{x',y',z'\}=\{u_1,u_3,u_9\}$, $\Gamma (y_2) \cap V(C) \subseteq \{u_2,u_{10}\}$, when $\{x',y',z'\}=\{u_1,u_4,u_7\}$, $\Gamma (y_2) \cap V(C) = \phi$ and when $\{x',y',z'\}=\{u_1,u_4,u_8\}$, $\Gamma (y_2) \cap V(C) \subseteq \{u_2,u_{10}\}$. When $\{x',y',z'\}=\{u_1,u_4,u_9\}$, $\Gamma (y_2) \cap V(C) \subseteq \{u_2,u_3,u_{10}\}$, when $\{x',y',z'\}=\{u_1,u_4,u_{10}\}$, $\Gamma (y_2) \cap V(C) \subseteq \{u_2,u_3\}$,  when $\{x',y',z'\}=\{u_1,u_5,u_9\}$, $\Gamma (y_2) \cap V(C) \subseteq \{u_3,u_7\}$ and when $\{x',y',z'\}=\{u_1,u_5,u_{10}\}$, $\Gamma (y_2) \cap V(C) \subseteq \{u_{3}\}$ and  when $\{x',y',z'\}=\{u_1,u_6,u_{11}\}$, $\Gamma (y_2) \cap V(C) =\phi$. Since none of these give a viable configuration, we get a contradiction.  

\vspace{8pt}
\noindent \textbf{Case 3: $n = 15$}

\vspace{8pt}

\noindent To deal with the case $n = 15$, we first prove three Lemmas. Lemma $\ref{l31}$, deals with the possible scenarios generated by the Standard Configuration ($15$). Lemmas $\ref{l32}$ and $\ref{l33}$ deal with showing that none of the scenarios generated by Lemma $\ref{l31}$ give viable configurations.


\vspace{4pt}  

\begin{lemma}
\label{l31}
\noindent In the Standard Configuration $(n=15)$, one of the following three scenarios $(a)$, $(b)$ and $(c)$ will occur:


\vspace{8pt}
\noindent \textbf{(a)} $y_1 \in Y$ is a vertex of the subgraph $K_4$ (see Figure 2(a)) in $H$.\vspace{8pt}



\vspace{8pt}
\noindent \textbf{(b)} $y_1,y_2\in Y$ are vertices of the subgraph $K$ (see Figure 2(b1)) or subgraph $K'$ (see Figure 2(b2)) in $H$.

\vspace{8pt}
\noindent \textbf{(c)} $y_1,y_2\in Y$ are vertices of the subgraph $L$ (see Figure 2(c)) in $H$.
\end{lemma}

\begin{center}
\input{graph1b.tex}
\end{center}
\hspace{20pt} \textit{scenario (a)}                 \hspace{85pt}           \textit{scenario (b)}  \hspace{88pt}     \textit{scenario (c)}
\vspace{8pt}
\begin{center}
Figure 2: (a),(b1), (b2) and (c). The first three scenarios, \textit{scenario} (a),  \textit{scenario} (b) and \textit{scenario} (c) of the Standard Configuration $(n=15)$.
\end{center}


\noindent {\bf Proof.} 
\noindent As in the case of $n=16$, we get that without loss of generality $1\leq i\leq 4$, $\left|\Gamma (y_i) \cap V(C)\right| =3$ and for each $1\leq j  < j' \leq 4$, $\Gamma (y_j) \cap \Gamma (y_{j'}) \cap V(C)=\phi$.
Also $\left|\Gamma (y_5) \cap V(C)\right| \in \{ 2,3\}$. In particular, if $\left|\Gamma (y_5) \cap V(C)  \right|=2$ then, for each $1\leq j  < j' \leq 5$, $\Gamma (y_j) \cap \Gamma (y_{j'}) \cap V(C)=\phi$ and if  $\left|\Gamma (y_5) \cap V(C)\right| =3$ then, for each $1\leq j < j' \leq 5$, 
\[
\left|\Gamma (y_j) \cap \Gamma (y_{j'}) \cap V(C)\right|=
\begin{cases} 
$ $ 1 & \text{if }  j,j' \in \{4,5\}, \\
\hspace{20pt} & \\
$ $ 0 & \text{otherwise. }    \\
\end{cases}
\]



\vspace{8pt}

\noindent By Lemma \ref{l1a}, as $\delta(G) \geq 13$, we get that $\left|\Gamma (y_i) \cap V(H \setminus Y)\right| \geq 10$.  Suppose that there is some $1\leq i\leq 3$ (say $i=1$) such that $\left|\Gamma (y_i) \cap V(H \setminus Y)\right|\geq 11$. Then as $r(P_3,K_6)=11$ we get scenario $(a)$. Next, assume that for all $1\leq i\leq 3$,  $\left|\Gamma (y_i) \cap V(H \setminus Y)\right|=10$.  By the classification of the Ramsey critical $(P_3,K_6)$ graphs, we get that for all $1\leq i\leq 3$, $G[\Gamma (y_i) \cap V(H \setminus Y)] \supseteq 5K_2$. 

\vspace{8pt}

\noindent This gives  two possibilities. The first possibility is $\left|{\cup}_{i=1}^3 \Gamma (y_i) \cap V(H \setminus Y)\right|=10$. In this case, as for all $1\leq i\leq 3$, $5K_2 \subseteq G[\Gamma (y_i) \cap V(H \setminus Y)]$ we get scenario $(c)$.
The second possibility if $\left|{\cup}_{i=1}^3 \Gamma (y_i) \cup V(H \setminus Y)\right|\geq 11$. Without loss of generality, we may assume that $\left| \Gamma (y_1) \cup  \Gamma (y_2) \cup V(H \setminus Y)\right|\geq 11$.  Let $x_{11}$ be any vertex of $\Gamma (y_2)   \cap (\Gamma (y_1))^c \cup V(H \setminus Y)$. Since  $r(P_3,K_6)=11$, we get that $G[\Gamma (y_1) \cup V(H \setminus Y) \cup \{x_{11}\}]$ contains a subgraph $P$ isomorphic to a $P_3$. If  $P$ is contained in $G[\Gamma (y_1) \cup V(H \setminus Y)]$ we  get scenario $(a)$. Otherwise, $x_{11} \in P$. However, $x_{11}$ is an element of $5K_2 \subseteq G[\Gamma (y_2) \cap V(H \setminus Y)]$ and therefore, $x_{11}$ is adjacent to some other vertex say $w$ in $G[\Gamma (y_2) \cap V(H \setminus Y)]$. Depending on whether or not $w$ belongs to $V(P)$,  we get scenarios $(b2)$ or $(b1)$ respectively. Hence the Lemma.  
\vspace{4pt}

\begin{lemma}
\label{l32}
\noindent In the Standard Configuration $(n=15)$,  $y_1\in Y$ can not be a vertex of a  $K_4$  in $H$ (see Figure 2(a)).
\end{lemma}

\noindent {\bf Proof.} As indicated in Figure 2(a), let  $x \in \Gamma (y_1) \cap V(H \setminus Y)$. 
Then we get two possibilities depending on whether or not  $x$ is  adjacent to a vertex of $\{y_2,y_3,y_4,y_5\}$. In the first possibility,  $x$ is adjacent to some vertex of  $Y$ (say $y_2$). Then, as $y_1$ and $y_2$ are connected by paths of lengths 2, 3 and 4 in $H$, no pair of vertices selected from of $\Gamma (y_1) \cap V(C)$ and  $\Gamma (y_2) \cap V(C)$ can be separated by a path of length 3, 4 or 5 along the cycle $C$. However, as argued in $n=16$, we get that $\left|\Gamma (y_2) \cap V(C)\right| \leq 2$ and $\left|\Gamma (y_2) \cap V(C)\right| = 2$ only when $\{x',y',z'\}=\{u_1,u_3,u_{8}\}$, $\{x',y',z'\}=\{u_1,u_4,u_{9}\}$ or $\{x',y',z'\}=\{u_1,u_5,u_{9}\}$. This gives a contradiction. In the second possibility, re order the vertices of the cycle such that $y_1\in X$ is adjacent to $u_1$. In this ordering, suppose further that $y_1$ is also adjacent to $u_t$ where $2 \leq t \leq 14$.  By the argument used in $n=16$, we get that any pair of vertices adjacent to $y_1$ in $C$ cannot be separated by a path of length 1, 2, 3 or 4  along  $C$. However, this again leads to a contradiction.  
\vspace{14pt}

\begin{lemma}
\label{l33}
\noindent In the Standard Configuration $(n=15)$, the vertices $y_1,y_2\in Y$ can not be  vertices of the  subgraph $K$, $K'$ or $L$ in $H$ (see Figure 2).
\end{lemma}


\noindent {\bf Proof.} In the case $y_1,y_2 \in K$, since $y_1$ and $y_2$ are connected by paths of lengths 3, 4 and 5 in $H$, no pair of vertices selected from of $\Gamma (y_1) \cap V(C)$ and  $\Gamma (y_2) \cap V(C)$ can be separated by a path of length 4, 5 or 6 along the cycle $C$. The cardinality of the possible vertex sets of  $\Gamma (y_i) \cap V(C)$ ($i=1,2$), subject to this condition, are presented in Table 1. 

\begin{center}
\begin{tabular}{ ||p{1.89cm}||p{4.55cm}||p{6.8cm}|| } 
 \hline
\begin{center}$\{x',y',z'\}$ equals \end{center}
  & 
	\begin{center}$\Gamma (y_2) \cap V(C)$ is contained in \end{center}	 
	& 
	\begin{center}Cardinality of $\Gamma (y_2) \cap V(C)$ \end{center} \\

 \hline
$\{u_1,u_3,u_5\}$     &   $\{u_2,u_4\}$   &  $\left|\Gamma (y_2) \cap V(C)\right| \leq 2$  \\
 \hline 
$\{u_1,u_3,u_6\}$     &   $\{u_4\}$   &  $\left|\Gamma (y_2) \cap V(C)\right|  \leq  1$  \\
 \hline 
$\{u_1,u_3,u_7\}$     &   $\{u_4,u_{14}\}$  &  $\left|\Gamma (y_2) \cap V(C)\right|  \leq 2$  \\
 \hline 
$\{u_1,u_3,u_8\}$     &   $ $  $  $ $\phi$     &  $\left|\Gamma (y_2) \cap V(C)\right| = 0$  \\
 \hline 
$\{u_1,u_3,u_9\}$     &   $\{u_{2}\}$    &  $\left|\Gamma (y_2) \cap V(C)\right| \leq  1$  \\
 \hline 
$\{u_1,u_4,u_7\}$     &   $ $  $  $ $\phi$   &  $\left|\Gamma (y_2) \cap V(C)\right| =0$   \\
 \hline 
$\{u_1,u_4,u_8\}$     &   $ $  $  $ $\phi$  &  $\left|\Gamma (y_2) \cap V(C)\right| =0$  \\
 \hline 
$\{u_1,u_4,u_9\}$     &   $\{u_2\}$   &  $\left|\Gamma (y_2) \cap V(C)\right|  \leq 1$  \\
 \hline 
$\{u_1,u_5,u_9\}$     &   $\{u_2,u_8,u_{12}\}$  & $\left|\Gamma (y_2) \cap V(C)\right|  \leq  3$ \\
\hline 
$\{u_1,u_5,u_{10}\}$  &   $\{u_3,u_8,u_{12}\}$  & $\left|\Gamma (y_2) \cap V(C)\right|  \leq  3$ \\
 \hline 
\end{tabular}
\end{center}
\begin{center}
Table 1: Cardinality of $\Gamma (y_2) \cap V(C)$: Graph $K$.
\end{center}


\vspace{8pt}

\noindent Because  $\Gamma (y_2) \cap V(C)=3$, we are only left to deal with the last two possibilities of Table 1 for $\Gamma (y_2) \cap V(C)$. In both possibilities, $\Gamma (y_1) \cap V(C)$ will induce a $C_3$ by Lemma \ref{l2}(b). In the first possibility, $\Gamma (y_1) \cap V(C)=\{u_1,u_5,u_9\}$  gives rise to the 15-cycle given by  $(u_1,u_5,...,u_8,y_2,y,x,y_1, u_9,...,u_{14},u_1)$, a contradiction.  In the second possibility, $\Gamma (y_1) \cap V(C)=\{u_1,u_5,u_{10}\}$  gives rise to the 15-cycle given by $ (u_1,u_5,u_6,...,u_8,y_2,z,y,x,y_1,u_{10},...,u_{14},u_1)$, a contradiction. 



\vspace{8pt}

\noindent In the case $y_1,y_2 \in K'$, since $y_1$ and $y_2$ are connected by paths of lengths 2, 3 or 4 in $H$, no pair of vertices selected from of $\Gamma (y_1) \cap V(C)$ and  $\Gamma (y_2) \cap V(C)$ can be separated by a path of length 3, 4 or 5 along the cycle $C$. The cardinality of the possible vertex set of  $\Gamma (y_1) \cap V(C)$ is presented in Table 2 and each of these leads to a contradiction as $\Gamma (y_2) \cap V(C)<3$

\vspace{10pt}

\begin{center}
\begin{tabular}{ ||p{1.9cm}||p{2.7cm}||p{4.7cm}|| }
 \hline
\begin{center}$\{x',y',z'\}$ equals \end{center}
  & 
	\begin{center}$\Gamma (y_2) \cap V(C)$ is contained in \end{center}
	  & 
	\begin{center}Cardinality of $\Gamma (y_2) \cap V(C)$ \end{center}
		\\
 \hline
$\{u_1,u_3,u_5\}$     &   $ $  $  $ $\phi$   &  $\left|\Gamma (y_2) \cap V(C)\right| =0$    \\
$\{u_1,u_3,u_6\}$     &   $ $  $  $ $\phi$   &  $\left|\Gamma (y_2) \cap V(C)\right| =0$   \\
$\{u_1,u_3,u_7\}$     &   $\{u_9\}$ &  $\left|\Gamma (y_2) \cap V(C)\right| \leq 1$   \\
$\{u_1,u_3,u_8\}$     &   $\{u_2,u_9\}$  &  $\left|\Gamma (y_2) \cap V(C)\right| \leq 2$    \\
$\{u_1,u_3,u_9\}$     &   $\{u_2\}$  &  $\left|\Gamma (y_2) \cap V(C)\right| \leq 1$    \\
$\{u_1,u_4,u_7\}$     &   $ $  $  $ $\phi$  &  $\left|\Gamma (y_2) \cap V(C)\right| =0$    \\
$\{u_1,u_4,u_8\}$     &   $\{u_2\}$ &  $\left|\Gamma (y_2) \cap V(C)\right| \leq 1$    \\
$\{u_1,u_4,u_9\}$     &   $\{u_2,u_3\}$ &  $\left|\Gamma (y_2) \cap V(C)\right| \leq 2$   \\
$\{u_1,u_5,u_9\}$     &   $\{u_3,u_7\}$  &  $\left|\Gamma (y_2) \cap V(C)\right| \leq 2$   \\
$\{u_1,u_5,u_{10}\}$  &   $\{u_3\}$  &  $\left|\Gamma (y_2) \cap V(C)\right| \leq 1$     \\
 \hline
\end{tabular}
\end{center}
\begin{center}
Table 2: Cardinality of $\Gamma (y_2) \cap V(C)$: Graph $K'$.
\end{center}
\vspace{4pt}

\noindent In the case $y_1,y_2 \in K'$, since  $y_1$ and $y_2$ are connected by paths of lengths 2, 3, 4 and 5 in $H$, no pair of vertices selected from of $\Gamma (y_1) \cap V(C)$ and  $\Gamma (y_2) \cap V(C)$ can be separated by  paths of length 3, 4, 5 or 6 along the cycle $C$. Thus, Table 2 will give us the required contradiction. Similarly,  in the case $y_1,y_2 \in L$, since  $y_1$ and $y_2$ are connected by paths of lengths 2, 3, 4, 5 and 6 in $H$, no pair of vertices selected from of $\Gamma (y_1) \cap V(C)$ and  $\Gamma (y_2) \cap V(C)$ can be separated by  paths of length 3, 4, 5, 6 or 7 along the cycle $C$. As before, for all possibilities  $\left|\Gamma (y_2) \cap V(C)\right| <3$, a contradiction. Thus, lemmas 5, 6 and 7 imply that $H$ cannot have an independent set of size 5.


\vspace{8pt}
\noindent Having proved that  $H$ cannot have an independent set of size 5 in all three cases $n=15,16$ and 17,  we next continue with the main proof. Since, $H$  satisfies all conditions of Lemma  \ref{l1b}, $H$ contains a $4K_{n-1}$. 



\vspace{8pt}
\noindent Next we show that $V(C_{n-1})$ induced a $K_{n-1}$. Suppose that there exists two vertices  of $V(C)$, say $v$ and $w$, such that $(v,w) \not \in E(G)$. In order to avoid a $C_n$ both $v$ and $w$ will have to be adjacent to at most one vertex of each of the four copies of $K_{n-1}$ in $H$. Moreover, any vertex of any copy of $K_{n-1}$ in $H$ will have to be adjacent to at most one vertex of another copy of a $K_{n-1}$ in $H$. Thus, each copy of a $K_{n-1}$  will have at most 5 vertices adjacent to some vertex outside that of $K_{n-1}$, in $V(H) \cup \{v,w\}$. Since $(n-1)-5 \geq 1$, we can select $x_1$ in the first $K_{n-1}$, $x_2$ in the second $K_{n-1}$, $x_3$ in the third $K_{n-1}$ and $x_4$ in the fourth $K_{n-1}$ such that $\{x_1, x_2, x_3, x_4\}$ is an independent set of size four and no vertex of $\{x_1, x_2, x_3, x_4\}$ is adjacent to any vertex of $\{v, w\}$. Hence $\{x_1, x_2, x_3, x_4, v, w\}$ is an independent set of size 6, a contradiction. Therefore, we get that any two pair of vertices of $V(C)$ are  connected by an edge. Hence, $G[V(C_{n-1})]=K_{n-1}$ as required. This $K_{n-1}$ along with the $4K_{n-1}$ contained in $H$  gives the required result. 

\section{ All Ramsey $(C_n,K_6)$ critical graphs for $n \geq 15$}

\noindent We have already observed that any Ramsey $(C_n,K_6)$ critical graph will consist of a red graph containing $5K_{n-1}$, with respect to the red/blue coloring. Let $\{V_i : $ $ i \in \{1,2,...,5\} \}$ be the vertex set of  the five $K_{n-1}$ graphs.  We notice that there are two types of Ramsey $(C_n,K_6)$ critical graphs. The first type (Type1) of Ramsey $(C_n,K_6)$ critical graphs will satisfy the condition that at most one vertex of each $V_i$ is adjacent to any other vertex in $V_i^c$. The second type (Type2) of Ramsey $(C_n,K_6)$ critical graphs  will satisfy the condition that there exists a  $V_k$ for some $1 \leq k \leq 5$ such that at least two vertices of $V_k$ have neighbors in  $V_k^c$. Moreover, it is  worth noting that a  Type1 critical graph is completely determined by the structure of the external edges between $V_i$'s and not by the $\binom{n}{2}$ edges inside each of the five $V_i$'s. This fact is taken into consideration when representing the Ramsey $(C_n,K_6)$ critical graphs.
\vspace{10pt}

\noindent Each subgraph of $K_5$ generates a unique Ramsey $(C_n,K_6)$ critical graph of Type1. Thus, as illustrated in the following figure, there are 34 critical graphs ($R_i$,$ $  $1 \leq i \leq 34$) of Type1 generated by the 34 subgraphs of $K_5$. 
\vspace{2pt}

\begin{center}
\input{graph81.tex}
\vspace{4pt}
\input{graph82.tex}
\vspace{4pt}
\input{graph83.tex}
\vspace{4pt}
\input{graph84.tex}
\vspace{4pt}
\input{graph85.tex}
\vspace{4pt}
\input{graph86.tex}
\vspace{12pt}

Figure 3. Ramsey $(C_n,K_6)$ critical graphs of Type1, $R_i$ ($1 \leq i \leq 34$) 
\end{center}
\vspace{8pt}


\noindent First note that each and every Type2 critical graph is obtained by an appropriate vertex splitting of some Type1 critical graph. As illustrated in the Figure 4, there are exactly 34 Type2 critical graphs (labeled $S_i$ where $1 \leq i \leq 34$) generated by 18 critical graphs of Type1, since exactly sixteen Type1 critical graphs do not generate  Type2 critical graphs. 

\vspace{2pt}

\begin{center}
\input{graph91.tex}
\vspace{4pt}
\input{graph92.tex}
\vspace{4pt}
\input{graph93.tex}
\vspace{4pt}
\input{graph94.tex}
\vspace{4pt}
\input{graph95.tex}
\vspace{4pt}
\input{graph96.tex}
\vspace{4pt}
\input{graph97.tex}
\vspace{4pt}
\input{graph98.tex}
\vspace{4pt}
\input{graph99.tex}
\vspace{4pt}
\input{graph910.tex}
\vspace{12pt}

Figure 4. Ramsey $(C_n,K_6)$ critical graphs of Type2 ($S_i$,  $1 \leq i \leq 34$)
\end{center}
\vspace{8pt}



\noindent Henceforth, we conclude that there are exactly 68  Ramsey $(C_n,K_6)$ critical graphs out of which 34 are  categorized as Type1 critical graphs (labeled $R_i$, $1 \leq i \leq 34$ ) and the balance 34 are categorized as Type2 critical graphs (labeled $S_i$, $1 \leq i \leq 34$).








