==== TABLE OF CONTENTS ====
Cycle-clique-Ramsey-numbers//01-introduction.tex
Cycle-clique-Ramsey-numbers//02-reduction.tex
Cycle-clique-Ramsey-numbers//03-clique-layers.tex
Cycle-clique-Ramsey-numbers//03-clique-rotations.tex
Cycle-clique-Ramsey-numbers//04-small.tex
Cycle-clique-Ramsey-numbers//05-size.tex
Cycle-clique-Ramsey-numbers//06-paths.tex
Cycle-clique-Ramsey-numbers//07-growth.tex
Cycle-clique-Ramsey-numbers//08-terminal.tex
Cycle-clique-Ramsey-numbers//09-finite-packing.tex
Cycle-clique-Ramsey-numbers//09-finite-patterns.tex
Cycle-clique-Ramsey-numbers//09-finite-results.tex
Cycle-clique-Ramsey-numbers//09-finite-rules.tex
Cycle-clique-Ramsey-numbers//10-implementation.tex
Cycle-clique-Ramsey-numbers//clique-figure.tex
Cycle-clique-Ramsey-numbers//main.tex
Cycle-clique-Ramsey-numbers//representative-figure.tex
Cycle-clique-Ramsey-numbers//references.bib
===========================

==== BEGIN Cycle-clique-Ramsey-numbers//01-introduction.tex ====
\section{Introduction}
\label{sec:introduction}

For finite simple graphs $H$ and $J$, the Ramsey number $R(H,J)$ is the
least integer $N$ such that every red--blue colouring of the edges of the
complete graph on $N$ vertices contains a red copy of $H$ or a blue copy of
$J$. Copies need not be induced. Write $C_m$ for the cycle on exactly $m$
vertices and $K_n$ for the complete graph on $n$ vertices.

\begin{theorem}\label{thm:main}
For all integers $m\ge n\ge3$ with $(m,n)\ne(3,3)$,
\[
 R(C_m,K_n)=(m-1)(n-1)+1.
\]
For the excluded pair, $R(C_3,K_3)=6$.
\end{theorem}

Theorem~\ref{thm:main} establishes the cycle--clique conjecture of
Erd\H{o}s, Faudree, Rousseau and Schelp
\cite{ErdosFaudreeRousseauSchelp1978}, in the formulation stated by
Keevash, Long and Skokan~\cite{KeevashLongSkokan2021}.
The cycle length in the theorem is exact. Its lower bound comes from
$n-1$ disjoint red cliques of order $m-1$, with all edges between them blue.
The task is to show that one additional vertex forces one of the two
specified graphs.

\subsection{Previous results and the parameter range}

The case $n=3$ goes back to Chartrand and Schuster
\cite{ChartrandSchuster1971}; see also Bondy and Erd\H{o}s
\cite[p.~47]{BondyErdos1973}. Bondy and Erd\H{o}s
\cite[Theorem~4]{BondyErdos1973} established the formula when
$m\ge n^2-2$. The complete conjectured range was established for $n=4$
by Yang, Huang and Zhang~\cite{YangHuangZhang1999}, for $n=5$ by
Bollob\'as and coauthors~\cite{BollobasEtAl2000}, for $n=6$ by
Schiermeyer~\cite{Schiermeyer2003}, and for $n=7$ by Chen, Cheng and
Zhang~\cite{ChenChengZhang2008}.
For $n=8$, further cases were established: $m=8$
\cite{JaradatAlzaleq2007,ZhangZhang2009}, $m=9$
\cite{BatainehJaradatAlZaleq2011}, and $10\le m\le15$
\cite{Baniabedalruhman2023}.
Theorem~1 of Nikiforov~\cite{Nikiforov2005} states the formula for
$n\ge4$ and $m\ge4n+2$.

Keevash, Long and Skokan~\cite[Theorem~1.1]{KeevashLongSkokan2021}
proved that an absolute constant $C\ge1$ suffices whenever
\begin{equation}\label{intro:kls}
 n\ge3,\qquad
 m\ge C\frac{\log_2 n}{\log_2\log_2 n}.
\end{equation}
This already contains every pair $m\ge n$ once $n$ is sufficiently large.
Indeed, the right-hand side of~\eqref{intro:kls} is $o(n)$.
For each of the finitely many smaller values of $n$, only finitely many
$m\ge n$ lie below that threshold. Thus their theorem leaves at most
finitely many pairs in the range of Theorem~\ref{thm:main}.
Our result completes that range. The finite calculation below comes from
an explicit structural reduction and does not require a numerical value
of the constant in~\eqref{intro:kls}.

\subsection{The proof}

Set $k=m-1$ and $a=n-1$. A failure of the upper bound gives a graph with
no cycle of order $k+1$ and independence number at most $a\le k$.
Holding $k$ fixed and minimizing $a$ produces a useful expansion property: every
nonempty independent set $I$ has at least $k|I|+1$ vertices in its closed
neighbourhood. In particular, the minimum degree is at least $k$.

The first structural step finds a clique of order
\[
 t\ge\max\{3,\lfloor k/2\rfloor\}.
\]
The proof uses distance layers in a rooted tree, followed by an explicit
path-rotation argument. Independent-set expansion and rooted distance
layers already appear in the cycle--clique argument of Erd\H{o}s,
Faudree, Rousseau and Schelp~\cite[Section~3]{ErdosFaudreeRousseauSchelp1978}.
We prove the particular quantitative statements needed here in
Sections~\ref{sec:reduction} and~\ref{sec:clique}.
The two smallest values $k=3,4$ are then settled directly.

For $k\ge5$, fix a maximum clique $Q$ of order $t$. Consider paths between
its vertices whose nonempty interiors lie outside $Q$ and are pairwise
disjoint, and whose endpoint pairs form disjoint chains. The total number
of interior vertices is called the \emph{amount} of the system. We maximize
this amount below $k+1-t$, breaking ties by minimizing the number of paths.
Certain improvements of this system would close to a cycle of order
exactly $k+1$; all such improvements are therefore forbidden.

These prohibitions make neighbourhoods of suitable path vertices
disjoint and anticomplete. Expansion then supplies independent sets
inside those neighbourhoods. A separate size lemma raises the available
independence bound from two to three when needed. For $t\ge9$, this
argument and a short numerical classification give more than $k$
independent vertices, a contradiction. Sections~\ref{sec:paths}--\ref{sec:terminal}
develop this part of the proof.

The remaining case has $3\le t\le8$, and the clique bound gives
$5\le k\le17$. A pattern records each chain by its sequence of
interior-vertex counts, up to chain reversal and permutation of components.
There are $3{,}099$ parameter-pattern instances across the $42$ admissible
pairs $(k,t)$. Section~\ref{sec:finite} proves the inference rules that
exclude them: path replacement, exact-cycle closure, neighbourhood
growth, independent-set packing, and contradiction under an added edge
or a path with one new interior vertex. The computation enumerates these
patterns, rather than graphs or edge colourings. Appendix~\ref{app:implementation}
describes two separate exact implementations and the accompanying
deduction traces. All structural arguments and all mathematical
inference rules are proved in the main text.
==== END Cycle-clique-Ramsey-numbers//01-introduction.tex ====

==== BEGIN Cycle-clique-Ramsey-numbers//02-reduction.tex ====
\section{A minimal counterexample and neighborhood expansion}
\label{sec:reduction}

All graphs in the proof are finite and simple. For a graph $H$, write
$\alpha(H)$ for its independence number, $\omega(H)$ for its clique
number, and $\delta(H)$ for its minimum degree. If $X\subseteq V(H)$,
then $H[X]$ is the induced subgraph on $X$ and $H-X$ is the induced
subgraph on $V(H)\setminus X$. We sometimes write $\alpha(X)$ for
$\alpha(H[X])$ when the ambient graph is clear. The open neighborhood
of a vertex $x$ is denoted by $N_H(x)$. For a set $X$, put
$N_H(X)=\bigcup_{x\in X}N_H(x)$, and
\[
  N_H[X]=X\cup\bigcup_{x\in X}N_H(x)
\]
is the closed neighborhood of a set $X$. Thus $N_H[x]=N_H[\{x\}]$.
The order of a path or cycle is its number of vertices, and its length
is its number of edges. In particular, a copy of $C_m$ always has
exactly $m$ vertices.

The upper bound is equivalent to the assertion that every graph on
$(m-1)(n-1)+1$ vertices contains either a cycle of order $m$ or an
independent set of order $n$: apply this assertion to the red graph of
a two-coloring. Set $k=m-1$ and $a=n-1$. In the range $m\ge n\ge3$
with $(m,n)=(3,3)$ excluded, these parameters satisfy
\[
  k\ge3,\qquad 2\le a\le k.
\]
Conversely, every such pair $(k,a)$ corresponds to a pair in the
required range. We will rule out counterexamples for each fixed $k$.

Fix $k\ge3$ and suppose that the upper bound fails for at least one
$a\in\{2,\ldots,k\}$. Choose the least such $a$, and fix a graph $G$
with
\begin{equation}
  |V(G)|=ka+1,\qquad \alpha(G)\le a,
  \qquad G\text{ contains no }C_{k+1}.
  \label{red:counterexample}
\end{equation}
The choice of the least independence parameter will turn deletion of
an independent set and all its neighbors into a useful expansion
bound. The graph $G$ and the parameter $k$ retain this meaning throughout
the upper-bound proof; the parameter $a$ is used through
Section~\ref{sec:small}.

\begin{lemma}\label{red:smaller}
For every integer $b$ with $0\le bp_{i-1}+1\), and therefore, by integrality,
\(p_i\ge p_{i-1}+2\).  Iterating to \(i=s\) gives
\(p_s\ge2s+1>k\), a contradiction.  Hence some nonempty layer
\(D_i\), \(1\le i\le s\), satisfies
\begin{equation}\label{clq:even-layer}
 |D_i|\ge s\alpha(D_i).
\end{equation}

Now suppose that \(k=2s+1\).  If \(|D_j|\le s\alpha(D_j)\) for
every \(1\le j\le s\), including empty layers, the same two
identities give
\[
 (2s+1)p_{i-1}\le s(p_i+p_{i-1}-1),
 \qquad
 p_i\ge p_{i-1}+1+\left\lceil\frac{p_{i-1}}s\right\rceil.
\]
Starting from \(p_0=1\), each increment is at least two, so
\(p_{s-1}\ge2s-1>s\).  The last increment is consequently at least
three, giving \(p_s\ge2s+2>k\), again a contradiction.  Thus some
layer \(D_i\), \(1\le i\le s\), satisfies
\begin{equation}\label{clq:odd-layer}
 |D_i|>s\alpha(D_i).
\end{equation}
This layer is necessarily nonempty.

We have found a layer of sufficiently large order relative to its
independence number.  Choose within it a nonempty induced subgraph
\(H\) of minimum order satisfying the corresponding inequality
\eqref{clq:even-layer} or \eqref{clq:odd-layer}.  Since \(G\) has
no \(K_s\), such an \(H\) cannot be complete: a complete graph
satisfying either inequality would have at least \(s\) vertices.
Thus \(\alpha(H)\ge2\).  For even \(k\) this gives
\(|V(H)|\ge2s=k\); for odd \(k\) it gives
\(|V(H)|>2s\), hence \(|V(H)|\ge2s+1=k\).

The graph \(H\) is connected.  Otherwise each component \(H_j\)
would be a proper nonempty induced subgraph and would fail the
chosen inequality.  Since independence number is additive across
components, summing these failures would give
\[
 \begin{cases}
 |V(H)|s\bigl(\alpha(H)-\alpha(R)\bigr)\ge s|I|.
\]
If \(R=\varnothing\), instead use
\(|N_H[I]|=|V(H)|\ge s\alpha(H)\ge s|I|\); the first
inequality is strict for odd \(k\).

Finally, take \(I=\{v\}\).  When \(H-N_H[v]\) is nonempty, the
strict neighborhood bound gives \(d_H(v)+1>s\), hence
\(d_H(v)\ge s\).  When it is empty, the order bound gives
\(d_H(v)=|V(H)|-1\ge k-1\ge s\).  This proves all the asserted
properties of \(H\).
\end{proof}

We now have a connected, nonbipartite graph \(H\) inside a single
depth layer \(D_i\), with \(1\le i\le s\), satisfying
\eqref{clq:H-properties}.  Under the assumption that \(G\) has no
\(K_s\), the same is true of \(H\).  The next argument uses these
properties to construct a path in \(H\) whose ends can be joined
through the tree above \(D_i\), producing the forbidden cycle.
==== END Cycle-clique-Ramsey-numbers//03-clique-layers.tex ====

==== BEGIN Cycle-clique-Ramsey-numbers//03-clique-rotations.tex ====
\subsection{Paths of a prescribed length}

We now show how the graph supplied by
Proposition~\ref{clq:layer-interface} yields a forbidden cycle.
The main step concerns paths whose ends lie in different parts of a
partition.  We first record the elementary longest-path bound needed
when all vertices of the layer have a common tree parent.

\begin{lemma}\label{clq:long-path}
Let $d\ge 2$, and let $F$ be a finite connected graph with
$\delta(F)\ge d$.  Then $F$ contains a path of order at least
$\min\{|V(F)|,2d+1\}$.
\end{lemma}

\begin{proof}
Let $v_1,\ldots,v_r$ be a longest path in $F$.  All neighbors of either
end belong to the path.  Suppose that
$r<\min\{|V(F)|,2d+1\}$.  The two sets
\[
 \{j\in\{1,\ldots,r-1\}:v_jv_r\in E(F)\},\qquad
 \{j\in\{1,\ldots,r-1\}:v_1v_{j+1}\in E(F)\}
\]
have at least $d$ elements each, whereas their common index set has
$r-1\le 2d-1$ elements.  Choose an index $j$ in their intersection.
If $j=1$ or $j=r-1$, the edge $v_1v_r$ closes the path to a cycle.
For $2\le j\le r-2$, the two indicated edges instead give the cycle
\[
 v_1,\ldots,v_j,v_r,v_{r-1},\ldots,v_{j+1},v_1
\]
through all vertices of the path.  Thus in every case there is a
cycle on these $r$ vertices.
Since $r<|V(F)|$ and $F$ is connected, some vertex outside the cycle
has a neighbor on it.  Starting with that vertex and then traversing
the cycle with one edge omitted gives a longer path, a contradiction.
\end{proof}

The next lemma uses only minimum degree, the exclusion of a clique,
and expansion of independent pairs.  Its proof identifies a clique of
possible path ends, shows that this clique attaches to the remaining
graph through one vertex, and uses that attachment to extend a path.

\begin{lemma}\label{clq:coloured-path}
Let $s\ge 4$, and let $H$ be a finite connected nonbipartite graph
containing no $K_s$.  Suppose that
\[
 \delta(H)\ge s,
 \qquad
 |N_H[\{a,b\}]|\ge 2s
 \quad\text{whenever $a,b$ are distinct and nonadjacent.}
\]
For every nonconstant map $\chi:V(H)\to\{0,1\}$ and every integer
$1\le\ell\le 2s-2$, there is a path in $H$ of length exactly $\ell$
whose ends receive different values of $\chi$.
\end{lemma}

\begin{proof}
Fix $\chi$ and $\ell$, and suppose that no such path exists.
There are vertices $y,z$ with $\chi(y)\ne\chi(z)$ and a common
neighbor $x$.  Indeed, if no such pair existed, the color would be
preserved along every walk of length two.  In a connected nonbipartite
graph there is an even walk between any two vertices: if a connecting
path has odd length, first insert an odd closed walk obtained by going
to an odd cycle, traversing it, and returning.  Preservation of the
color along successive pairs of steps would make $\chi$ constant.
This proves the assertion, and $x,y,z$ are distinct because the graph
is simple.

Let $K$ be the component containing $x$ in $H-\{y,z\}$.
Every vertex of $K$ loses at most two neighbors on deleting $y,z$,
and all its other neighbors lie in the same component.  Thus
\begin{equation}\label{clq:component-degree}
 \delta(K)\ge s-2.
\end{equation}
There is no path of order at least $\ell$ starting at $x$ in $K$.
For the first $\ell$ vertices of such a path form a path with some
last vertex $b$.  At least one of $y,z$ has color different from $b$;
prefixing that vertex gives a path of length $\ell$ with differently
colored ends.

Choose a longest path $P$ starting at $x$ in $K$, and write
$W=V(P)$ and $r=|W|$.  All neighbors in $K$ of its last vertex lie
on $P$, so \eqref{clq:component-degree} gives $r\ge s-1$.
If $\ell\le s-1$, this already contradicts the preceding paragraph.
This disposes in particular of $\ell=1,2$.  Henceforth we have
\begin{equation}\label{clq:path-order}
 s\le\ell\le 2s-2,
 \qquad s-1\le r\le\ell-1.
\end{equation}

\medskip
\noindent\emph{The possible last vertices form a clique.}
Define
\[
 E=\{e\in W:\text{there is a path from $x$ to $e$
 whose vertex set is exactly $W$}\}.
\]
Every such path has the maximum possible order among paths starting
at $x$ in $K$.  Its last vertex has no neighbor in $K-W$.
Since vertices of $K$ have no neighbors in
$H-(K\cup\{y,z\})$, we obtain
\begin{equation}\label{clq:endpoint-neighbors}
 N_K(e)\subseteq W,
 \qquad N_H(e)\subseteq W\cup\{y,z\}
 \quad(e\in E).
\end{equation}
If two vertices of $E$ were nonadjacent, their closed neighborhood
in $H$ would have size at most
$r+2\le\ell+1\le 2s-1$, contrary to the hypothesis.
Thus $E$ is a clique.  Also $x\notin E$, because a simple path with
more than one vertex has distinct ends, and $r\ge s-1\ge3$.

We use the standard fixed-end path rotation of P\'osa
\cite[p.~358]{Posa1963}. The endpoint-clique and attachment conclusions
needed here follow from our stated hypotheses. Explicitly, let
$v_1=x,\ldots,v_r=e$ be any path from $x$ with vertex set $W$.
For an edge $ev_j$ with $1\le j\le r-2$, the sequence
\begin{equation}\label{clq:rotation}
 v_1,\ldots,v_j,v_r,v_{r-1},\ldots,v_{j+1}
\end{equation}
is another path from $x$ on exactly $W$.  Its last vertex is
$v_{j+1}$.  The operation is valid also when $j=1$, so the pivot
may be $x$.  For $j=r-1$, the original path itself has last vertex
$v_{j+1}=e$.  Therefore the successor of every neighbor of $e$
along the path belongs to $E$.  Different neighbors have different
successors, and hence
\begin{equation}\label{clq:endpoint-degree}
 d_K(e)\le |E| \qquad(e\in E).
\end{equation}
Combining \eqref{clq:component-degree} with the fact that $E$ is a
clique and $H$ has no $K_s$ gives
\begin{equation}\label{clq:endpoint-size}
 s-2\le |E|\le s-1.
\end{equation}

On every path from $x$ with vertex set $W$, the vertices of $E$ form
a consecutive final segment.  To see this, let $e$ be its last
vertex.  Every earlier vertex of $E$ is adjacent to $e$, since $E$
is a clique.  The rotation then places its successor in $E$ as well.
Thus membership in $E$ is preserved on moving forward along the path.

\medskip
\noindent\emph{The endpoint clique attaches through one vertex.}
Fix one of the paths from $x$ on $W$.  Let $u$ be the predecessor
of its final segment $E$, and let $w_0$ be the first vertex of that
segment.  Both are defined because $E$ is nonempty and $x\notin E$;
in particular, $u\notin E$ and $uw_0$ is an edge.

For $w\in E-\{w_0\}$, reorder the final clique segment so that it
still starts at $w_0$ and now ends at $w$.  Every neighbor of $w$
in $K$ lies on this path by \eqref{clq:endpoint-neighbors}, and
the successor of each neighbor belongs to $E$ by the rotation.
A vertex of the prefix strictly before $u$ has its successor outside
$E$, so it cannot be a neighbor of $w$.  Consequently
\begin{equation}\label{clq:partial-attachment}
 N_K(w)\subseteq (E-\{w\})\cup\{u\}
 \qquad(w\in E-\{w_0\}).
\end{equation}

We claim that $u$ has at least two neighbors in $E$.  There are two
possibilities in \eqref{clq:endpoint-size}.
If $|E|=s-2$, each $w\in E-\{w_0\}$ has at most
$(s-3)+3=s$ possible neighbors in $H$: the other vertices of $E$,
and $u,y,z$.  Minimum degree $s$ forces all these adjacencies.
Since $|E|\ge2$, there is such a $w$, and $u$ is adjacent to both
$w_0$ and $w$.

If $|E|=s-1$, suppose instead that $w_0$ is the only neighbor of
$u$ in $E$.  By \eqref{clq:partial-attachment}, every vertex in
$E-\{w_0\}$ must then see both $y$ and $z$ to have degree at
least $s$.  The vertex $w_0$ is itself a possible last vertex by
the definition of $E$, whether or not it is last in our fixed order.
Thus \eqref{clq:endpoint-degree} gives $d_K(w_0)\le s-1$,
so $w_0$ sees at least one of $y,z$.  That vertex is adjacent to
all of $E$, giving a $K_s$, a contradiction.
We have proved the claim.

Choose a second neighbor $w_1\in E-\{w_0\}$ of $u$.
Keeping the prefix through $u$ fixed, we can enter $E$ at $w_1$
and reorder this clique so that $w_0$ is last.  The same successor
argument used for \eqref{clq:partial-attachment} now applies to
$w_0$ as well.  It follows that
\begin{equation}\label{clq:attachment}
 N_K(E)\setminus E\subseteq\{u\},
 \qquad |N_K(u)\cap E|\ge2.
\end{equation}

There is a vertex $w\in E$ adjacent to both $y,z$.
For $|E|=s-2$, any vertex of $E-\{w_0\}$ already has this
property.  For $|E|=s-1$, suppose none does.  Each vertex of $E$
then has at most one neighbor among $y,z$ and, by
\eqref{clq:attachment}, no neighbor in $K-E$ other than $u$.
To have degree at least $s$, it must be adjacent to $u$.
Thus $E\cup\{u\}$ would be a $K_s$, again a contradiction.

\medskip
\noindent\emph{A path starting in the endpoint clique is long enough.}
We now seek a path of order at least $\ell$ starting at this vertex
$w$ in $K$.  Since both $y$ and $z$ are adjacent to $w$, the same
prefix argument used at $x$ will give the final contradiction.

First, $K$ is not a clique.  Its minimum degree would force a clique
$K$ to have at least $s-1$ vertices.  It cannot have at least $s$
vertices, and if it has exactly $s-1$, minimum degree $s$ in $H$
forces every vertex of $K$ to see both $y,z$.  Then
$K\cup\{y\}$ is a $K_s$.  Hence $K$ has a nonadjacent pair.
Its closed neighborhood in $H$ is contained in $K\cup\{y,z\}$,
so the independent-pair hypothesis gives
\begin{equation}\label{clq:component-size}
 |V(K)|\ge 2s-2.
\end{equation}

The graph $K-E$ is connected.  Otherwise, since $K$ is connected,
each component of $K-E$ would have a neighbor in $E$;
\eqref{clq:attachment} would force every one of these components
to contain $u$.  Moreover,
\[
 |V(K-E)|\ge (2s-2)-(s-1)=s-1\ge3.
\]
Let $R$ be a longest path starting at $u$ in $K-E$, and let $v$
be its last vertex.  Connectedness and the preceding size bound
ensure that $R$ is nontrivial, so $v\ne u$.
By \eqref{clq:attachment}, the vertex $v$ has no neighbor in $E$;
by maximality of $R$, all its neighbors in $K-E$ lie on $R$.
Thus all its neighbors in $K$ lie on $R$, and
\begin{equation}\label{clq:remaining-path-order}
 |V(R)|\ge d_K(v)+1\ge s-1.
\end{equation}

If $|E|=s-2$ and $|V(R)|=s-1$, the vertices $v,w$ are
nonadjacent by \eqref{clq:attachment}, since $v\ne u$.
Their closed neighborhood in $H$ is contained in
\[
 E\cup V(R)\cup\{y,z\}.
\]
These sets are disjoint and have total size
$(s-2)+(s-1)+2=2s-1$, contrary to the hypothesis.
Together with \eqref{clq:endpoint-size} and
\eqref{clq:remaining-path-order}, this proves
\[
 |E|+|V(R)|\ge2s-2\ge\ell.
\]

By \eqref{clq:attachment}, choose a neighbor $e$ of $u$ in $E$
different from $w$.  Traverse all of the clique $E$ in a path
starting at $w$ and ending at $e$, follow the edge $eu$, and then
follow $R$ from $u$, as shown in Figure~\ref{fig:clique-endpoints}.
The vertex sets $E$ and $V(R)$ are disjoint,
so this is a simple path in $K$ of order
$|E|+|V(R)|\ge\ell$ starting at $w$.
Take its first $\ell$ vertices and prefix whichever of $y,z$ has
color different from its last vertex.  The prefixed vertex lies
outside $K$, so the resulting path is simple and has length exactly
$\ell$.  This contradicts the choice of $\ell$ and completes the
proof.
\end{proof}

\subsection{Closing a path through the breadth-first tree}

The preceding lemma now supplies the path within one distance layer;
the tree supplies a disjoint path of the complementary length.

\begin{proof}[Proof of Theorem~\ref{clq:bound}]
Lemma~\ref{clq:triangle} gives $3\le t\le k$.
If $s=\lfloor k/2\rfloor\le3$, this is the required bound.
Suppose therefore that $s\ge4$ and that $G$ has no $K_s$.
Choose a vertex of $G$ and a breadth-first spanning tree of its
component rooted at that vertex.  Since $\alpha(G)\le a\le k$,
Proposition~\ref{clq:layer-interface} applies and gives $H$ in one
distance layer $D_i$ of this tree, where $1\le i\le s$.

In the breadth-first tree defining this layer, let $c$ be the lowest
common ancestor of all vertices of $H$.
They all have depth $i$, so their distance below $c$ is the same
integer
\[
 p=i-\operatorname{depth}(c).
\]
The graph $H$ has at least $k$ vertices, so $c$ is a proper
ancestor of its vertices, giving $1\le p\le i\le s$.
At least two child branches of $c$ meet $H$, since otherwise the
common child would be a lower common ancestor.

If $p=1$, every vertex of $H$ is adjacent to $c$.
By Lemma~\ref{clq:long-path}, the graph $H$ contains a path of
order at least
\[
 \min\{|V(H)|,2s+1\}\ge k,
\]
because $|V(H)|\ge k$ and $k\in\{2s,2s+1\}$.
Take a subpath of order exactly $k$ and join both ends to $c$.
The vertex $c$ lies above $D_i$, so this gives a simple cycle of
order $k+1$, a contradiction.

Suppose that $p\ge2$.  Partition the child branches of $c$ that
meet $H$ into two nonempty classes, and color each vertex of $H$
according to its class.  This is a nonconstant coloring.
Vertices of different colors have tree distance exactly $2p$,
and all internal vertices of their tree path have depth less than
$i$.
Set
\[
 \ell=k+1-2p.
\]
The inequalities $p\le s$, $p\ge2$, and
$k\in\{2s,2s+1\}$ give $1\le\ell\le2s-2$.
The graph $H$ has all the hypotheses of
Lemma~\ref{clq:coloured-path}: its independent-set neighborhood
bound applies in particular to independent pairs.
That lemma supplies a path in $H$ of length exactly $\ell$
with differently colored ends.
Its vertices have depth $i$, so its interior is disjoint from
the tree path between its ends.  The union of the two paths is
therefore a simple cycle of length
\[
 \ell+2p=k+1.
\]
This final contradiction proves $t\ge s$ and hence the theorem.
\end{proof}
==== END Cycle-clique-Ramsey-numbers//03-clique-rotations.tex ====

==== BEGIN Cycle-clique-Ramsey-numbers//04-small.tex ====
\section{The cases of four- and five-cycles}
\label{sec:small}

We now rule out the minimal counterexample when $k=3$ or $k=4$.
Only the triangle guaranteed by Lemma~\ref{clq:triangle} is needed
from the preceding section. The argument examines the neighbors
outside a clique and uses the absence of the required exact cycle
to separate their neighborhoods.

\begin{proposition}\label{small:cases}
Let $k\in\{3,4\}$ and let $a$ be an integer with $2\le a\le k$.
There is no graph $G$ with
\[
  |V(G)|=ka+1,\qquad \alpha(G)\le a,
  \qquad G\text{ contains no }C_{k+1},
\]
such that $|N_G[I]|\ge k|I|+1$ for every nonempty independent set
$I\subseteq V(G)$.
\end{proposition}

\begin{proof}
Suppose such a graph exists. Applying the neighborhood bound to a
singleton gives $\delta(G)\ge k$. Lemma~\ref{clq:triangle} supplies
a triangle, and a clique of order $k+1$ would contain the forbidden
cycle, so $3\le\omega(G)\le k$.

For a clique $Q=\{q_1,\ldots,q_t\}$, let $F=G-Q$ and put
\[
  U_i=N_G(q_i)\cap V(F)\qquad(1\le i\le t).
\]
We will use this notation with different choices of $Q$, specifying
the choice each time. A path between two distinct vertices of $Q$
whose internal vertices lie in $F$ can be completed using edges of
$Q$. The exact numbers of internal vertices that are forbidden are
checked below.

\medskip
\noindent\textbf{The case $k=3$.}
Choose a triangle $Q=\{q_1,q_2,q_3\}$. Each $U_i$ is nonempty,
since $q_i$ has two neighbors inside $Q$ and degree at least three.
For distinct $i,j$, write $h$ for the remaining index. A common
vertex $u\in U_i\cap U_j$ would give the cycle
\[
  q_i,u,q_j,q_h,q_i
\]
of order four. If $u\in U_i$ and $v\in U_j$ were adjacent, then
\[
  q_i,u,v,q_j,q_i
\]
would be a cycle of order four. Thus the sets $U_1,U_2,U_3$ are
pairwise disjoint and pairwise anticomplete.

Choosing one vertex from each $U_i$ gives an independent set of
order three. Hence $a=3$. If any $U_i$ contained two nonadjacent
vertices, adjoining one vertex from each of the other two sets would
give an independent set of order four. Therefore each $U_i$ is a
clique. Moreover, $\{q_i\}\cup U_i$ is a clique and there is no
$K_4$, so
\[
  1\le |U_i|\le2.
\]
Since $|V(F)|=7$, the set
\[
  W=V(F)\setminus(U_1\cup U_2\cup U_3)
\]
is nonempty. Every vertex of $W$ has no neighbor in $Q$ by the
definition of the $U_i$.

Fix $w\in W$. If $w$ saw two distinct vertices $u,v\in U_i$, then
$w,u,q_i,v,w$ would be a $C_4$. Thus $w$ has at most one neighbor
in each $U_i$. On the other hand, if $w$ missed a vertex $u\in U_i$
and a vertex $v\in U_j$ for distinct $i,j$, then
$\{w,u,v,q_h\}$ would be an independent set of order four. Indeed,
$w$ misses $Q$, the two exterior sets are anticomplete, and $q_h$
has no neighbor in either of them. It follows that $w$ is adjacent
to every vertex of at least two of the $U_i$. These two sets must
therefore be singletons.

There are consequently at least two singleton sets among the three
$U_i$. If exactly two are singletons, the three sizes are $1,1,2$,
so $|W|=3$. Every vertex of $W$ sees the two singleton vertices,
say $u,v$. Distinct $w,w'\in W$ then give the cycle
$w,u,w',v,w$ of order four. If all three $U_i$ are singletons,
then $|W|=4$. Each $w\in W$ sees at least two of the three singleton
vertices. Choose one pair of such neighbors for each $w$. There are
only three pairs, so two vertices $w,w'$ choose the same pair
$\{u,v\}$, again giving $w,u,w',v,w$. This rules out $k=3$.

\medskip
\noindent\textbf{The case $k=4$ with a clique of order four.}
Suppose first that $Q=\{q_1,q_2,q_3,q_4\}$ is a clique. A path
between distinct $q_i,q_j$ with one, two, or three internal vertices
outside $Q$ can be completed to a $C_5$ by a path in $Q$ of length
three, two, or one, respectively. More explicitly, with $q_h,q_\ell$
the other clique vertices, the prohibited configurations yield
\[
\begin{gathered}
  q_i,u,q_j,q_h,q_\ell,q_i,\\
  q_i,u,v,q_j,q_h,q_i,\\
  q_i,u,z,v,q_j,q_i.
\end{gathered}
\]
In every row the exterior vertices are distinct and lie outside
$Q$, so the displayed cycle has exactly five vertices.

The sets $U_i$ are nonempty. Their closed neighborhoods in $F$ are
pairwise disjoint: an intersection of $N_F[U_i]$ and $N_F[U_j]$
would give vertices $u\in U_i$, $v\in U_j$ at distance at most two
in $F$, with $u=v$ allowed. A shortest such path, joined to $q_i$
and $q_j$, is one of the three prohibited configurations. In
particular, every vertex $u\in U_i$ has exactly one neighbor in
$Q$, so it has at least three neighbors in $F$. It follows that
\[
  |V(F)|\ge\sum_{i=1}^4|N_F[U_i]|\ge4\cdot4=16.
\]
But $|V(F)|=4a-3\le13$, a contradiction. We may therefore assume
that $\omega(G)=3$.

\medskip
\noindent\textbf{Triangles with disjoint exterior neighbor sets.}
For any triangle $Q=\{q_1,q_2,q_3\}$, every $U_i$ has size at
least two. A path between distinct triangle vertices with two or
three internal vertices outside $Q$ gives a $C_5$. In particular,
if distinct $u\in U_i$, $v\in U_j$ are adjacent, or are joined by
a two-edge path $u,z,v$ in $F$, the respective cycles are
\begin{equation}
  q_i,u,v,q_j,q_h,q_i
  \qquad\text{and}\qquad
  q_i,u,z,v,q_j,q_i,
  \label{small:five-cycles}
\end{equation}
where $h$ is the remaining triangle index.

Suppose for the moment that $U_1,U_2,U_3$ are disjoint. By
\eqref{small:five-cycles}, their closed neighborhoods in $F$ are
also pairwise disjoint. A maximum independent subset $J$ of $U_i$
has exactly one neighbor in $Q$, namely $q_i$. Thus the assumed
expansion bound gives
\begin{equation}
  |N_F[U_i]|\ge |N_F[J]|
  =|N_G[J]|-1\ge4\alpha(U_i).
  \label{small:one-neighbor-count}
\end{equation}
Here $|V(F)|=4a-2\le14$. If any $U_i$ had independence number at
least two, the three disjoint neighborhoods would together have
at least $8+4+4=16$ vertices. Hence every $U_i$ is a clique. Its
size is exactly two, because it has size at least two and adjoining
$q_i$ cannot produce a $K_4$.

If the exterior neighbor sets were disjoint for every triangle,
write $U_i=\{u_i,v_i\}$ and apply that assertion to the triangle
$T_i=\{q_i,u_i,v_i\}$. Each of $u_i,v_i$ has at least two neighbors
outside $T_i$, and the two sets of such neighbors are disjoint.
All of these vertices lie in $F-U_i$: the original disjointness
prevents $u_i$ or $v_i$ from seeing a vertex of $Q\setminus\{q_i\}$.
Consequently $|N_F[U_i]|\ge2+2+2=6$ for every $i$. The three
original closed neighborhoods are disjoint, so this would require
at least $18$ vertices in $F$, again impossible. Some triangle
therefore has overlapping exterior neighbor sets.

\medskip
\noindent\textbf{The necessary structure at an overlapping triangle.}
Take a triangle for which
$I=U_1\cap U_2\ne\varnothing$. No other pair of exterior sets
overlaps. Indeed, a vertex in all three sets would form a $K_4$
with $Q$. If $x\in U_1\cap U_2$ and
$y\in U_1\cap U_3$ are distinct, then
\[
  q_2,x,q_1,y,q_3,q_2
\]
is a $C_5$; if instead $y\in U_2\cap U_3$, use
$q_1,x,q_2,y,q_3,q_1$. Also $I$ is independent, since adjacent
vertices $x,y\in I$ would give the $K_4$ on $q_1,q_2,x,y$.

The four sets
\[
  I,\qquad A=U_1\setminus I,\qquad
  B=U_2\setminus I,\qquad D=U_3
\]
have pairwise disjoint closed neighborhoods in $F$. To check this
even for pairs involving $I$, choose distinct triangle neighbors
for vertices in the six possible pairs of classes as follows:
\[
\begin{array}{c|cccccc}
\text{classes}&(I,A)&(I,B)&(I,D)&(A,B)&(A,D)&(B,D)\\ \hline
\text{neighbors}&(q_2,q_1)&(q_1,q_2)&(q_1,q_3)&
                  (q_1,q_2)&(q_1,q_3)&(q_2,q_3).
\end{array}
\]
If two vertices from the indicated classes were adjacent or shared
a neighbor in $F$, the corresponding distinct triangle neighbors
would close one of the cycles in \eqref{small:five-cycles}. Since
the classes themselves are disjoint, their closed neighborhoods
are disjoint as claimed.

Write $r=|I|$. The set $I$ is independent and its only neighbors in
$Q$ are $q_1,q_2$. Hence
\begin{equation}
  |N_F[I]|=|N_G[I]|-2\ge4r-1.
  \label{small:overlap-count}
\end{equation}
Each nonempty one of $A,B,D$ has exactly one triangle neighbor,
so the argument of \eqref{small:one-neighbor-count} bounds the
size of its closed neighborhood below by four times its
independence number. These bounds may be added because the four
closed neighborhoods are disjoint.

If $r=1$, then both $A$ and $B$ are nonempty, since
$|U_1|,|U_2|\ge2$, and $D$ is nonempty as well. The four
neighborhoods would have total size at least
$3+4+4+4=15>14$. If $r\ge3$, the neighborhoods of $I$ and $D$
alone would have total size at least $11+4=15>14$. Thus $r=2$.
In this case the neighborhoods of $I$ and $D$ already contribute
at least $7+4=11$ vertices; a nonempty $A$ or $B$ would increase
the bound to $15$. Therefore
\begin{equation}
  |I|=2,\qquad U_1=U_2=I.
  \label{small:overlap-structure}
\end{equation}
Moreover, $\alpha(D)\ge2$ would give $7+8=15$ vertices, so $D$
is a clique. Its size is exactly two, by the degree bound and the
absence of a $K_4$.

This argument proves a necessary statement for \emph{every}
triangle with overlapping exterior neighbor sets: exactly one
pair overlaps, both sets in that pair equal an independent set
of size two, and the third exterior neighbor set is a clique of
size two. No condition on the exterior sets of other triangles
was used in proving this statement.

\medskip
\noindent\textbf{The final contradiction.}
Write $I=\{w,z\}$ and consider the triangle
$T=\{q_1,q_2,w\}$. By \eqref{small:overlap-structure}, the
exterior neighbor sets of its first two vertices are both
\[
  N_G(q_1)\setminus T=N_G(q_2)\setminus T=\{q_3,z\}.
\]
The necessary statement just proved therefore applies to $T$.
Its third vertex $w$ has exactly two neighbors outside $T$.
Neither $q_3$ nor $z$ is adjacent to $w$: adjacency to $q_3$
would give a $K_4$ with the original triangle, and $I$ is
independent. Thus the neighbors of $w$ outside $T$ are precisely
its neighbors in the original graph $F$, and $d_F(w)=2$.
The same reasoning applies to $z$. Consequently,
\[
  |N_F[I]|\le |I|+d_F(w)+d_F(z)=2+2+2=6,
\]
whereas \eqref{small:overlap-count} gives $|N_F[I]|\ge7$.
This contradiction completes the case $k=4$ and the proof.
\end{proof}

By Lemma~\ref{red:expansion}, the minimal counterexample satisfies
all the assumptions of Proposition~\ref{small:cases}. Hence we
may assume $k\ge5$ from now on.
==== END Cycle-clique-Ramsey-numbers//04-small.tex ====

==== BEGIN Cycle-clique-Ramsey-numbers//05-size.tex ====
\section{From size to independence}\label{sec:size}

We next show that a vertex set larger than both $k$ and twice the clique
number contains three independent vertices.  The argument uses only the
forbidden cycle and the clique bound.  We first prove two elementary facts
about graphs with independence number at most two.
The first is a special case of the Chv\'atal--Erd\H{o}s Hamiltonicity
theorem~\cite[Theorem~1]{ChvatalErdos1972}. The shortening argument in the
second appears in Radziszowski and Jin's proof of their pancyclicity
theorem~\cite[Theorem~2]{RadziszowskiJin1994}. We include both proofs.

\begin{lemma}\label{size:hamiltonian}
Every finite simple 2-connected graph $H$ with $\alpha(H)\le2$ contains a
cycle through all its vertices.
\end{lemma}

\begin{proof}
A 2-connected graph has minimum degree at least two and therefore contains
a cycle: all neighbors of an endpoint of a longest path lie on that path,
and two such neighbors give a cycle.  Choose a cycle $C$ of maximum order,
orient it, and write $a^+$ for the successor of $a\in V(C)$.

Suppose that a component $D$ of $H-V(C)$ exists.  Its set of neighbors on
$C$ contains at least two vertices.  Indeed, it is nonempty by
connectedness, and a unique such vertex would be a cutvertex of $H$.
If $a\in V(C)$ has a neighbor in $D$, then $a^+$ has none.  Otherwise a
path from $a$ to $a^+$ with nonempty interior in the connected graph $D$
could replace the edge $aa^+$, giving a longer cycle.  This path exists
even if $a$ and $a^+$ have the same neighbor in $D$.

Choose distinct vertices $a,b\in V(C)$ with neighbors in $D$, and a path
$P$ from $a$ to $b$ with nonempty interior in $D$.  The vertices $a^+,b^+$
are distinct, neither equals $a$ or $b$, and both have no neighbor in $D$.
If $a^+b^+$ were an edge, we could traverse $P$ from $a$ to $b$, follow
$C$ backwards from $b$ to $a^+$, use $a^+b^+$, and follow $C$ forwards
from $b^+$ to $a$.  Deleting $aa^+$ and $bb^+$ from $C$ leaves exactly
the two cycle segments used here.  Hence this would be a cycle containing
every vertex of $C$ and at least one additional vertex, a contradiction.
Thus $a^+$ and $b^+$ are nonadjacent.  Together with any vertex of $D$,
they form an independent triple, also a contradiction.  Therefore $C$
is spanning.
\end{proof}

\begin{lemma}\label{size:shortening}
Let $H$ be a finite simple graph on $r\ge7$ vertices with
$\alpha(H)\le2$.  If $H$ has a Hamiltonian cycle, then it has a cycle
on exactly $r-1$ vertices.
\end{lemma}

\begin{proof}
Label the vertices around a Hamiltonian cycle by $0,1,\ldots,r-1$, with
indices interpreted modulo $r$.  If some edge joins $i$ to $i+2$, it
bypasses the vertex $i+1$ and gives the required cycle.  Suppose there
is no such edge.  In each triple $i,i+2,i+4$, the pairs $i(i+2)$ and
$(i+2)(i+4)$ are nonedges.  Since the triple is not independent,
$i(i+4)$ is an edge.  All cyclic step-four edges are therefore present.

Consider the cyclic sequence
\begin{equation}\label{size:shortening-cycle}
 1,2,\ldots,r-6,\quad r-2,r-1,\quad r-5,r-4,r-3,\quad1.
\end{equation}
Before closing, its three blocks partition the vertices $1,\ldots,r-1$.
Consecutive vertices within a block are adjacent on the original cycle.
The three edges joining the blocks and closing the sequence are
\[
 (r-6)(r-2),\qquad (r-1)(r-5),\qquad (r-3)1;
\]
their cyclic differences are $4,-4,4$, respectively.  Thus
\eqref{size:shortening-cycle} is a cycle of order $r-1$.
When $r=7$, the first block is the singleton $1$, and the sequence is
explicitly $1,5,6,2,3,4,1$, so the same construction applies.
\end{proof}

\begin{lemma}[Size test]\label{size:test}
Let $k\ge5$ and $t\ge1$ be integers.  Let $G$ be a finite simple graph
with no cycle on exactly $k+1$ vertices and with clique number at most
$t$.  For every $Y\subseteq V(G)$,
\[
 |Y|>\max\{k,2t\}\quad\Longrightarrow\quad\alpha(G[Y])\ge3.
\]
\end{lemma}

\begin{proof}
Suppose that $H=G[Y]$ has $\alpha(H)\le2$ and order
$n>\max\{k,2t\}$.  If $H$ is disconnected, it has exactly two
components, each a clique.  Indeed, three components give an independent
triple, as does a nonadjacent pair in one component together with a vertex
of another.  The two cliques have at most $t$ vertices each, contrary to
$n>2t$.

If $H$ has a cutvertex $v$, the same argument shows that $H-v$ has
exactly two components $A,B$, both cliques of order at most $t$.
The inequalities
\[
 |A|+|B|+1=n>2t,\qquad |A|,|B|\le t
\]
force $|A|=|B|=t$.  The vertex $v$ must be adjacent to all of one
component: a nonneighbor in each would form an independent triple with
$v$.  That component together with $v$ is a clique of order $t+1$,
again a contradiction.

Consequently $H$ is 2-connected and has a Hamiltonian cycle by
Lemma~\ref{size:hamiltonian}.  Its order is $n\ge k+1$.  If a current
cycle has order $r>k+1$, the graph induced by its vertices is Hamiltonian,
has independence number at most two, and satisfies $r\ge k+2\ge7$.
Lemma~\ref{size:shortening} therefore produces a cycle of order $r-1$.
Repeated shortening reaches exactly $k+1$, contradicting the hypothesis
on $G$.
\end{proof}
==== END Cycle-clique-Ramsey-numbers//05-size.tex ====

==== BEGIN Cycle-clique-Ramsey-numbers//06-paths.tex ====
\section{Optimal path systems}\label{sec:paths}

We now assume $k\geq5$ and work in the graph $G$ from the
minimal-counterexample reduction. Thus $G$ has no cycle of order $k+1$,
$\delta(G)\geq k$, $\alpha(G)\leq k$, and the independent-set expansion
of Lemma~\ref{red:expansion} holds. Fix a maximum clique $Q$, and write
\[
 t=|Q|,\qquad h=k+1-t.
\]
By Theorem~\ref{clq:bound},
$\max(3,\lfloor k/2\rfloor)\leq t\leq k$, so $h\geq1$.
Our first objective is to encode paths through vertices outside $Q$ in a
way that allows us to close them into a cycle of exactly the forbidden
order. We then choose an optimal encoding and relate short paths outside
its vertex set to separated sets of vertices.

\subsection{Paths joining clique vertices}

A \emph{path system on $Q$} is a collection $\mathcal R$ of simple paths
with the following properties. Each path has two distinct endpoints in
$Q$ and a nonempty interior contained in $V(G)\setminus Q$. The interiors
of different paths are disjoint. Represent each path by the edge joining
its endpoints in an auxiliary graph with vertex set $Q$. These represented
edges must be distinct and must form a linear forest: every component is
a path, including isolated vertices. We call these components
\emph{chains}. In particular, every unused clique vertex is a singleton
chain; it does not represent a path with empty interior.

The \emph{amount} of an assigned path is its number of internal vertices.
For a system $\mathcal R$, let $q(\mathcal R)$ be the sum of its amounts,
let $e(\mathcal R)$ be its number of assigned paths, and let
$v(\mathcal R)$ be the number of clique vertices incident with its
represented edges. Thus singleton chains contribute neither to the amount
nor to the incident-vertex count. The empty collection is allowed.

\begin{lemma}[Closing a path system]\label{path:interval}
Let $G$ be a finite simple graph with no cycle of order $k+1$, and let
$Q$ be a clique of size $t$, where $3\leq t\leq k$.
Put $h=k+1-t$. No path system on $Q$, of total amount $q$ and with $v$
incident clique vertices, satisfies
\begin{equation}\label{path:forbidden-interval}
 h\leq q\leq k+1-v.
\end{equation}
\end{lemma}

\begin{proof}
Suppose such a system exists. The integer
\[
 u=k+1-q-v
\]
satisfies $0\leq u\leq t-v$: the first inequality follows from the upper
bound on $q$, and the second from $q\geq h$. Choose exactly $u$ of the
clique vertices not incident with represented edges.

Expand each nontrivial chain by replacing its represented edges with
their assigned paths. Each expansion is a simple path, and different
expansions are vertex-disjoint. Indeed, their clique vertices belong to
different forest components, and all assigned interiors are disjoint and
lie outside $Q$. Adjoin the $u$ chosen unused clique vertices as singleton
paths. These paths together contain exactly
\[
 q+v+u=k+1
\]
vertices, and all their endpoints belong to $Q$.

There is at least one nontrivial expanded chain, since $q\geq h\geq1$.
If there is only one path in the resulting list, it has at least three
vertices: it contains an assigned path with nonempty interior. The clique
edge between its distinct endpoints closes it into a simple cycle. If
there are two or more paths, order and orient them arbitrarily, join each
path's last endpoint to the next path's first endpoint by a clique edge,
and close the last to the first. This again gives a simple cycle. In the
case of two paths with one singleton, the two joining edges use the two
distinct endpoints of the nontrivial path; thus they are distinct. The
case of two singleton paths cannot occur. All remaining cases follow
directly from vertex-disjointness. The resulting cycle has order $k+1$,
a contradiction.
\end{proof}

Choose a path system $\mathcal P$ of maximum total amount $L$ subject to
$Lk$, this contradicts $\alpha(G)\le k$; this also settles the
case $t=k$ without using the independent-triple conclusion.

We may therefore assume $2t\le k$.  The bound
$\lfloor k/2\rfloor\le t$ from Theorem~\ref{clq:bound} now gives
\begin{equation}\label{grow:parity}
 k\in\{2t,2t+1\}.
\end{equation}
In particular $tk$.

If $|S|t$ at every representative, so any two suffice.
It remains to consider $|S|=k$.  In this case
$L=k-t>0$, and hence $e\ge 1$.

Suppose first that $e\ge 2$.  At least two representatives are
interior vertices of paths of $\mathcal P$.  For each such
representative $x$, let $y$ be the next vertex toward its target.
This vertex is not in $R$: it is either a later interior vertex of
the same path, or, when the amount is one, the target itself, which
is not a chain start.  By the consecutive-vertex assertion of
Lemma~\ref{grow:one}, every outside neighbor of $x$ misses $y$.
The improved degree count following \eqref{grow:degree} yields
\[
 |B_1(x;S)|\ge k-|S|+t+1=t+1.
\]
Thus the two chosen first balls are not cliques.

Finally suppose that $e=1$.  The represented forest has one
nonsingleton chain, consisting of a single edge, and $t-2\ge 7$
singleton chains.  Let $x$ be the representative of any singleton
chain.  Reverse the nonsingleton chain, leaving every other
orientation fixed, and let $y$ be its new starting clique vertex.
The vertex $y$ was not in the original representative set $R$,
whereas $x$ is a representative in both orientations.
Lemma~\ref{grow:one}, applied to the reversed orientation, shows that
every outside neighbor of $x$ misses $y$.  Consequently
$|B_1(x;S)|\ge t+1$ once again.  Choosing two singleton
representatives gives the two required noncliques and the final
contradiction.  The reversed orientation was used only for the
unconditional one-vertex exclusion; the assumed absence of paths
with up to six internal vertices concerned the original orientation
alone.
\end{proof}
==== END Cycle-clique-Ramsey-numbers//07-growth.tex ====

==== BEGIN Cycle-clique-Ramsey-numbers//08-terminal.tex ====
\section{Excluding large cliques}\label{sec:terminal}

We retain the notation of Section~\ref{sec:paths} and assume \(t\ge9\).
Our goal is to obtain more than \(k\) independent vertices by combining
independent sets in separated balls.  Lemma~\ref{grow:short} supplies a short
outside path between representatives.  We first show that such a path forces
the optimal system \(\mathcal P\) into one of three configurations.
By Theorem~\ref{clq:bound},
\[
 t\le k\le2t+1,\qquad h=k+1-t,\qquad L\le k-t\le t+1.
\]

\subsection{A restriction on small increases in amount}

The next lemma applies to any valid replacement system, not only to the
construction between representatives.

\begin{lemma}\label{terminal:increment}
Let \(t\ge9\), and let \(\mathcal R\) be a valid path system consisting of some
paths of \(\mathcal P\) and one new path.  Suppose that its total amount is
\(L+d\), where \(1\le d\le6\).  Then
\[
 L=h-1=k-t.
\]
Moreover, \(\mathcal R\) contains all \(e\) paths of \(\mathcal P\), its new
path has amount \(d\), and every old path has amount at least \(d\).
In particular, a construction of this kind that removes an old path is
impossible.
\end{lemma}

\begin{proof}
If \(L+dk+1-w,\qquad\text{or equivalently}\qquad w>t-j.
\]
Since \(w\le t\), this also excludes \(j=0\).  Thus
\begin{equation}\label{terminal:minimal}
 1\le j\le5,\qquad 2r\ge w\ge t-j+1.
\end{equation}

Deleting any selected path lowers the amount below \(h\); consequently
every selected amount is at least \(j+1\).
Suppose that all were at least \(j+2\).
Exactly \(r-1\) of the selected paths are old, so
\[
 (r-1)(j+2)\le L\le k-t.
\]
Together with \eqref{terminal:minimal}, this implies
\[
 (t-j-1)(j+2)\le2(k-t)\le2t+2.
\]
The left side is a concave function of \(j\) on \([1,5]\).
Its endpoint values are \(3(t-2)\) and \(7(t-6)\), whose differences from
\(2t+2\) are respectively \(t-8\) and \(5t-44\).
Both are positive for \(t\ge9\), a contradiction.

Some selected path therefore has amount exactly \(j+1\).
Deleting it, whether it is old or new, leaves a valid system of amount
\(h-1\).  Maximality gives \(L=h-1\).
The minimum-path tie-break in the choice of \(\mathcal P\) now gives
\(r-1\ge e\).
On the other hand, \(\mathcal R\) has at most \(e+1\) paths, so \(r\le e+1\).
Hence \(r=e+1\): the selected subcollection is all of \(\mathcal R\), and
all old paths occur in it.
Comparing its two expressions for the total amount gives
\[
 h+j=L+d=h-1+d,\qquad j=d-1.
\]
Thus every selected amount is at least \(j+1=d\), and, since all old paths
remain, the new path has amount exactly \(d\).
\end{proof}

\subsection{The three possible configurations}

Call a vertex of \(Q\) \emph{missing} if it is not incident to any path of
\(\mathcal P\).  Thus the missing vertices are precisely the singleton
chains of its represented forest.  Let \(v\) denote the number of incident
vertices, so there are \(t-v\) missing vertices.

\begin{lemma}\label{terminal:classification}
Suppose that, for some orientation of the chains, an outside path with
parameter \(d\in\{1,\ldots,6\}\) joins two representatives.
Then \(L=k-t\), and exactly one of the following alternatives holds:
\begin{enumerate}
 \item\label{terminal:two}
 \(d=2\), \(v\ge t-2\), and every old amount is at least two;
 \item\label{terminal:three}
 \(d=3\), \(t\in\{9,11\}\), \(e=(t-3)/2\), and \(v=t-3\);
 the old paths represent a matching and have amounts at least three;
 \item\label{terminal:five}
 \(d=5\), \(t=9\), \(k=19\), \(e=2\), and \(v=4\);
 the old paths represent a matching and both have amount five.
\end{enumerate}
In every alternative, the two targets must be starting vertices in their
oriented chains.  In Alternative~\ref{terminal:two} their union must contain
all missing vertices.  In Alternatives~\ref{terminal:three}
and~\ref{terminal:five} both targets must be missing.

Once one of these alternatives holds, its parameter and endpoint
restrictions apply to every outside path with parameter between one and six
between representatives, in every orientation.
\end{lemma}

\begin{proof}
Lemma~\ref{grow:replacement} constructs a valid system of amount \(L+d\),
consisting of unchanged old paths and one new path.
Lemma~\ref{terminal:increment} shows that no old path was removed.
The two targets must therefore be starting vertices, and every old amount
is at least \(d\).
The proof of Lemma~\ref{terminal:increment} also gives \(j=d-1\ge1\), so
\(d\ge2\).

Let \(a\in\{0,1,2\}\) be the number of missing targets among these two
vertices.  The new system has exactly \(v+a\) incident vertices.
Its amount is \(h+d-1\); hence Lemma~\ref{path:interval} gives
\begin{equation}\label{terminal:incident}
 v+a\ge t-d+2.
\end{equation}
In particular, \(v\ge t-d\).  Since \(v\le2e\) and every old amount is at
least \(d\), we obtain
\begin{equation}\label{terminal:arithmetic}
 2\le d\le6,\qquad
 d\left\lceil\frac{t-d}{2}\right\rceil
 \le de\le L=k-t\le t+1.
\end{equation}

For \(d=2\), this gives \(v\ge t-2\).
Equation~\eqref{terminal:incident} says that \(v+a\ge t\), so the two targets
must cover all \(t-v\) missing vertices.

For \(d=3\), dropping the ceiling in \eqref{terminal:arithmetic} gives
\(3(t-3)\le2(t+1)\), and hence \(t\le11\).
At \(t=10\), the exact bound fails because
\(3\lceil7/2\rceil=12>11\).
At \(t=9\) it forces \(e=3\), and at \(t=11\) it forces \(e=4\).
In each case
\[
 t-3\le v\le2e=t-3.
\]
Thus \(v=2e=t-3\), so no two old edges share a clique vertex.
Equation~\eqref{terminal:incident} then forces \(a=2\).

For \(d=4\), the weaker bound \(4(t-4)\le2(t+1)\) gives \(t\le9\);
but at \(t=9\) the exact bound fails:
\(4\lceil5/2\rceil=12>10\).
For \(d=5\), the weaker bound gives \(3t\le27\), hence \(t=9\).
Now \(2\le e\le2\) and \(4\le v\le2e=4\).
Moreover,
\[
 10=5e\le L\le t+1=10,
\]
so \(L=10\), \(k=19\), and both amounts are five.
Again \eqref{terminal:incident} forces \(a=2\).
Finally, for \(d=6\), the weaker bound gives \(4t\le38\), hence \(t=9\);
there \(6\lceil3/2\rceil=12>10\), which is impossible.

The three surviving alternatives are mutually exclusive properties of
the fixed old system: they require respectively
\[
 v\ge t-2,\qquad v=t-3,\qquad t=9,\ v=t-5.
\]
The argument applies to every orientation and every pair admitting a
path with parameter between one and six.  Thus, once the old system lies in
one alternative, any such path in any orientation must obey the corresponding
parameter and endpoint restrictions.
\end{proof}

\subsection{Independent sets in balls}

We next obtain bounds that apply to each representative individually.
When choosing several balls later, we will check their pairwise separation
separately.

\begin{lemma}\label{terminal:weights}
Under any alternative of Lemma~\ref{terminal:classification}, there are at
least two nonsingleton chains.
For every vertex \(x\) that is a representative in some orientation,
\[
 |B_1(x;S)|\ge t+1,\qquad \alpha(B_1(x;S))\ge2.
\]
If \(k\ge2t\), then also \(\alpha(B_2(x;S))\ge3\).
\end{lemma}

\begin{proof}
The matching in Alternative~\ref{terminal:three} has three or four edges,
and that in Alternative~\ref{terminal:five} has two.
In Alternative~\ref{terminal:two}, if there were only one nonsingleton
chain, then
\[
 v=e+1\le\left\lfloor\frac{t+1}{2}\right\rfloor+10\).

Fix an orientation in which \(x\) is a representative.
Choose a nonsingleton chain other than the chain containing its target,
and reverse only that chain.  Its old terminal clique vertex becomes a
representative, although it was not one of the original representatives;
meanwhile \(x\) remains a representative.
By Lemma~\ref{grow:one}, every vertex of \(B_0(x;S)\) is nonadjacent to the
other \(t-1\) original representatives and to this additional clique vertex.

Lemma~\ref{terminal:classification} gives \(|S|=t+L=k\).
The set \(B_0(x;S)\) is nonempty, because \(\delta(G)\ge k\) and
\(|S|\le k\).  For \(z\in B_0(x;S)\), its closed neighborhood has size at
least \(k+1\), meets \(S\) in at most \(|S|-t\) vertices, and is contained
in \(S\cup B_1(x;S)\).  Therefore
\[
 |B_1(x;S)|\ge k+1-(|S|-t)=t+1.
\]
Since \(t\) is the maximum clique size, this ball contains an independent
pair \(I\).  The expansion inequality \eqref{red:expansion-bound} and the
containment \(N_G[I]\subseteq S\cup B_2(x;S)\) give
\[
 |B_2(x;S)|\ge2k+1-|S|=k+1.
\]
If \(k\ge2t\), this exceeds \(\max(k,2t)\), so
Lemma~\ref{size:test} supplies an independent triple.
\end{proof}

\subsection{The final packings}

\begin{proposition}\label{terminal:contradiction}
There is no counterexample \(G\) with maximum clique size \(t\ge9\).
\end{proposition}

\begin{proof}
By Lemma~\ref{grow:short}, some pair of representatives admits an outside
path with parameter between one and six.  We may therefore apply
Lemma~\ref{terminal:classification}.  In each of its alternatives we will
choose balls with distinct bases that are pairwise disjoint and
anticomplete.  Independent sets in these balls then combine into an
independent set in \(G\).

\paragraph{Alternative~\ref{terminal:two}: at least one missing vertex.}
Put \(c=t-v\), so \(0\le c\le2\), and first suppose \(c\ge1\).
Fix an orientation and choose the \(v=t-c\) representatives whose targets
are incident to old paths.  No pair of these targets covers the missing
vertices.  The endpoint restriction in
Lemma~\ref{terminal:classification} therefore forbids every outside
parameter \(1,\ldots,6\) between any two chosen representatives.
Their radius-two balls are pairwise disjoint and anticomplete by
Lemma~\ref{path:separation}.

We claim that each of these balls contains an independent triple, even
when \(k<2t\).  First,
\[
 k=t+L\ge t+2e\ge t+v\ge2t-2.
\]
For a chosen base \(x\), Lemma~\ref{terminal:weights} gives an independent
pair \(I\subseteq B_1(x;S)\).
There are at least two other chosen representatives, since
\(v\ge t-2\ge7\).  For either such representative \(y\), the prohibition of
parameters one and two means that \(y\) has no neighbor in \(B_1(x;S)\),
by Lemma~\ref{path:separation}.  Thus at least two vertices of \(S\) are
absent from \(N_G[I]\).  Since \(|S|=k\), expansion gives
\[
 |B_2(x;S)|\ge2k+1-(|S|-2)=k+3\ge2t+1.
\]
This exceeds both \(k\) and \(2t\), so Lemma~\ref{size:test} proves the
claim.  The separated balls now give an independent set of size at least
\[
 3(t-c)\ge3t-6>2t+1\ge k,
\]
a contradiction.

\paragraph{Alternative~\ref{terminal:two}: no missing vertex.}
Now \(c=0\).  The bounds
\[
 t=v\le2e\le L\le t+1
\]
give \(e=\lceil t/2\rceil\) and \(k=t+L\ge2t\).
Lemma~\ref{terminal:weights} therefore gives an independent triple in the
radius-two ball of any representative.
We select at least \(t-1\) interior vertices as follows.

If \(t\) is even, then \(e=t/2\) and \(v=2e\), so the represented forest is
a matching.  Every amount is at least two, and \(L\le2e+1\), so at most one
amount exceeds two; if it does, it is three.
Choose both interior vertices on each amount-two path, and one first
interior vertex on the possible amount-three path.
This chooses \(t\) or \(t-1\) vertices.

If \(t\) is odd, then \(2e=t+1\), so \(L=t+1\) and every amount is two.
The forest has \(v-e=e-1\) nonsingleton chains and \(e\) edges.
Exactly one chain therefore has two edges, and all the others have one.
Choose the two interior representatives of the two-edge chain in one
fixed orientation.  On each single-edge chain choose both interior
vertices.  This chooses
\[
 2+2(e-2)=t-1
\]
vertices.

Every chosen vertex is an interior representative in some orientation.
Two chosen vertices on different chains can be representatives
simultaneously, because the chains can be oriented independently.
The two chosen vertices in the two-edge chain are simultaneous
representatives by their definition.  For any of these pairs, an outside
path with parameter \(1\le d\le6\) would give, by
Lemma~\ref{grow:replacement}, a new system of amount \(L+d\) that removes
an old path.  Lemma~\ref{terminal:increment} rules this out.

The only pairs not yet covered are the two interior vertices \(a,b\) of a
single amount-two path \(u,a,b,v\).
If an outside \(a\)-to-\(b\) path with parameter \(1\le d\le6\) existed,
replace the step \(ab\) by it.  The resulting \(u\)-to-\(v\) path has
amount \(2+d\).  Replacing the old path produces a valid system of amount
\(L+d\), consisting of \(e-1\) unchanged paths and one new path.
This again contradicts Lemma~\ref{terminal:increment}, which requires all
old paths to remain.

Thus every pair of chosen bases forbids parameters \(1,\ldots,6\).
Their radius-two balls are separated and give an independent set of size
at least
\[
 3(t-1)>2t+1\ge k,
\]
another contradiction.

\paragraph{Alternative~\ref{terminal:three}.}
Here \(e=(t-3)/2\), every amount is at least three, and
\[
 k=t+L\ge t+3e=\frac{5t-9}{2}\ge2t,
\]
since \(t\in\{9,11\}\).
In a fixed orientation, choose the representatives of all \(t-3\)
incident targets and one missing target.
No pair has two missing targets, so the endpoint restriction forbids
every parameter \(1,\ldots,6\) between chosen representatives.
Their \(t-2\) radius-two balls are separated and each contains an
independent triple.  They give
\[
 3(t-2)>2t+1\ge k,
\]
which is impossible.

\paragraph{Alternative~\ref{terminal:five}.}
Here \(t=9\) and \(k=19\).
Fix an orientation.  At the four representatives with incident targets
take radius-two balls, and at the five representatives with missing
targets take radius-one balls.
Among parameters \(1,\ldots,6\), the only potentially permitted parameter
between representatives is five, and that requires two missing targets.
Consequently, incident--incident pairs forbid parameters \(1,\ldots,6\),
incident--missing pairs forbid parameters \(1,\ldots,5\), and
missing--missing pairs forbid parameters \(1,\ldots,4\).
These are exactly the prohibitions required by
Lemma~\ref{path:separation} for radius pairs \((2,2)\), \((2,1)\), and
\((1,1)\), respectively.
All nine balls are therefore pairwise disjoint and anticomplete.
Lemma~\ref{terminal:weights}, using \(19\ge2\cdot9\), supplies independent
sets of total size
\[
 4\cdot3+5\cdot2=22>19.
\]
This final contradiction excludes every alternative and proves the
proposition.
\end{proof}
==== END Cycle-clique-Ramsey-numbers//08-terminal.tex ====

==== BEGIN Cycle-clique-Ramsey-numbers//09-finite-packing.tex ====
\subsection{Packing independent sets}\label{finite:packing-subsection}

The forbidden parameters now give lower bounds on independent sets in
exterior balls.  Throughout this subsection, $G$ has no $C_{k+1}$,
$\omega(G)\le t$, and $\alpha(G)\le k$, where $k\ge5$ and $3\le t\le k$.
We also use the expansion property
\[
 |N_G[I]|\ge k|I|+1
 \qquad\text{for every nonempty independent set }I,
\]
which was established in Lemma~\ref{red:expansion}.
In particular, $\delta(G)\ge k$.
Let $S\subseteq X\subseteq V(G)$, and let $M$ be a symmetric matrix of
valid forbidden outside-path parameters on $X$, with empty diagonal,
as defined above.  Write $n_X=|X|$.  The balls $B_r(i;X)$ are those of
Section~\ref{sec:paths}.

\begin{lemma}[Bounds for exterior balls]\label{finite:ball-bounds}
For $i\in X$, put
\[
 b_0=k+1-n_X+|\{j\in X:0\in M_{ij}\}|.
\]
Assume $b_0>0$, and define
\[
 u_0=1+\mathbf 1_{\{b_0\ge t\}}.
\]
For $r=1,2$, recursively set
\begin{align}
 A_r(i)&=\{j\in X:\{1,\ldots,r\}\subseteq M_{ij}\},
 &T_r&=|A_r(i)|,\label{finite:excluded-neighbors}\\
 b_r&=\max\{b_{r-1},\,ku_{r-1}+1-n_X+T_r\},\label{finite:ball-size}\\
 \widehat u_r&=\max\bigl\{u_{r-1},
       1+\mathbf 1_{\{b_r>t\}}
        +\mathbf 1_{\{b_r>\max(k,2t)\}}\bigr\}.
       \label{finite:ordinary-weight}
\end{align}
Set $u_r=\widehat u_r$, except that $u_r=2$ when
\begin{equation}\label{finite:exception-condition}
 \widehat u_r=1,\qquad b_{r-1}=b_r=t,\qquad
 k+1-n_X+T_r\ge t.
\end{equation}
Then, for $r=0,1,2$,
\[
 |B_r(i;X)|\ge b_r,\qquad \alpha(B_r(i;X))\ge u_r.
\]
\end{lemma}

\begin{proof}
The empty diagonal means that the vertices counted by
$|\{j:0\in M_{ij}\}|$ are all distinct from $i$.  They are nonneighbors
of $i$.  Thus at most
$n_X-1-|\{j:0\in M_{ij}\}|$ neighbors of $i$ lie in $X$, proving the
bound on $|B_0(i;X)|$.  Positivity gives an independent vertex.
Furthermore, a $t$-clique in $B_0(i;X)$ together with $i$ would be a
$(t+1)$-clique.  Therefore $b_0\ge t$ forces an independent pair, which
proves the asserted value of $u_0$.

Suppose the bounds have been proved at radius $r-1$.  Each vertex
$j\in A_r(i)$ is distinct from $i$, because $M_{ii}$ is empty, and has
no neighbor in $B_{r-1}(i;X)$.  Indeed, such a neighbor would give an
outside $i$--$j$ path with between one and $r$ internal vertices, by
the no-neighbor assertion of Lemma~\ref{path:separation}.
Choose an independent set $I\subseteq B_{r-1}(i;X)$ of order
$u_{r-1}$.  Its closed neighborhood outside $X$ is contained in
$B_r(i;X)$, whereas its closed neighborhood inside $X$ avoids the
$T_r$ vertices of $A_r(i)$.  Expansion gives
\[
 |B_r(i;X)|\ge ku_{r-1}+1-(n_X-T_r).
\]
The balls are nested, so \eqref{finite:ball-size} follows.
Nesting also preserves the independence bound $u_{r-1}$.
If $b_r>t$, the ball is not a clique; if $b_r>\max(k,2t)$,
Lemma~\ref{size:test} supplies an independent triple.
These are precisely the additional bounds in
\eqref{finite:ordinary-weight}, with the stated strict inequalities.

It remains to justify \eqref{finite:exception-condition}.
If $B_r(i;X)$ were a clique $C$, nesting and
$b_{r-1}=b_r=t$ would force
\[
 B_{r-1}(i;X)=B_r(i;X)=C,\qquad |C|=t.
\]
Every $v\in C$ has at most $t-1$ neighbors outside $X$, since
$B_r(i;X)$ contains all outside neighbors of the preceding ball.
The vertices of $A_r(i)$ are also unavailable as neighbors.  Hence
\[
 k+1-t
 \ \le\ |N_G(v)\cap X|
 \ \le\ n_X-T_r
 \ \le\ k+1-t.
\]
If the last inequality were strict, there would already be a
contradiction.  Otherwise equality forces $v$ to be adjacent to every
vertex of $X\setminus A_r(i)$, including $i$.
Thus $C\cup\{i\}$ is a $(t+1)$-clique, a contradiction.
The ball therefore contains an independent pair.
\end{proof}

For each $i\in X$, include the \emph{singleton option} $\{i\}$, label its
radius by $-1$, and give it weight one.  If $b_0>0$, also include the
options $B_r(i;X)$, for $r=0,1,2$, with weights $u_r$ from
Lemma~\ref{finite:ball-bounds}.  If $b_0\le0$, include no ball option at
$i$: the available bound does not certify that a ball is nonempty.
This omission makes no assertion about the actual ball.

\begin{lemma}[Packing test]\label{finite:packing}
Let a family of these options have distinct base vertices.
For options based at $i,j$ with radius labels $r,s$, require
\begin{equation}\label{finite:compatibility}
 \begin{cases}
 0\in M_{ij},&r=s=-1,\\
 \{1,\ldots,r+s+2\}\subseteq M_{ij},&\text{otherwise}.
 \end{cases}
\end{equation}
If every pair satisfies this condition, the sum of the option weights
is at most $k$.
\end{lemma}

\begin{proof}
For $r,s\ge0$, the balls are disjoint and anticomplete by
Lemma~\ref{path:separation}.  For a singleton $\{i\}$ and a ball
$B_s(j;X)$, disjointness is automatic.  An edge between them would give
an outside $i$--$j$ path with between one and $s+1$ internal vertices,
which is prohibited by \eqref{finite:compatibility} with $r=-1$.
Two singleton options are nonadjacent precisely when their joining edge
is absent, as certified by $0\in M_{ij}$.
Thus all represented sets are disjoint and pairwise anticomplete.
Independent subsets of their certified weights combine into an
independent set in $G$.  Its order cannot exceed $k$.
\end{proof}

\paragraph{Removing redundant radii.}
Retain every singleton and every available radius-zero option.
For $r=1,2$, retain the option at radius $r$ only when
$u_r>u_{r-1}$; still compute both bounds at every radius.
This does not change whether a family of weight greater than $k$
exists.  Indeed, an omitted positive radius $r$ has the same weight as
the most recent retained \emph{nonnegative} radius $q0$, the first tuple consumes
$\ell(p)+1\ge1$ vertices and $\sigma(p)$ amount.  The inductive
hypothesis supplies every allowed tail exactly once, while its lower
bound $p$ enforces nondecreasing order.  Conversely, every permitted
list has exactly this first tuple and one of these tails.  This proves
both coverage and uniqueness.
\end{proof}

In particular, a system containing no paths is represented by $t$
empty component tuples.  The outer empty list instead represents a
forest on zero vertices.  Unused amount budget is allowed: optimality
does not require $L=k-t$.  Enumerating some patterns that cannot occur
as optimal systems causes no difficulty; Lemma~\ref{finite:coverage}
ensures that every system that could occur is present.

There are exactly $42$ parameter pairs in \eqref{finite:domain},
and their pattern lists contain $3099$ instances in total.  A pattern
appearing for two different parameter pairs is counted once for each
pair.  Table~\ref{finite:counts} gives the counts.  For completeness,
these numbers have a separate elementary enumeration.  If $a(r,m)$
denotes the number of chain types with $r\ge1$ edges and amount
$m\ge r$, reversal pairs all positive compositions except the
palindromes.  Hence
\begin{equation}\label{finite:chain-count}
 a(r,m)=\frac12\left(\binom{m-1}{r-1}+b(r,m)\right),
\end{equation}
where
\[
 \begin{aligned}
 b(2s,m)&=
 \begin{cases}
  \binom{m/2-1}{s-1},&m\text{ even},\\
  0,&m\text{ odd},
 \end{cases}\\
 b(2s+1,m)&=\binom{\lfloor(m-1)/2\rfloor}{s}.
 \end{aligned}
\]
The even formula follows by pairing equal entries; the odd formula
also allows a positive central entry and sums over the paired entries.
The case $s=0$ in the odd formula gives one type with a single edge.
Choosing a multiset of chain types and then singleton components shows
that the count for $(t,B)$ is
\begin{equation}\label{finite:count-series}
 \sum_{L=0}^{B}[x^t y^L]\,
 \frac{1}{1-x}
 \prod_{r\ge1}\prod_{m\ge r}
       (1-x^{r+1}y^m)^{-a(r,m)}.
\end{equation}
Only factors with $r+1\le t$ and $m\le B$ contribute.  Thus the
table can be checked by finite integer arithmetic independently of
the deductions that exclude the patterns.

\begin{table}[htbp]
\centering
\begin{tabular}{ccl}
$k$ & admissible $t$ & number of patterns, summed over $t$\\
\hline
5 & $3,4,5$ & $4+2+1=7$\\
6 & $3,4,5,6$ & $6+5+2+1=14$\\
7 & $3,4,5,6,7$ & $9+9+5+2+1=26$\\
8 & $4,5,6,7,8$ & $16+10+5+2+1=34$\\
9 & $4,5,6,7,8$ & $25+20+11+5+2=63$\\
10 & $5,6,7,8$ & $35+24+11+5=75$\\
11 & $5,6,7,8$ & $60+46+25+11=142$\\
12 & $6,7,8$ & $87+51+26=164$\\
13 & $6,7,8$ & $152+104+55=311$\\
14 & $7,8$ & $197+118=315$\\
15 & $7,8$ & $364+237=601$\\
16 & $8$ & $468$\\
17 & $8$ & $879$
\end{tabular}
\caption{All admissible parameter pairs and their pattern counts,
with amount budget $B=k-t$.  These are counts of weighted forests,
not of ambient graphs.}
\label{finite:counts}
\end{table}

\subsection{Required edges and path labels}

We now give each pattern a concrete graph on $S$, to which the
subsequent deductions can be applied.  Process its components in
their chosen order and traverse each one in its chosen orientation.
Label its clique vertices and all intervening path interiors
consecutively, beginning with label zero for the first component and
continuing with the next unused label at each new component.
Thus $S$ is identified with $\{0,\ldots,t+L-1\}$.

Let $\mathcal E(P)$ be the ordered list of pairs $(a,b)$ of clique
labels corresponding to the original paths, in this traversal order.
An edge of amount $q$ has $b=a+q+1$, and its expanded path is
$a,a+1,\ldots,b$.  Let $J$ be the graph whose edges are all clique
edges on $Q$ and all consecutive steps of these expanded paths.
We call these the \emph{required edges}: every one is present in
$G[S]$, while a pair not joined in $J$ may or may not be an edge
of $G[S]$.

For a label $x\in S$, define the set of endpoint choices
\begin{equation}\label{finite:tips}
 T(x)=
 \begin{cases}
  \{x\},&x\in Q,\\
  \{a,b\},&a=Stealth]
\node[vertex,label=above:$p$] (p) at (0,1.2) {};
\node[vertex,label=above:$\rho(q)$] (r) at (1.4,1.2) {};
\node[vertex,label=above:$q$] (q) at (4.8,1.2) {};
\node[vertex,label=below:$p'$] (pp) at (0,-1.2) {};
\node[vertex,label=below:$\rho(q')$] (rr) at (1.4,-1.2) {};
\node[vertex,label=below:$q'$] (qq) at (4.8,-1.2) {};
\draw[dashed] (p)--(r) (pp)--(rr);
\draw[very thick,->] (r)--(q);
\draw[very thick,->] (rr)--(qq);
\draw[very thick] (r) to[bend right=55] node[left,xshift=-3pt] {$d$ new vertices} (rr);
\node at (3.3,.78) {$a$ interior vertices};
\node at (3.3,-.78) {$b$ interior vertices};
\node at (3.2,0) {new path: $q\longleftrightarrow q'$};
\end{tikzpicture}
\caption{Representative replacement when both targets have incoming
paths. Each representative is the \emph{first} interior vertex on its
incoming path. Deleting the initial edge of each incoming path leaves its
full representative-to-target segment available. The new
path has amount $a+b+d$, so the entire system has amount $L+d$.
Lemma~\ref{grow:replacement} also treats a target at a chain start and
two targets on the same original chain. Dashed initial steps are not
used by the new path.}
\label{fig:representatives}
\end{figure}
==== END Cycle-clique-Ramsey-numbers//representative-figure.tex ====

==== BEGIN Cycle-clique-Ramsey-numbers//references.bib ====
@article{KeevashLongSkokan2021,
  author = {Keevash, Peter and Long, Eoin and Skokan, Jozef},
  title = {Cycle-Complete {Ramsey} Numbers},
  journal = {International Mathematics Research Notices},
  volume = {2021},
  number = {1},
  year = {2021},
  pages = {275--300},
  doi = {10.1093/imrn/rnz119},
  eprint = {1807.06376},
  archivePrefix = {arXiv},
  primaryClass = {math.CO},
  url = {https://academic.oup.com/imrn/article/2021/1/275/5530320},
  note = {\href{https://doi.org/10.1093/imrn/rnz119}{Published article}}
}

@article{ErdosFaudreeRousseauSchelp1978,
  author = {Erd{\H{o}}s, P. and Faudree, R. J. and Rousseau, C. C. and Schelp, R. H.},
  title = {On cycle--complete graph {Ramsey} numbers},
  journal = {Journal of Graph Theory},
  volume = {2},
  number = {1},
  year = {1978},
  pages = {53--64},
  doi = {10.1002/jgt.3190020107},
  url = {https://www.renyi.hu/~p_erdos/1978-18.pdf},
  note = {\href{https://doi.org/10.1002/jgt.3190020107}{Published article}}
}

@article{BondyErdos1973,
  author = {Bondy, J. A. and Erd{\H{o}}s, P.},
  title = {{Ramsey} numbers for cycles in graphs},
  journal = {Journal of Combinatorial Theory, Series B},
  volume = {14},
  number = {1},
  year = {1973},
  pages = {46--54},
  doi = {10.1016/S0095-8956(73)80005-X},
  url = {https://users.renyi.hu/~p_erdos/1973-22.pdf},
  note = {\href{https://doi.org/10.1016/S0095-8956(73)80005-X}{Published article}}
}

@article{YangHuangZhang1999,
  author = {Yang, J. S. and Huang, Y. R. and Zhang, K. M.},
  title = {The value of the {Ramsey} number {$R(C_n,K_4)$} is {$3(n-1)+1$} ({$n\geq4$})},
  journal = {Australasian Journal of Combinatorics},
  volume = {20},
  year = {1999},
  pages = {205--206},
  url = {https://ajc.maths.uq.edu.au/pdf/20/ocr-ajc-v20-p205.pdf},
  note = {\href{https://ajc.maths.uq.edu.au/pdf/20/ocr-ajc-v20-p205.pdf}{Publisher's full text}}
}

@article{BollobasEtAl2000,
  author = {Bollob{\'a}s, B. and Jayawardene, C. and Yang, J. and Huang, Y. R. and Rousseau, C. and Zhang, K. M.},
  title = {On a conjecture involving cycle-complete graph {Ramsey} numbers},
  journal = {Australasian Journal of Combinatorics},
  volume = {22},
  year = {2000},
  pages = {63--71},
  url = {https://ajc.maths.uq.edu.au/pdf/22/ocr-ajc-v22-p63.pdf},
  note = {\href{https://ajc.maths.uq.edu.au/pdf/22/ocr-ajc-v22-p63.pdf}{Publisher's full text}}
}

@article{Schiermeyer2003,
  author = {Schiermeyer, Ingo},
  title = {All cycle-complete graph {Ramsey} numbers {$r(C_m,K_6)$}},
  journal = {Journal of Graph Theory},
  volume = {44},
  number = {4},
  year = {2003},
  pages = {251--260},
  doi = {10.1002/jgt.10145},
  url = {https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.10145},
  note = {\href{https://doi.org/10.1002/jgt.10145}{Published article}}
}

@article{Nikiforov2005,
  author = {Nikiforov, Vladimir},
  title = {The Cycle-Complete Graph {Ramsey} Numbers},
  journal = {Combinatorics, Probability and Computing},
  volume = {14},
  number = {3},
  year = {2005},
  pages = {349--370},
  doi = {10.1017/S096354830400642X},
  eprint = {math/0404501},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.1017/S096354830400642X},
  note = {\href{https://doi.org/10.1017/S096354830400642X}{Published article}}
}

@article{ChvatalErdos1972,
  author = {Chv{\'a}tal, V. and Erd{\H{o}}s, P.},
  title = {A note on {Hamiltonian} circuits},
  journal = {Discrete Mathematics},
  volume = {2},
  number = {2},
  year = {1972},
  pages = {111--113},
  doi = {10.1016/0012-365X(72)90079-9},
  url = {https://users.renyi.hu/~p_erdos/1972-02.pdf},
  note = {\href{https://doi.org/10.1016/0012-365X(72)90079-9}{Published article}}
}

@article{ChartrandSchuster1971,
  author = {Chartrand, Gary and Schuster, Seymour},
  title = {On the existence of specified cycles in complementary graphs},
  journal = {Bulletin of the American Mathematical Society},
  volume = {77},
  number = {6},
  year = {1971},
  pages = {995--998},
  doi = {10.1090/S0002-9904-1971-12832-X},
  note = {\href{https://doi.org/10.1090/S0002-9904-1971-12832-X}{Published article}}
}

@article{ChenChengZhang2008,
  author = {Chen, Yaojun and Cheng, T. C. Edwin and Zhang, Yunqing},
  title = {The {Ramsey} numbers {$R(C_m,K_7)$} and {$R(C_7,K_8)$}},
  journal = {European Journal of Combinatorics},
  volume = {29},
  number = {5},
  year = {2008},
  pages = {1337--1352},
  doi = {10.1016/j.ejc.2007.05.007},
  url = {https://ira.lib.polyu.edu.hk/handle/10397/1264},
  note = {\href{https://doi.org/10.1016/j.ejc.2007.05.007}{Published article}}
}

@article{Posa1963,
  author = {P{\'o}sa, L.},
  title = {On the circuits of finite graphs},
  journal = {Magyar Tudom{\'a}nyos Akad{\'e}mia Matematikai Kutat{\'o} Int{\'e}zet{\'e}nek K{\"o}zlem{\'e}nyei},
  volume = {8},
  year = {1963},
  pages = {355--361},
  url = {https://real.mtak.hu/201453/1/cut_MATKUTINT_8_3_1963_pp355_-_361.pdf},
  note = {\href{https://real.mtak.hu/201453/1/cut_MATKUTINT_8_3_1963_pp355_-_361.pdf}{Primary scan}}
}

@article{RadziszowskiJin1994,
  author = {Radziszowski, Stanis{\l}aw P. and Jin, Xia},
  title = {Paths, cycles and wheels in graphs without antitriangles},
  journal = {Australasian Journal of Combinatorics},
  volume = {9},
  year = {1994},
  pages = {221--232},
  url = {https://ajc.maths.uq.edu.au/pdf/9/ocr-ajc-v9-p221.pdf},
  note = {\href{https://ajc.maths.uq.edu.au/pdf/9/ocr-ajc-v9-p221.pdf}{Publisher's full text}}
}

@article{JaradatAlzaleq2007,
  author = {Jaradat, M. M. M. and Alzaleq, B. M. N.},
  title = {The cycle-complete graph {Ramsey} number {$r(C_8,K_8)$}},
  journal = {SUT Journal of Mathematics},
  volume = {43},
  number = {1},
  year = {2007},
  pages = {85--98},
  url = {https://sites.ju.edu.jo/sites/Alzalg/Documents/Papers/r88.pdf},
  note = {\href{https://sites.ju.edu.jo/sites/Alzalg/Documents/Papers/r88.pdf}{Author's copy}}
}

@article{ZhangZhang2009,
  author = {Zhang, Yunqing and Zhang, Ke Min},
  title = {The {Ramsey} number {$R(C_8,K_8)$}},
  journal = {Discrete Mathematics},
  volume = {309},
  number = {5},
  year = {2009},
  pages = {1084--1090},
  doi = {10.1016/j.disc.2007.11.064},
  url = {https://www.sciencedirect.com/science/article/pii/S0012365X07009764},
  note = {\href{https://doi.org/10.1016/j.disc.2007.11.064}{Published article}}
}

@article{BatainehJaradatAlZaleq2011,
  author = {Bataineh, M. S. A. and Jaradat, M. M. M. and Al-Zaleq, L. M. N.},
  title = {The cycle-complete graph {Ramsey} number {$r(C_9,K_8)$}},
  journal = {ISRN Algebra},
  volume = {2011},
  year = {2011},
  pages = {1--10},
  doi = {10.5402/2011/926191},
  url = {https://onlinelibrary.wiley.com/doi/full/10.5402/2011/926191},
  note = {Article ID 926191. \href{https://doi.org/10.5402/2011/926191}{Published article}}
}

@article{Baniabedalruhman2023,
  author = {Baniabedalruhman, A.},
  title = {The cycle-complete graph {Ramsey} numbers {$R(C_n,K_8)$}, for {$10\le n\le15$}},
  journal = {Jordan Journal of Mathematics and Statistics},
  volume = {16},
  number = {4},
  year = {2023},
  pages = {703--718},
  doi = {10.47013/16.4.6},
  url = {https://journals.yu.edu.jo/jjms/Issues/Vol16No42023PDF/6.PDF},
  note = {\href{https://doi.org/10.47013/16.4.6}{Published article}}
}
==== END Cycle-clique-Ramsey-numbers//references.bib ====