# Ramsey numbers of connected 4-clique matching

Krit Kanopthamakun  Division of Computational Science, Faculty of Science,
Prince of Songkla University, Thailand<EMAIL_ADDRESS>and  Panupong
Vichitkunakorn  Division of Computational Science, Faculty of Science, Prince
of Songkla University, Thailand<EMAIL_ADDRESS>
###### Abstract.

We determine the exact value of the $2$-color Ramsey number of a connected
$4$-clique matching $\mathscr{C}(nK_{4})$ which is a set of connected graphs
containing $n$ disjoint $K_{4}$. That is, we show that
$R_{2}(\mathscr{C}(nK_{4}))=13n-3$ for any positive integer $n\geq 3$. The
result is an extension of the result by (Roberts, 2017) which gave that result
when $n\geq 18$. We also show that the result still holds when $n=2$ provided
that $R_{2}(2K_{4})\leq 23$.

##  1\. Introduction and Preliminaries

The literature on Ramsey-type problems begins in 1930 with Ramsey’s original
paper [12]. Ramsey’s famous theorem makes an analogous assertion regarding the
partitioning of $r$-element subsets of objects into classes. A thorough study
of Ramsey’s theorem and other partitioning theorems later appears in Graham-
Rothschild-Spencer [8].

######  Definition 1 ([15]).

Let $\binom{s}{r}$ denote the set of $r$-element subsets ($r$-sets) of a set
$S$. A set $T\subseteq S$ is _homogeneous_ under a coloring of $\binom{s}{r}$
if all $r$-sets in $T$ receive the same color; it is $i$-_homogeneous_ if that
color is $i$.

Let $r$ and $p_{1},p_{2},\ldots,p_{k}$ be positive integers. If there is an
integer $N$ such that every $k$-coloring of $\binom{[N]}{r}$ yields an
$i$-homogeneous set of size $p_{i}$ for some $i$, then the smallest integer is
the _Ramsey number_ $R(p_{1},\ldots,p_{k};r)$.

######  Theorem 2 ([15]).

Given a positive integers $r$ and $p_{1},p_{2},\ldots,p_{k}$, there exists an
integer $N$ such that every $k$-coloring of $\binom{[N]}{r}$ yields an
$i$-homogeneous set of size $p_{i}$ for some $i$, where $\binom{[N]}{r}$
denote the set of $r$-subsets of a set $[N]$.

We consider the case $r=2$, which is an edge-coloring of graphs. We abbreviate
the notation $R(p_{1},p_{2},\ldots,p_{k};r)$ to $R(p_{1},p_{2},\ldots,p_{k})$.
Until now, no exact formula is known for general values of $p_{i}$ and $r$ and
few Ramsey numbers have been computed, even for $k=2$:
$R(3,3)=6,R(3,4)=9,R(3,5)=14,R(3,6)=18,R(3,7)=23,R(3,8)=28,R(3,9)=36,R(4,4)=18$
and $R(4,5)=25$. See [11] and references therein.

For $k=3$, only two Ramsey numbers are known, which are $R(3,3,3)=17$ [6] and
$R(3,3,4)=30$ [5]. For $k>3$, the exact values of Ramsey numbers are still
unknown, see the survey [11] for other bounds on Ramsey numbers $R(k,l)$.

Ramsey’s Theorem for $r=2$ says that $k$-edge-coloring of a large enough
complete graph $G$ always induces a monochromatic complete subgraph of a given
size. If we want a monochromatic copy of non-complete subgraph, it may require
a smaller graph $G$. So we can define the Ramsey number of any graph. In this
paper, we follow the notations in [15].

######  Definition 3.

Given simple graphs $G_{1},G_{2},\ldots,G_{k}$, the _(graph)_ _Ramsey number_
$R(G_{1},\ldots,G_{k})$ is the smallest integer $n$ such that every
$k$-coloring of $E(K_{n})$ contains a copy of $G_{i}$ in color $i$ for some
$i$. When $G_{i}=G$ for all $i$, we write $R_{k}(G)$ for
$R(G_{1},\ldots,G_{k})$.

There are a lot of research about Ramsey number for non-complete graphs (see
the survey [11]) such as complete bipartite graphs, cycles, paths, stars, etc.

For disconnected graphs, there are only few results. For example, [4] found
the exact formula of $R(n_{1}P_{2},n_{2}P_{2},\ldots,n_{k}P_{2})$, and later
[9] extended it to a more general case of
$R(K_{m},n_{1}P_{2},n_{2}P_{2},\ldots,n_{k}P_{2})$. Later, there are more
results on general cases of disconnected graphs, such as forest [14] and
multiple copies of complete graphs [10, 3, 4].

Other kinds of Ramsey number have been studied as well. For Ramsey numbers
$R_{2}(nK_{r})$, the exact formula for any $n\geq 2$ is only known when $r$ is
either $2$ [4, 9] or $3$ [3]. For $r=4$, [2] gave the formula when $n$ is
large.

Let $G$ be a disconnected graph and $\mathscr{C}(G)$ be the set of all
connected graphs containing $G$. Then $R_{k}(\mathscr{C}(G))$ is the least
integer $n$ such that any $k$-edge-coloring on $K_{n}$ contains a
monochromatic copy of a graph in $\mathscr{C}(G)$, see [7, 13].

For $r=3$, we call a graph in $\mathscr{C}(nK_{r})$ a connected triangle
matching. $R_{2}(\mathscr{C}(nK_{3}))=7n-2$ is proved by [7]. For $r\geq 4$,
the only result for $R_{2}(\mathscr{C}(nK_{r}))$ is the following.

######  Theorem 4.

[13] For $r\geq 4$ and $n\geq R_{2}(K_{r})$ we have

$R_{2}(\mathscr{C}(nK_{r}))=(r^{2}-r+1)n-r+1.$

In this paper, we are only interested in the case when $r=4$. Theorem 4 showed
that $R_{2}(\mathscr{C}(nK_{4}))=13n-3$ when $n\geq R_{2}(K_{4})=18$. The main
goal of this paper is to extend Theorem 4 from $n\geq 18$ to $n\geq 3$.

The paper is structured as follows. In Section 2, we prove Lemma 5, which is
the main lemma of the paper. We then construct the proof of the main result,
Theorem 7, and divide it into four parts in Sections 3–6. We end the section
with another three lemmas which will be used in later sections. In Section 8,
we discuss the results and further research.

##  2\. Main results

The following lemma is the main key to proving our main theorem.

######  Lemma 5.

For any positive integers $x$ and $y$ where $y\geq 4$. If a two-edge-coloring
of $K_{4x+y}$ with red and blue contains at most $x$ blue copies of $K_{4}$,
then there is a red matching of size $r$, where

$r=\begin{cases}y-3&\text{for }x\geq y-4,\\\
\left\lfloor\frac{x+y-3}{2}\right\rfloor&\text{for }x\leq y-5.\end{cases}$

###### Proof.

Let $V$ be the set of vertices of $K_{4x+y}$. For $x\geq y-4$, suppose there
is no red matching of size $y-3$. Let
$M=\\{u_{1}v_{1},u_{2}v_{2},\ldots,u_{m}v_{m}\\}$ be a maximum red matching of
size $m\leq y-4$. Let
$P=\\{u_{1},u_{2},\ldots,u_{m},v_{1},v_{2},\ldots,v_{m}\\}$ and
$P^{\prime}=V\setminus P$. We see that all edges between vertices in
$P^{\prime}$ are blue, otherwise, there will be a red matching of size larger
than $m$.

Now, for any $1\leq i\leq m$, in order to prevent a larger red matching there
are no two vertices $w_{1},w_{2}\in P^{\prime}$ such that both $u_{i}w_{1}$
and $v_{i}w_{2}$ are both red. From this observation, there are only two
cases:

  1. (1)

If both $u_{i}$ and $v_{i}$ are adjacent to some vertices in $P^{\prime}$ via
red edges, then all red edges incident to $u_{i}$ or $v_{i}$ must have a
common endpoint $w\in P^{\prime}$. Hence, $u_{i}w^{\prime}$ and
$v_{i}w^{\prime}$ are blue for all $w^{\prime}\in P^{\prime}\setminus\\{w\\}$.

  2. (2)

Either $u_{i}$ or $v_{i}$ is adjacent to every vertex in $P^{\prime}$ via a
blue edge. We assume without loss of generality that it is $v_{i}$.

We also assume that $\\{u_{i},v_{i}\\}$ is in the first case when $1\leq i\leq
k$ and is in the second case when $k+1\leq i\leq m$. Let
$W=\\{w_{1},w_{2},\ldots,w_{k}\\}$. We note that $w_{i}$’s are not necessarily
distinct.

Next we construct a blue copy of $mK_{4}$. For $1\leq i\leq k$, a blue copy of
$K_{4}$ is obtained from $v_{i}$, one vertex in $W$ which differs from $w_{i}$
and two other vertices in $P^{\prime}\setminus W$. If we cannot choose any
vertex from $W$, we choose any three vertices from $W^{\prime}$ instead. For
$k+1\leq i\leq m$, a blue copy of $K_{4}$ is obtained from $v_{i}$ and three
vertices in $P^{\prime}$. The construction is feasible, because
$|P^{\prime}|=4x+y-2m\geq 4x-y+8\geq 3x+4>3x+1\geq 3m+1$.

The number of vertices in $P^{\prime}$ which are not in those $m$ disjoint
blue copies of $K_{4}$ is $4x+y-2m-3m=4x+y-5m\geq 4x+y-5(y-4)\geq
4x-4y+20=4(x-y+5)$. These vertices can form other $x-y+5\geq x-m+1$ disjoint
blue copies of $K_{4}$. Thus, there are at least $x+1$ disjoint blue copies of
$K_{4}$, which contradicts to the assumption.

In the case $x\leq y-5$, we follow exactly the same construction. We have
$m\leq\left\lfloor\frac{x+y-3}{2}\right\rfloor-1\leq\frac{x+y-5}{2}$. If
$x<m$, we can construct a blue copy of $(x+1)K_{4}$ where each $K_{4}$
contains one vertex from $\\{v_{1},v_{2},\ldots,v_{m}\\}$ and three vertices
from $P^{\prime}$. Since $|P^{\prime}|\geq 3x+5>3(x+1)+1$, we have a blue copy
of $(x+1)K_{4}$, which is a contradiction. Hence, we may assume $x\geq m$. The
construction of the first blue copy of $mK_{4}$ is feasible because
$|P^{\prime}|=4x+y-2m\geq 4x+y-x-y+5=3x+5>3x+1\geq 3m+1$. The construction of
the other $x-m+1$ is feasible if $4x+y-2m-3m\geq 4(x-m+1)$, which is
equivalent to $y\geq m+4$. From $m\leq\frac{x+y-5}{2}$ and $x\leq y-5$, we
have $y\geq m+5$. Hence, the construction is feasible. ∎

The lower bound of $R_{2}(\mathscr{C}(nK_{4}))$ in Theorem 7 is a consequence
of Theorem 1 of [1]. In fact, the result can be directly proved as shown in
the following lemma.

######  Lemma 6.

For any integer $n\geq 2$ and $r\geq 3$,
$R_{2}(\mathscr{C}(nK_{r}))\geq(r^{2}-r+1)n-r+1$.

###### Proof.

Let $N=(r^{2}-r+1)n-r$. It can be rewritten as $N=(r-1)(rn-1)+(n-1)$. We can
construct a $2$-edge-coloring of $G=K_{N}$ using red and blue without a
monochromatic copy of a graph in $\mathscr{C}(nK_{r})$ as follows. We form a
copy of $K_{N}$ with a $2$-edge-coloring by joining a blue copy of
$(r-1)K_{rn-1}$ and a blue copy of $K_{n-1}$ using only red edges. The size of
each blue component is at most $rn-1$, hence there are at most $n-1$ disjoint
blue copies of $K_{r}$. Thus, this coloring on $G$ contains no blue copy of a
graph in $\mathscr{C}(nK_{r})$.

Any red copy $K_{r}$ in $G$ must be formed using exactly one vertex from each
of the blue components. But, the smallest component, $K_{n-1}$ has only $n-1$
vertices. Hence, there are at most $n-1$ disjoint red copies of $K_{r}$ in
$G$. Thus, there is no red copy of a graph in $\mathscr{C}(nK_{r})$. ∎

We prove the upper bound of $R_{2}(\mathscr{C}(nK_{r}))$ and obtain the exact
Ramsey number in the following theorem.

######  Theorem 7.

For any positive integer $n\geq 3$, $R_{2}(\mathscr{C}(nK_{4}))=13n-3$.

###### Proof.

We known that $R_{2}(\mathscr{C}(nK_{4}))\geq 13n-3$. For the upper bound, we
consider a $2$-edge-coloring of $G=K_{13n-3}$ with red and blue. We will show
that there is a monochromatic subgraph in $\mathscr{C}(nK_{4})$, which we will
simply call it a _connected_ monochromatic copy of $nK_{4}$ or $n$ connected
disjoint monochromatic copies of $K_{4}$. Since a graph and its complement
cannot be both disconnected, at least one color is connected, we suppose that
red is connected. If $G$ contains a red copy $nK_{4}$ or blue connected copy
of $nK_{4}$, then we are done. So, we may assume that there are at most $n-1$
disjoint red copies of $K_{4}$ and no blue connected copy of $nK_{4}$. Since
$13n-3=18+4(3n-5)+n-1$ and $R(4,4)=18$, $G$ has at least
$3n-4+\left\lfloor\frac{n-1}{4}\right\rfloor$ disjoint monochromatic copies of
$K_{4}$. Since there are at most $n-1$ disjoint red copies of $K_{4}$, there
are at least
$3n-4+\left\lfloor\frac{n-1}{4}\right\rfloor-n+1=2n-3+\left\lfloor\frac{n-1}{4}\right\rfloor$
disjoint blue copies of $K_{4}$.

Let $k$ be the maximum number of disjoint blue copies of $K_{4}$, and $K$ be
the set of such $k$ disjoint blue copies of $K_{4}$. We partition the set of
vertices $V(G)$ of $G$ into $V_{1},V_{2},\dots,V_{t}$ and $V^{\prime}$ in the
way that $G[V_{i}]$ is a blue component of $G$ containing at least one blue
copy of $K_{4}$ in $K$ and $V^{\prime}$ is the set of vertices outside
$V_{1}\cup\dots\cup V_{t}$, see Figure 1 for an example. In other words,
$V^{\prime}=V(G)\setminus(V_{1}\cup\dots\cup V_{t})$. Let $a_{i}$ be the
number of disjoint blue copies of $K_{4}$ from $K$ containing in $G[V_{i}]$.
Since there is no connected disjoint blue copies of $K_{4}$, we have
$a_{i}\leq n-1$. Hence, $t\geq 2$ as $a_{1}+\dots+a_{t}=k\geq
2n-3+\left\lfloor\frac{n-1}{4}\right\rfloor>n-1.$

$G[V_{1}]$$G[V_{2}]$$G[V^{\prime}]$ Figure 1. An example of a graph $G$
together with $V_{1}$, $V_{2}$ and $V^{\prime}$ where all red edges are
omitted.

The aim of this proof is to construct a red copy of $nK_{4}$ by partitioning
$G$ into multiple components where each component consists of one or more blue
components $G[V_{i}]$’s. All edges between any two components will be red. A
red copy of $K_{4}$ will be constructed by choosing a single vertex, a red
edge, or a red triangle from different components and combining them into a
red copy of $K_{4}$. The key is to show that there are enough vertices in each
component to do the construction.

The proof is divided into four cases, Sections 3–6, according to the value of
$k$. In each case, we get a red copy of $nK_{4}$ in $G$, which contradicts to
our assumption. Hence, for any 2-edge-coloring of $G=K_{13n-3}$, there exists
a monochromatic subgraph in $\mathscr{C}(nK_{4})$. Thus,
$R_{2}(\mathscr{C}(nK_{4}))\leq 13n-3$ for $n\geq 3$. ∎

The following three lemmas will be used in Sections 3–6.

######  Lemma 8.

Let $a_{1}+\dots+a_{t}\geq n-1+m$ where $1\leq a_{i}\leq n-1$ and
$m\leq\frac{n}{2}$. Then we can partition $a_{1},\dots,a_{t}$ into two parts
where the sum of each part is at least $m$.

###### Proof.

We can assume without loss of generality that $n-1\geq a_{1}\geq
a_{2}\geq\cdots\geq a_{t}\geq 1$. Since each $a_{i}$ is at most $n-1$, we have
$t\geq 2$.

If $a_{1}\geq a_{2}\geq m$, then $a_{1}\geq m$ and $a_{2}+\dots+a_{t}\geq m$.

If $a_{1}\geq m>a_{2}$, then $a_{2}+a_{3}+\cdots+a_{t}\geq n-1+m-a_{1}\geq m$.

If $m>a_{1}\geq a_{2}$, we can partition $a_{1},\dots,a_{t}$ into two parts
whose difference is at most the largest number $a_{1}<m$. (We can keep moving
the largest number in the larger part to the smaller part until the desired
difference is archived.) Let the sum of the smaller part be $x$. Then the sum
of the larger part is at most $x+m-1$. Since the total sum is at least
$n-1+m$, we have $x+x+m-1\geq n-1+m$, which simplifies to
$x\geq\frac{n}{2}\geq m$.

Hence, we always have two parts whose sum is at least $m$. ∎

######  Lemma 9.

Let $a_{1}+\dots+a_{t}\geq 2n-1+\left\lfloor\frac{n}{4}\right\rfloor$ where
$1\leq a_{i}\leq n-1$. Then we can partition $a_{1},\dots,a_{t}$ into three
parts where the sum of each part is at least
$\left\lceil\frac{n}{4}\right\rceil$.

###### Proof.

We can assume without loss of generality that $n-1\geq a_{1}\geq
a_{2}\geq\cdots\geq a_{t}\geq 1$. Since each $a_{i}$ is at most $n-1$, we have
$t\geq 3$. So, the claim is trivial for $n=2,3,4$ because
$\left\lceil\frac{n}{4}\right\rceil=1$. Now, we suppose that $n\geq 5$. If
$a_{3}\geq\left\lceil\frac{n}{4}\right\rceil$, then we are done.

If $a_{2}\geq\left\lceil\frac{n}{4}\right\rceil$ and
$a_{3}<\left\lceil\frac{n}{4}\right\rceil$, then
$a_{3}+a_{4}+\cdots+a_{t}\geq\left\lfloor\frac{n}{4}\right\rfloor+1\geq\left\lceil\frac{n}{4}\right\rceil$.
Thus, we can combine $a_{3},a_{4},\ldots,a_{t}$ into one part, and we are
done.

If $a_{1}\geq\left\lceil\frac{n}{4}\right\rceil$ and
$a_{2}<\left\lceil\frac{n}{4}\right\rceil$, then $a_{2}+a_{3}+\cdots+a_{t}\geq
n+\left\lfloor\frac{n}{4}\right\rfloor$. From Lemma 8, we can partition
$a_{2},\dots,a_{t}$ into two parts where the sum of each part is at least
$\left\lceil\frac{n}{4}\right\rceil$. Thus, the sum of the smallest part is at
least $\left\lceil\frac{n}{4}\right\rceil$. Therefore, we have three parts
whose sum are all at least $\left\lceil\frac{n}{4}\right\rceil$.

The last case is when $a_{1}<\left\lceil\frac{n}{4}\right\rceil$. Similar to
the previous case, we can combine $a_{1},\dots,a_{t}$ into three parts, where
the pairwise difference between the sum of each part is at most the largest
number $a_{1}\leq\left\lceil\frac{n}{4}\right\rceil$. Let $x$ be the sum of
the smallest part. Then the other parts have their sum at most
$x+\left\lceil\frac{n}{4}\right\rceil-1$. Then
$x+2(x+\left\lceil\frac{n}{4}\right\rceil-1)\geq
2n-1+\left\lfloor\frac{n}{4}\right\rfloor$, which simplifies to
$x\geq\frac{2n-\left\lceil
n/4\right\rceil}{3}\geq\left\lceil\frac{n}{4}\right\rceil$. The last
inequality comes from the fact that $2n>4\lceil\frac{n}{4}\rceil$ when $n\geq
5$. Hence, the sum of each part is at least
$\left\lceil\frac{n}{4}\right\rceil$. ∎

######  Lemma 10.

Let $a_{1}+\dots+a_{t}\geq 3n-3+\left\lceil\frac{n}{4}\right\rceil$ where
$1\leq a_{i}\leq n-1$. Then we can partition $a_{1},\dots,a_{t}$ into four
parts where the sum of each part is at least
$\left\lceil\frac{n}{4}\right\rceil$.

###### Proof.

Let $k=a_{1}+a_{2}+\cdots+a_{t}$, where $n-1\geq a_{1}\geq a_{2}\geq\cdots\geq
a_{t}\geq 1$. Since each part is at most $n-1$ and $k>3n-3$, we get $t\geq 4$.
The claim is obvious when $2\leq n\leq 4$.

Let $n\geq 5$. We use the same method as in the proof Lemma 9. Consider the
following cases.

  * •

$a_{1}\geq a_{2}\geq a_{3}\geq a_{4}\geq\left\lceil\frac{n}{4}\right\rceil$.
Then $a_{4}+\dots+a_{t}\geq\left\lceil\frac{n}{4}\right\rceil$.

  * •

$a_{1}\geq a_{2}\geq a_{3}\geq\left\lceil\frac{n}{4}\right\rceil>a_{4}$. Then
$a_{4}+\dots+a_{t}\geq
3n-3+\left\lceil\frac{n}{4}\right\rceil-(3n-3)\geq\left\lceil\frac{n}{4}\right\rceil$.

  * •

$a_{1}\geq a_{2}\geq\left\lceil\frac{n}{4}\right\rceil>a_{3}\geq a_{4}$. Then
$a_{3}+\dots+a_{t}\geq n-1+\left\lceil\frac{n}{4}\right\rceil$. From Lemma 8,
we can combine $a_{3},\dots,a_{t}$ into two parts where each part is at least
$\left\lceil\frac{n}{4}\right\rceil$.

  * •

$a_{1}\geq\left\lceil\frac{n}{4}\right\rceil>a_{2}\geq a_{3}\geq a_{4}$. Then
$a_{2}+\dots+a_{t}\geq 2n-2+\left\lceil\frac{n}{4}\right\rceil$. From Lemma 9,
we can combine $a_{2},\dots,a_{t}$ into three parts where each part is at
least $\left\lceil\frac{n}{4}\right\rceil$.

  * •

$\left\lceil\frac{n}{4}\right\rceil>a_{1}\geq a_{2}\geq a_{3}\geq a_{4}$. We
can combine $a_{1},\dots,a_{t}$ into four parts where each part differs from
another by at most the size of the largest part
$a_{1}<\left\lceil\frac{n}{4}\right\rceil$. Let $x$ be the sum of the smallest
part. Then the sum of largest part is at most
$x+\left\lceil\frac{n}{4}\right\rceil-1$. Consider the sum of the four parts,
we have

$x+3\left(x+\left\lceil\dfrac{n}{4}\right\rceil-1\right)\geq
3n-3+\left\lceil\dfrac{n}{4}\right\rceil.$

This implies that

$x\geq\frac{3n-2\left\lceil\frac{n}{4}\right\rceil}{4}\geq\left\lceil\frac{n}{4}\right\rceil.$

From all cases, we get four parts where each part is at least
$\left\lceil\frac{n}{4}\right\rceil$. ∎

##  3\. Proof of the first case

Let $2n-3+\left\lfloor\frac{n-1}{4}\right\rfloor\leq k\leq
2n-2+\left\lfloor\frac{n}{4}\right\rfloor$. We combine
$V_{1},V_{2},\ldots,V_{t}$ and $V^{\prime}$ into two disjoint sets, say
$U_{1}$ and $U_{2}$. So, each $U_{i}$ is a disjoint union of some sets from
$V_{1},V_{2},\ldots,V_{t}$ and $V^{\prime}$. Let $x_{1}$ and $x_{2}$ be the
number of disjoint blue copies of $K_{4}$ containing in $G[U_{1}]$ and
$G[U_{2}]$, respectively. Since the number of disjoint blue copies of $K_{4}$
in $G[V_{i}]$ is at most $n-1$, we can combine these
$V_{1},V_{2},\ldots,V_{t}$ and $V^{\prime}$ into $U_{1}$ and $U_{2}$ so that
the difference between $x_{1}$ and $x_{2}$ is at most $n-1$. We note that all
edges between $U_{1}$ and $U_{2}$ are red.

Let $Y_{1}$ and $Y_{2}$ be the set of vertices in $U_{1}$ and $U_{2}$ that are
not used in any $K_{4}$ from $K$, respectively. We also let $y_{1}=\lvert
Y_{1}\rvert$ and $y_{2}=\lvert Y_{2}\rvert$. Since $x_{1}+x_{2}=k$ and
$4x_{1}+4x_{2}+y_{1}+y_{2}=13n-3$. Hence,

$y_{1}+y_{2}=13n-3-4k\geq 5n+5-4\left\lfloor\dfrac{n}{4}\right\rfloor.$ (1)

Since the difference between $x_{1}$ and $x_{2}$ is at most $n-1$, we get

$2x_{i}\geq k-(n-1)\geq
2n-3+\left\lfloor\frac{n-1}{4}\right\rfloor-(n-1)=n-2+\left\lfloor\frac{n-1}{4}\right\rfloor.$

We can conclude that

$x_{i}\geq\frac{n}{2}-1+\frac{1}{2}\left\lfloor\dfrac{n-1}{4}\right\rfloor.$
(2)

This also gives

$4x_{i}\geq n.$ (3)

From Eq. (1), $y_{1}$ and $y_{2}$ cannot be both less than four.

Case 1:

Exactly one of $y_{1}$ and $y_{2}$ is less than four.

We suppose that $y_{1}<4$. Then $y_{2}\geq
5n+2-4\left\lfloor\frac{n}{4}\right\rfloor\geq 3n+6=9+3(n-1)$. Since
$R(3,4)=9$ and $G[Y_{2}]$ contains no blue copy of $K_{4}$, there is a red
copy of $nK_{3}$ in $G[Y_{2}]$. Since $\lvert U_{1}\rvert\geq 4x_{1}\geq n$
from Eq. (3), we can then construct a red copy of $nK_{4}$ using $n$ vertices
in $U_{1}$ and a red copy of $nK_{3}$ in $G[Y_{2}]$.

Case 2:

$y_{1},y_{2}\geq 4$.

We assume $y_{1}\geq y_{2}$. Eq. (1) gives $y_{1}+y_{2}\geq
5n+5-4\left\lfloor\frac{n}{4}\right\rfloor\geq 4n+5$. Hence $y_{1}\geq 2n+3$.
By Eq. (2), we have $x_{1}=k-x_{2}\leq
2n-2+\left\lfloor\frac{n}{4}\right\rfloor-\frac{n-1}{2}-\frac{1}{2}\left\lfloor\frac{n-1}{4}\right\rfloor\leq
2n-2\leq y_{1}-5$. By Lemma 5, $G[U_{1}]$ contains a red matching of size
$r_{1}=\left\lfloor\frac{x_{1}+y_{1}-3}{2}\right\rfloor\geq\left\lfloor\frac{x_{1}+2n}{2}\right\rfloor\geq
n$. If $G[U_{2}]$ contains a red matching of size at least $n$, we can create
a red copy of $nK_{4}$ using $n$ red edges in $G[U_{1}]$ and $n$ red edges in
$G[U_{2}]$. So we assume that $G[U_{2}]$ has no red matching of size $n$.

Case 2.1:

$x_{2}\geq y_{2}-4$.

By Lemma 5, $G[U_{2}]$ contains a red matching of size $y_{2}-3$, which must
be less than $n$. We then have $4\leq y_{2}<n+3$. First, we can construct
$y_{2}-3$ disjoint red copies of $K_{4}$ from one red matching of size
$y_{2}-3$ from $G[U_{1}]$ and another from $G[U_{2}]$. Next, we need to
construct $n-y_{2}+3$ additional disjoint red copies of $K_{4}$. In $Y_{1}$,
apart from vertices in $y_{2}-3$ red copies of $K_{4}$, there are
$y_{1}-2(y_{2}-3)$ remaining vertices. From Eq. (1), we have

$y_{1}+y_{2}\geq 5n+5-4\left\lfloor\dfrac{n}{4}\right\rfloor\geq 3n+9.$

Hence,

$y_{1}-2y_{2}+6\geq 3n-3y_{2}+15\geq 9+3(n-y_{2}+2).$

Therefore, there are $n-y_{2}+3$ disjoint red copies of $K_{3}$ available in
$G[U_{1}]$. Lastly, we need to show that there are at least $n-y_{2}+3$
remaining vertices in $U_{2}$ apart from vertices in $y_{2}-3$ disjoint red
copies of $K_{4}$. From Eq. (3), we have

$4x_{2}+y_{2}-2(y_{2}-3)\geq n-y_{2}+3.$

Hence, there is a red copy of $nK_{4}$ in $G$.

Case 2.2:

$x_{2}\leq y_{2}-5$.

Again, by Lemma 5 we get a red matching of size
$r_{2}=\left\lfloor\frac{x_{2}+y_{2}-3}{2}\right\rfloor$, which must be less
than $n$. Again, we can construct a red copy of $r_{2}K_{4}$ by connecting two
red matchings of size $r_{2}$ from $G[U_{1}]$ and $G[U_{2}]$. So, we need
additional $n-r_{2}$ disjoint red copies of $K_{4}$ in $G$.

From $r_{2}=\left\lfloor\frac{x_{2}+y_{2}-3}{2}\right\rfloor<n$, we get
$x_{2}+y_{2}\leq 2n+2$. Since $2x_{2}\leq x_{2}+y_{2}-5\leq 2n-3$, we can
conclude that $x_{2}\leq n-2$. So,

$x_{1}=k-x_{2}\geq 2n-3+\left\lfloor\frac{n-1}{4}\right\rfloor-(n-2)\geq
n-1+\left\lfloor\frac{n-1}{4}\right\rfloor.$

  * •:

$x_{1}=n-1+\left\lfloor\frac{n-1}{4}\right\rfloor$

Then $x_{2}=n-2$. Hence,

$n+3=x_{2}+5\leq y_{2}\leq 2n+2-x_{2}\leq n+4.$

So $y_{2}$ can be either $n+3$ or $n+4$. Since
$4x_{1}+4x_{2}+y_{1}+y_{2}=13n-3$, we then have

$y_{1}\geq(13n-3)-4(n-1)-4\left\lfloor\frac{n-1}{4}\right\rfloor-4(n-2)-(n+4)\geq
3n+6.$

Hence,

$y_{1}-2r_{2}\geq 3n+6-3r_{2}=9+3(n-r_{2}-1).$

Thus, there are $n-r_{2}$ disjoint red copies of $K_{3}$ using vertices from
$U_{1}$ apart from vertices in the $r_{2}$ disjoint red copies of $K_{4}$.

  * •:

$x_{1}\geq n+\left\lfloor\frac{n-1}{4}\right\rfloor$.

Recall that we have constructed a red copy of $r_{2}K_{4}$ using $r_{2}<n$ red
matching in $G[U_{1}]$. We would like to show further that when $x_{1}\geq
n+\left\lfloor\frac{n-1}{4}\right\rfloor$ those $r_{2}$ red matching can be
constructed without using any vertices in $Y_{1}$. Since each blue component
of $G[U_{1}]$ contains at most $n-1$ disjoint blue copies of $K_{4}$, we can
partition the blue components in $G[U_{1}]$ into two parts where the smaller
part has at least $\left\lfloor\frac{n-1}{4}\right\rfloor+1$ disjoint blue
copies of $K_{4}$. We know that edges between these two parts are red and the
number of vertices in each part is at least
$4(\left\lfloor\frac{n-1}{4}\right\rfloor+1)\geq n$. Hence, we can construct a
red matching of size $r_{2}<n$ in $G[U_{1}]$ using no vertices from $Y_{1}$.

We now construct $n-r_{2}$ disjoint red copies of $K_{3}$ in $G[Y_{1}]$. Since
there is no blue copy of $K_{4}$ in $G[Y_{1}]$ and $R(3,4)=9$, we need to show
that $y_{1}\geq 9+3(n-r_{2}-1)$. Consider

$2y_{1}+3x_{2}+3y_{2}-12=3x_{2}+2(y_{1}+y_{2})+y_{2}-12.$

From Eq. (1) and $x_{2}\leq y_{2}-5$, we have

$2y_{1}+3x_{2}+3y_{2}-12\geq 3x_{2}+2(4n+5)+(x_{2}+5)-12=4x_{2}+8n+3.$

Since $n\geq 3$ and $x_{2}\geq 1$, we then get

$2y_{1}+3x_{2}+3y_{2}-12\geq 4x_{2}+8n+3\geq 6n+13>6n+12.$

We can conclude that

$y_{1}+3r_{2}\geq y_{1}+3\left(\frac{x_{2}+y_{2}-4}{2}\right)>3n+6.$

Thus, $y_{1}>9+3(n-r_{2}-1)$. So there are $n-r_{2}$ disjoint red copies of
$K_{3}$ using vertices from $U_{1}$.

From both cases, there are additional $n-r_{2}$ disjoint red copies of $K_{3}$
in $G[U_{1}]$. The last step is to show that there are also additional
$n-r_{2}$ vertices in $U_{2}$, which is $4x_{2}+y_{2}-2r_{2}\geq n-r_{2}$.
From $y_{2}-5\geq x_{2}$ and Eq. (3), we have

$4x_{2}+y_{2}-\frac{x_{2}+y_{2}-3}{2}=\frac{7x_{2}+y_{2}+3}{2}\geq
4x_{2}+4\geq n.$

Since
$r_{2}=\left\lfloor\frac{x_{2}+y_{2}-3}{2}\right\rfloor\leq\frac{x_{2}+y_{2}-3}{2}$,
we conclude that

$4x_{2}+y_{2}-2r_{2}\geq 4x_{2}+y_{2}-\frac{x_{2}+y_{2}-3}{2}-r_{2}\geq
n-r_{2}.$

This concludes that there is a red copy of $nK_{4}$ in $G$.

This finished the proof of the first case.

##  4\. Proof of the second case

Let $2n-1+\left\lfloor\frac{n}{4}\right\rfloor\leq k\leq 3n-3$. From Lemma 9,
we can combine $V_{1},V_{2},\ldots,V_{t}$ and $V^{\prime}$ into three
partitions, say $U_{1},U_{2}$ and $U_{3}$, where each $G[U_{i}]$ contains at
least $\left\lceil\frac{n}{4}\right\rceil$ disjoint blue copies of $K_{4}$. In
addition, we can partition them so that only one part contains more than $n-1$
disjoint blue copies of $K_{4}$. (If the first and the second parts contain
more than $n-1$ disjoint blue copies of $K_{4}$, we can keep repartitioning
the second part into two subparts and add the smaller part into the first part
until the second part is at most $n-1$. Note that the larger part is always at
least $\frac{n}{2}\geq\left\lceil\frac{n}{4}\right\rceil$.)

For $i\in\\{1,2,3\\}$, we let $x_{i}$ be the number of disjoint blue copies of
$K_{4}$ in $G[U_{i}]$ from $K$, $y_{i}$ be the number of vertices in
$G[U_{i}]$ not belong to those disjoint blue copies of $K_{4}$ from $K$. The
number of vertices not in any $K_{4}$ in $K$ is $\lvert
V(G-K)\rvert=13n-3-4k$. Since $2n-1+\left\lfloor\frac{n}{4}\right\rfloor\leq
k\leq 3n-3$, we have

$n+9\leq y_{1}+y_{2}+y_{3}\leq 5n+10-4\left\lfloor\dfrac{n}{4}\right\rfloor.$
(4)

The main goal is to construct a red copy of $nK_{4}$. Since we can divide the
graph $G$ into three subgraphs, $G[U_{1}],G[U_{2}]$ and $G[U_{3}]$ where edges
between these parts are red, we can construct a red copy of $K_{4}$ by choose
two vertices whose adjacent by a red edge from one subgraph and choose one
vertex each from the other two subgraphs.

Let $r_{i}$ be the size of a maximum matching in $G[U_{i}]$. The next two
lemmas show that we have a red matching of size $s_{1}+s_{2}+s_{3}=n$ in $G$,
which will be used to construct a red copy of $nK_{4}$. The proofs are
postponed to the end of the section.

######  Lemma 11.

$r_{1}+r_{2}+r_{3}\geq n$.

######  Lemma 12.

There exists $s_{i}\leq r_{i}$ for $i\in\\{1,2,3\\}$ such that
$s_{1}+s_{2}+s_{3}=n$ and $|U_{i}|\geq s_{i}+n$ for all $i$.

Let $M$ be a red matching obtained by choosing $s_{i}$ edges from a matching
of size $r_{i}$ in $G[U_{i}]$. We write

$M=\\{u_{11}v_{11},\ldots,u_{1s_{1}}v_{1s_{1}},u_{21}v_{21},\ldots,u_{2s_{2}}v_{2s_{2}},u_{31}v_{31},\ldots,u_{3s_{3}}v_{3s_{3}}\\}$

where $u_{ij},v_{ij}\in U_{i}$ for any $j$. From Lemma 12, we can choose
distinct vertices $w_{ij}$ in
$U_{i}\setminus\\{u_{i1},v_{i1},\dots,u_{is_{i}},v_{is_{i}}\\}$ for $1\leq
j\leq n-s_{i}$. Next, for $1\leq j\leq s_{1}$, the four vertices
$u_{1j},v_{1j},w_{2j}$ and $w_{3j}$ induces $s_{1}$ disjoint red copies of
$K_{4}$. Similarly, for $1\leq j\leq s_{2}$, the four vertices
$u_{2j},v_{2j},w_{1j}$ and $w_{3(s_{1}+j)}$ also induces $s_{2}$ disjoint red
copies of $K_{4}$. Lastly, for $1\leq j\leq s_{3}$, the four vertices
$u_{3j},v_{3j},w_{1(s_{2}+j)}$ and $w_{2(s_{1}+j)}$ induces another $s_{3}$
disjoint red copies of $K_{4}$. By Lemma 12, the construction is feasible.
Since $s_{1}+s_{2}+s_{3}=n$, there is a red copy of $nK_{4}$ in $G$.

###### Proof of Lemma 11.

If there is $i$ where $x_{i}\geq n-1+\left\lceil\frac{n}{4}\right\rceil$, then
$x_{i}>n-1$. The graph $G[U_{i}]$ can then be separated into two parts where
all edges between the two parts are red and the number of disjoint blue copies
of $K_{4}$ from $K$ in each part is at least
$\left\lceil\frac{n}{4}\right\rceil$. So the number of vertices in each part
is at least $4\left\lceil\frac{n}{4}\right\rceil$, hence $r_{i}\geq
4\left\lceil\frac{n}{4}\right\rceil\geq n$. In the rest of the proof, we can
then assume that $x_{i}<n-1+\left\lceil\frac{n}{4}\right\rceil$.

Consider the lower bound of $x_{1}+x_{2}+x_{3}+y_{1}+y_{2}+y_{3}$. The lowest
possible value occurs when the number of vertices in $K$ is the largest as
possible, i.e., $x_{1}+x_{2}+x_{3}=3n-3$. So, $y_{1}+y_{2}+y_{3}=n+9$. We have

$x_{1}+x_{2}+x_{3}+y_{1}+y_{2}+y_{3}\geq 4n+6.$ (5)

Since $x_{1}+x_{2}+x_{3}=k\leq 3n-3$, all $x_{1},x_{2},x_{3}$ cannot be
greater than $n-1$. We then separate the proof into 3 cases, according to the
number of $x_{i}$ that is greater than $n-1$. We also have
$y_{1}+y_{2}+y_{3}=13n-3-4k\geq n+9>9$. Therefore, $y_{1},y_{2}$ and $y_{3}$
cannot simultaneously be less than four.

Case 1:

$x_{1},x_{2},x_{3}\leq n-1$.

Without loss of generality, we assume that $y_{3}\leq y_{2}\leq y_{1}$. We
consider 3 sub-cases.

Case 1.1:

$y_{3}\leq y_{2}<4\leq y_{1}$.

From Eq. (5), we have

$x_{1}+y_{1}\geq 2n+2.$

  * •:

If $x_{1}+y_{1}\geq 2n+3$, because $x_{1}\leq n-1$, so $y_{1}\geq n+4\geq
x_{1}+5$. By Lemma 5,
$r_{1}\geq\left\lfloor\frac{x_{1}+y_{1}-3}{2}\right\rfloor\geq\left\lfloor\frac{2n}{2}\right\rfloor=n$.

  * •:

If $x_{1}+y_{1}=2n+2$, then this equality happens only when $x_{1}=n-1$. Thus,
$y_{1}=n+3\leq n-1+4=x_{1}+4$. Hence, by Lemma 5, we have $r_{1}\geq
y_{1}-3=n$.

Case 1.2:

$y_{3}<4\leq y_{2}\leq y_{1}$.

From Eq. (5), we get

$x_{1}+x_{2}+y_{1}+y_{2}\geq(4n+6)-(n-1)-3=3n+4$ (6)

To apply Lemma 5 to $r_{1}$ and $r_{2}$, there are 4 possibilities. In each
case, we use Eq. (6) and the inequalities $x_{1},x_{2}\leq n-1$ when needed.

  * •:

Let $x_{1}\geq y_{1}-4$ and $x_{2}\geq y_{2}-4$. Then

$r_{1}+r_{2}\geq y_{1}+y_{2}-6\geq n.$

  * •:

Let $x_{1}\leq y_{1}-5$ and $x_{2}\leq y_{2}-5$. Then

$\begin{split}r_{1}+r_{2}&\geq\left\lfloor\dfrac{x_{1}+y_{1}-3}{2}\right\rfloor+\left\lfloor\dfrac{x_{2}+y_{2}-3}{2}\right\rfloor\\\
&\geq\frac{x_{1}+y_{1}-4}{2}+\frac{x_{2}+y_{2}-4}{2}\\\
&\geq\frac{3n-4}{2}.\end{split}$

We know that $\frac{3n-4}{2}\geq n$ when $n\geq 4$. For $n=3$, we have
$r_{1}+r_{2}\geq\frac{5}{2}$. So $r_{1}+r_{2}\geq 3=n$.

  * •:

Let $x_{1}\geq y_{1}-4$ and $x_{2}\leq y_{2}-5$. (The case when $x_{1}\leq
y_{1}-5$ and $x_{2}\geq y_{2}-4$ can be treated similarly.) Then

$\begin{split}r_{1}+r_{2}&=y_{1}-3+\left\lfloor\dfrac{x_{2}+y_{2}-3}{2}\right\rfloor\\\
&\geq y_{1}-3+\frac{x_{2}+y_{2}-4}{2}\\\
&=\frac{x_{1}+y_{1}+x_{2}+y_{2}-(x_{1}-y_{1})-10}{2}\\\ &\geq
n-\frac{1}{2}.\end{split}$

The last inequality follows from $x_{1}\leq n-1$ and $y_{1}\geq 4$. Since
$r_{1}+r_{2}$ is an integer, we have $r_{1}+r_{2}\geq n$.

Case 1.3:

$4\leq y_{3}\leq y_{2}\leq y_{1}$.

We will apply Lemma 5 to $r_{1},r_{2}$ and $r_{3}$, which have 8
possibilities. They can be separated into 4 groups, by the number of $i$ where
$x_{i}\geq y_{i}-4$, as follows.

  * •:

There is no $i$ where $x_{i}\geq y_{i}-4$. Let $x_{1}\leq y_{1}-5$, $x_{2}\leq
y_{2}-5$ and $x_{3}\leq y_{3}-5$. Then

$\begin{split}r_{1}+r_{2}+r_{3}&=\left\lfloor\dfrac{x_{1}+y_{1}-3}{2}\right\rfloor+\left\lfloor\dfrac{x_{2}+y_{2}-3}{2}\right\rfloor+\left\lfloor\dfrac{x_{3}+y_{3}-3}{2}\right\rfloor\\\
&\geq\frac{x_{1}+y_{1}-4}{2}+\frac{x_{2}+y_{2}-4}{2}+\frac{x_{3}+y_{3}-4}{2}\\\
&=\frac{x_{1}+y_{1}+x_{2}+y_{2}+x_{3}+y_{3}-12}{2}\\\ &\geq 2n-3\geq
n.\end{split}$

  * •:

There is exactly one $i$ where $x_{i}\geq y_{i}-4$. Let $x_{1}\leq y_{1}-5$
and $x_{2}\leq y_{2}-5$, but $x_{3}\geq y_{3}-4$. Then

$\begin{split}r_{1}+r_{2}+r_{3}&=\left\lfloor\dfrac{x_{1}+y_{1}-3}{2}\right\rfloor+\left\lfloor\dfrac{x_{2}+y_{2}-3}{2}\right\rfloor+y_{3}-3\\\
&\geq\frac{x_{1}+y_{1}-4}{2}+\frac{x_{2}+y_{2}-4}{2}+y_{3}-3\\\
&\geq\frac{x_{1}+y_{1}+x_{2}+y_{2}+x_{3}+2y_{3}-14}{2}\\\
&\geq\frac{x_{1}+x_{2}+x_{3}+y_{1}+y_{2}+y_{3}-(x_{3}-y_{3})-14}{2}\\\
&\geq\frac{4n-8-(x_{3}-y_{3})}{2}\end{split}$

The last inequality follows from Eq. (5). Since $y_{3}\geq 4$ and $x_{3}\leq
n-1$, we have $x_{3}-y_{3}\leq n-5$. Hence,
$r_{1}+r_{2}+r_{3}\geq\frac{3n-3}{2}\geq n$.

  * •:

There are exactly two $i$ where $x_{i}\geq y_{i}-4$. Let $x_{1}\leq y_{1}-5$,
but $x_{2}\geq y_{2}-4$ and $x_{3}\geq y_{3}-4$. The other two cases can be
treated in the same manner. Then

$\begin{split}r_{1}+r_{2}+r_{3}&\geq\left\lfloor\dfrac{x_{1}+y_{1}-3}{2}\right\rfloor+y_{2}-3+y_{3}-3\\\
&\geq\frac{x_{1}+y_{1}-4}{2}+y_{2}+y_{3}-6\\\
&\geq\frac{x_{1}+y_{1}+2y_{2}+2y_{3}-16}{2}\\\
&\geq\frac{x_{1}+x_{2}+x_{3}+y_{1}+y_{2}+y_{3}-(x_{2}-y_{2})-(x_{3}-y_{3})-16}{2}\\\
&\geq\frac{4n-10-(x_{2}-y_{2})-(x_{3}-y_{3})}{2}.\end{split}$

Since $x_{2}-y_{2}\leq n-5$ and $x_{3}-y_{3}\leq n-5$, we get

$r_{1}+r_{2}+r_{3}\geq\frac{4n-10-2(n-5)}{2}=n.$

  * •:

Let $x_{1}\geq y_{1}-4$, $x_{2}\geq y_{2}-4$ and $x_{3}\geq y_{3}-4$. From Eq.
(5) and $x_{1}+x_{2}+x_{3}\leq 3n-3$, we then get

$r_{1}+r_{2}+r_{3}\geq y_{1}+y_{2}+y_{3}-9\geq n.$

Case 2:

Exactly one of $x_{1},x_{2},x_{3}$ is more than $n-1$.

Suppose without loss of generality that $x_{1}>n-1$ and $x_{2},x_{3}\leq n-1$.
Let $x_{1}=n-1+m$ for some $1\leq m<\left\lceil\frac{n}{4}\right\rceil$. Thus,
we can partition $U_{1}$ into two parts where each part has at most $n-1$
disjoint blue copies of $K_{4}$ and all edges between these two parts are red.
Then the smaller part contains at least $m$ disjoint blue copies of $K_{4}$,
and so does the larger part. Hence, there is a red matching $M$ of size $4m$
(between the two sets of $m$ disjoint blue copies of $K_{4}$) in $G[U_{1}]$.

Case 2.1:

$y_{1}<4$.

With $x_{1}=n-1+m$ and $y_{1}\leq 3$, Eq. (5) gives

$x_{2}+y_{2}+x_{3}+y_{3}\geq 3n+4-m.$ (7)

If either $y_{2}$ or $y_{3}$ is less than four, then we can suppose that
$y_{2}<4$. By Eq. (4), $y_{3}\geq n+3$. Since $x_{3}\leq n-1$, the condition
$x_{3}\geq y_{3}-4$ occurs only when $x_{3}=n-1$ and $y_{3}=n+3$. Then by
Lemma 5, $r_{3}\geq y_{3}-3=n$.

When $x_{3}\leq y_{3}-5$, Lemma 5 gives

$r_{3}\geq\left\lfloor\frac{x_{3}+y_{3}-3}{2}\right\rfloor\geq\frac{x_{3}+y_{3}-4}{2}.$

Since $x_{2}\leq n-1$ and $y_{2}\leq 3$, Eq. (7) gives

$x_{3}+y_{3}\geq 2n+2-m.$

Since $r_{1}\geq 4m$ with $m\geq 1$, we have

$r_{1}+r_{3}\geq 4m+\frac{2n+2-m-4}{2}=\frac{2n-2+7m}{2}>n.$

Hence, we assume $y_{2}\geq 4$ and $y_{3}\geq 4$.

To apply Lemma 5 to $r_{2}$ and $r_{3}$, we consider 4 possibilities. In each
case, we use Eq. (7) and the inequalities $x_{2}\leq n-1$ and $x_{3}\leq n-1$
when necessary.

  * •:

If $x_{2}\geq y_{2}-4$ and $x_{3}\geq y_{3}-4$, we get

$\begin{split}r_{2}+r_{3}&\geq y_{2}+y_{3}-6\\\ &\geq 3n+4-m-2(n-1)-6\\\
&=n-m.\end{split}$

So $r_{1}+r_{2}+r_{3}\geq 4m+n-m\geq n$.

  * •:

If $x_{2}\leq y_{2}-5$ and $x_{3}\leq y_{3}-5$, we get

$\begin{split}r_{2}+r_{3}&\geq\left\lfloor\dfrac{x_{2}+y_{2}-3}{2}\right\rfloor+\left\lfloor\dfrac{x_{3}+y_{3}-3}{2}\right\rfloor\\\
&\geq\frac{x_{2}+y_{2}-4}{2}+\frac{x_{3}+y_{3}-4}{2}\\\
&\geq\frac{x_{2}+y_{2}+x_{3}+y_{3}-8}{2}\\\ &\geq\frac{3n-4-m}{2}.\end{split}$

Since $r_{1}\geq 4m$ and $m\geq 1$, we have

$r_{1}+r_{2}+r_{3}\geq
4m+\frac{3n-4-m}{2}\geq\frac{3n-4+7m}{2}\geq\frac{3n+3}{2}\geq n.$

  * •:

If $x_{2}\geq y_{2}-4$ and $x_{3}\leq y_{3}-5$, we get

$\begin{split}r_{2}+r_{3}&\geq
y_{2}-3+\left\lfloor\dfrac{x_{3}+y_{3}-3}{2}\right\rfloor\\\ &\geq
y_{2}-3+\frac{x_{3}+y_{3}-4}{2}\\\
&=\frac{x_{2}+y_{2}+x_{3}+y_{3}-(x_{2}-y_{2})-10}{2}.\end{split}$

With $x_{2}\leq n-1$, $y_{2}\geq 4$ and $m\geq 1$, we have

$\begin{split}r_{2}+r_{3}&\geq\frac{x_{2}+y_{2}+x_{3}+y_{3}-(x_{2}-y_{2})-10}{2}\\\
&\geq\frac{3n+4-m-(n-5)-10}{2}\\\ &\geq n-\frac{m+1}{2}.\\\ \end{split}$

Since $r_{1}\geq 4m$ and $m\geq 1$, we obtain

$r_{1}+r_{2}+r_{3}\geq 4m+n-\frac{m+1}{2}\geq n+\frac{7m-1}{4}\geq n.$

  * •:

If $x_{2}\leq y_{3}-5$ and $x_{3}\geq y_{2}-4$, we can treat this in the same
manner as in the previous case.

Case 2.2:

$y_{1}\geq 4$.

Apart from $2m$ disjoint blue copies of $K_{4}$ which gives a red matching of
size $4m$ in $G[U_{1}]$, there are $x_{1}^{\prime}=x_{1}-2m=n-m-1$ disjoint
blue copies of $K_{4}$ ramained in $G[U_{1}]$. Let $r_{1}^{\prime}=r_{1}-4m$.
We will apply Lemma 5 using $x_{1}^{\prime}$ instead of $x_{1}$, and get a
lower bound on $r_{1}^{\prime}$.

Consider the following situations based on the values of $y_{2}$ and $y_{3}$.

  1. (1):

Exactly one of $y_{2}$ and $y_{3}$ is less than $4$. We assume without loss of
generality that $y_{2}\geq 4$ but $y_{3}<4$. Eq. (4) gives

$y_{1}+y_{2}\geq n+6.$

Since $x_{3}\leq n-1$, Eq. (5) also gives

$x_{1}+x_{2}+y_{1}+y_{2}\geq 3n+4.$

    1. (a):

Suppose that $x_{1}^{\prime}\geq y_{1}-4$. By Lemma 5, $r_{1}^{\prime}\geq
y_{1}-3$. So, $r_{1}=r_{1}^{\prime}+4m\geq y_{1}-3+4m.$

If $x_{2}\geq y_{2}-4$, then $r_{2}\geq y_{2}-3$. Hence,

$r_{1}+r_{2}\geq y_{1}+y_{2}+4m-6\geq n+4m\geq n.$

If $x_{2}\leq y_{2}-5$, then
$r_{2}\geq\left\lfloor\frac{x_{2}+y_{2}-3}{2}\right\rfloor\geq\frac{x_{2}+y_{2}-4}{2}$.
Hence,

$\begin{split}r_{1}+r_{2}&\geq y_{1}-3+4m+\frac{x_{2}+y_{2}-4}{2}\\\
&\geq\frac{x_{2}+2y_{1}+y_{2}+8m-10}{2}\\\ \end{split}$ (8)

From $x_{1}+x_{2}+y_{1}+y_{2}\geq 3n+4$, $x_{1}=n-1+m$ and $y_{1}\geq 4$, we
obtain

$r_{1}+r_{2}\geq\frac{2n+7m-1}{2}>n.$

    2. (b):

Let $x_{1}^{\prime}\leq y_{1}-5$. By Lemma 5,
$r_{1}^{\prime}\geq\left\lfloor\frac{x_{1}^{\prime}+y_{1}-3}{2}\right\rfloor$.
So $r_{1}=r_{1}^{\prime}+4m\geq\frac{x_{1}^{\prime}+y_{1}-4}{2}+4m$.

If $x_{2}\geq y_{2}-4$, then $r_{2}\geq y_{2}-3$. Hence,

$\begin{split}r_{1}+r_{2}&\geq\frac{x_{1}^{\prime}+y_{1}-4}{2}+4m+y_{2}-3\\\
&\geq\frac{x_{1}^{\prime}+y_{1}+2y_{2}+8m-10}{2}\\\
&=\frac{n-m-1+y_{1}+2y_{2}+8m-10}{2}\\\
&=\frac{y_{1}+2y_{2}+n+7m-11}{2}.\end{split}$ (9)

Since $y_{1}+y_{2}\geq n+6$ and $y_{2}\geq 4$, we get $y_{1}+2y_{2}\geq n+10$.
Thus,

$r_{1}+r_{2}\geq\frac{2n+7m-1}{2}\geq n.$

If $x_{2}\leq y_{2}-5$, then
$r_{2}\geq\left\lfloor\frac{x_{2}+y_{2}-3}{2}\right\rfloor\geq\frac{x_{2}+y_{2}-4}{2}$.
Hence,

$\begin{split}r_{1}+r_{2}&\geq
4m+\frac{x_{1}^{\prime}+y_{1}-4}{2}+\frac{x_{2}+y_{2}-4}{2}\\\
&\geq\frac{8m+x_{1}^{\prime}+y_{1}+x_{2}+y_{2}-8}{2}\\\
&\geq\frac{7m+n-9+y_{1}+x_{2}+y_{2}}{2}.\end{split}$

Since $x_{1}+x_{2}+y_{1}+y_{2}\geq 3n+4$ and $x_{1}=n+m-1$, we get
$y_{1}+x_{2}+y_{2}\geq 2n+5-m$. Thus,

$r_{1}+r_{2}\geq\frac{3n+6m-4}{2}>n.$

  2. (2):

Both $y_{2}$ and $y_{3}$ are less than four. From $y_{1}+y_{2}+y_{3}\geq n+9$,
we get $y_{1}\geq n+3$.

If $x_{1}^{\prime}\geq y_{1}-4$, then $r_{1}^{\prime}\geq y_{1}-3\geq n$.

If $x_{1}^{\prime}\leq y_{1}-5$, then

$r_{1}^{\prime}\geq\left\lfloor\frac{x_{1}^{\prime}+y_{1}-3}{2}\right\rfloor\geq\left\lfloor\frac{2x_{1}^{\prime}+2}{2}\right\rfloor=x_{1}^{\prime}+1=n-m.$

Hence,

$r_{1}=4m+r_{1}^{\prime}\geq 3m+n>n.$

  3. (3):

Let both $y_{2}$ and $y_{3}$ is at least four. ecall that
$x_{1}^{\prime}=n-m-1$ and $r_{1}=r_{1}^{\prime}+4m$. Similar to Eq. (5), we
have

$x_{1}^{\prime}+x_{2}+x_{3}+y_{1}+y_{2}+y_{3}\geq 4n-2m+6.$

From $x_{1}+x_{2}+x_{3}\leq 3n-3$, we also get

$y_{1}+y_{2}+y_{3}\geq n+9.$

We apply Lemma 5 to $r_{1}^{\prime}$, $r_{2}$ and $r_{3}$ in the same manner
as in Case 1.Case 1.3: . Note that the inequality $x_{1}^{\prime}-y_{1}\leq
n-m-5$ is used when $x_{1}^{\prime}\geq y_{1}-4$, while $x_{i}-y_{i}\leq n-5$
is used when $x_{i}\geq y_{i}-4$ when $i\neq 1$.

For simplicity of the following inequality, we let $A$ be the set of all $i$
such that $x_{i}\geq y_{i}-4$ (or $x_{i}^{\prime}\geq y_{i}-4$ when $i=1$). We
then have

$\begin{split}r_{1}^{\prime}+r_{2}+r_{3}\geq\begin{cases}2n-m-3,&A=\emptyset,\\\
\frac{3n-m-3}{2},&A=\\{1\\},\\\ \frac{3n-2m-3}{2},&A=\\{2\\}\text{ or
}\\{3\\},\\\ n-m,&A=\\{2,3\\},\\\ n-\frac{m}{2},&A=\\{1,2\\}\text{ or
}\\{1,3\\},\\\ n,&A=\\{1,2,3\\}.\end{cases}\end{split}$

Hence,

$r_{1}+r_{2}+r_{3}\geq r_{1}^{\prime}+r_{2}+r_{3}+4m\geq n.$

From the two cases, we can conclude that $r_{1}+r_{2}+r_{3}\geq n$. ∎

###### Proof of Lemma 12.

From the proof of Lemma 11, there are many situations from which the lower
bounds on $r_{i}$ are obtained. In each situation, we choose $s_{i}=0$ when
the obviouse bound $r_{i}\geq 0$ is obtained, and choose $s_{i}\leq L_{n}$
when the lower bound $r_{i}\geq L_{n}$ is obtained (either from Lemma 5 or a
red matching construction using a blue copy of $K_{4}$) in such a way that
$s_{1}+s_{2}+s_{3}$ holds. We now prove that $|U_{i}|-s_{i}\geq n$.

  1. (1)

$x_{i}\leq n-1$. The lower bound on $r_{i}$ is obtained from Lemma 5.

     * •

If $y_{i}\leq 3$, then $r_{i}\geq 0$. Then, $|U_{i}|-s_{i}=4x_{i}+y_{i}$.

     * •

If $x_{i}\geq y_{i}-4$ and $y_{i}\geq 4$, then $r_{i}\geq y_{i}-3$. Then,

$|U_{i}|-s_{i}\geq 4x_{i}+y_{i}-(y_{i}-3)=4x_{i}+3.$

     * •

If $x_{i}\leq y_{i}-5$ and $y_{i}\geq 4$, then
$r_{i}\geq\left\lfloor\frac{x_{i}+y_{i}-3}{2}\right\rfloor$. With $y_{i}\geq
x_{i}+5$, we get

$\begin{split}|U_{i}|-s_{i}&\geq
4x_{i}+y_{i}-\left\lfloor\frac{x_{i}+y_{i}-3}{2}\right\rfloor\\\ &\geq
4x_{i}+y_{i}-\frac{x_{i}+y_{i}-2}{2}\\\ &=\frac{7x_{i}+y_{i}+2}{2}\\\
&\geq\frac{8x_{i}+7}{2}.\end{split}$

From the three cases, we can conclude that $|U_{i}|-s_{i}\geq 4x_{i}\geq n$.

  2. (2)

$n-1<x_{i}<n-1+\lceil\frac{n}{4}\rceil$ and $y_{i}\geq 4$. We write
$x_{i}=n+m-1$ where $m<\lceil\frac{n}{4}\rceil$. Also,
$x_{i}^{\prime}=x_{i}-2m=n-m-1$ and $r_{i}\geq r_{i}^{\prime}+4m$ where the
lower bound on $r_{i}^{\prime}$ is obtained from Lemma 5.

     * •

If $x_{i}\geq y_{i}-4$, then

$|U_{i}|-s_{i}\geq 4x_{i}+y_{i}-4m-(y_{i}-3)=4n-1\geq n.$

     * •

If $x_{i}\leq y_{i}-5$, then

$\begin{split}|U_{i}|-s_{i}&\geq
4x_{i}+y_{i}-4m-\left\lfloor\frac{x^{\prime}_{i}+y_{i}-3}{2}\right\rfloor\\\
&\geq 4x_{i}+y_{i}-4m-\frac{x^{\prime}_{i}+y_{i}-2}{2}\\\
&=\frac{8x_{i}-x^{\prime}_{i}+y_{i}-8m+2}{2}\\\ &\geq\frac{7n+m-1}{2}\\\ &\geq
n.\end{split}$

  3. (3)

$n-1<x_{i}<n-1+\lceil\frac{n}{4}\rceil$ and $y_{i}\leq 3$. Similarly, we write
$x_{i}=n+m-1$ where $m<\lceil\frac{n}{4}\rceil$. The lower bound $r_{i}\geq
4m$ is obtained. Then,

$|U_{i}|-s_{i}\geq 4x_{i}+y_{i}-4m\geq 4n+y_{i}-4\geq n.$

  4. (4)

$x_{i}\geq n-1+\lceil\frac{n}{4}\rceil$. We get $r_{i}\geq n$. Hence,

$|U_{i}|-s_{i}\geq 4x_{i}+y_{i}-n\geq 4n+y_{i}-4\geq n.$

From all four cases, we can conclude that $|U_{i}|\geq s_{i}+n$. ∎

##  5\. Proof of the third case

Let $3n-2\leq k\leq 3n-4+\left\lceil\frac{n}{4}\right\rceil$. We have that
$n\geq 5$. With the same setup as in Section 4, we let $U_{1},U_{2}$ and
$U_{3}$ be the partition of the vertices of $G$ where each $G[U_{i}]$ contains
at least $\left\lceil\frac{n}{4}\right\rceil$ disjoint blue copies of $K_{4}$
from $K$. In addition, at most one $G[U_{i}]$, assumed to be $G[U_{1}]$,
contains more than $n-1$ disjoint blue copies of $K_{4}$.

Let $x_{i}$ be the number of disjoint blue copies of $K_{4}$ in $G[U_{i}]$
from $K$, $y_{i}$ be the number of vertices in $G[U_{i}]$ not belong to those
disjoint blue copies of $K_{4}$ from $K$. Let $r_{i}$ be the size of the
maximum red matching in $G[U_{i}]$.

Since $k\geq 3n-2$, at least one of $x_{1},x_{2}$ and $x_{3}$ is larger than
$n-1$. Hence, $x_{1}>n-1$ while $x_{2}\leq n-1$ and $x_{3}\leq n-1$.

Since $3n-2\leq k\leq 3n-4+\left\lceil\frac{n}{4}\right\rceil$, we can write

$x_{1}+x_{2}+x_{3}=k=3n+p-3$ (10)

for some $1\leq p<\left\lceil\frac{n}{4}\right\rceil$. Thus,

$y_{1}+y_{2}+y_{3}=|V(G)|-4k=13n-3-4k=n-4p+9.$ (11)

We also have

$x_{1}+x_{2}+x_{3}+y_{1}+y_{2}+y_{3}=4n-3p+6.$ (12)

Lastly, Eq. (10) gives $x_{1}\geq n+p-1$. So, we let

$x_{1}=n+m-1$ (13)

for some $m\geq p$.

Similar to Section 4, we can show that $r_{1}+r_{2}+r_{3}\geq n$.

######  Lemma 13.

$r_{1}+r_{2}+r_{3}\geq n$.

Using the same method as in Lemma 12, we can show that there is $s_{i}\leq
r_{i}$ such that $s_{1}+s_{2}+s_{3}=n$ and $|U_{i}|\geq s_{i}+n$ for all $i$.
In exactly the same way as in Section 4, we can then construct a red copy of
$nK_{4}$ from a red matching of size $n$.

###### Proof of Lemma 13.

If $x_{1}\geq n-1+\left\lceil\frac{n}{4}\right\rceil$, we can use Lemma 8 to
partition the blue connected components in $G[U_{1}]$ into two parts, where
each part has at least $\left\lceil\frac{n}{4}\right\rceil$ disjoint blue
copies of $K_{4}$. We then construct a red matching of size
$4\left\lceil\frac{n}{4}\right\rceil\geq n$ in $G[U_{1}]$. Thus, $r_{1}\geq
n$.

We now assume that $n-1<x_{1}<n-1+\left\lceil\frac{n}{4}\right\rceil$. This
implies that $m<\left\lceil\frac{n}{4}\right\rceil$. Hence,

$1\leq p\leq m<\left\lceil\frac{n}{4}\right\rceil.$ (14)

Similarly, we can apply Lemma 8 to Eq. (13) and get a red matching of size
$4m$ in $G[U_{1}]$. We let

$x_{1}^{\prime}=x_{1}-2m=n-m-1.$

Then $G[U_{1}]-M$ contains a blue copy of $x_{1}^{\prime}K_{4}$ from $K$.

In order to apply Lemma 5, we need to consider different cases depending on
whether $y_{i}\geq 4$ and whether $x_{i}\geq y_{i}-4$. We note that for $i=1$,
we consider $G[U_{1}]-M$ instead of $G[U_{1}]$. Hence, we use $x_{1}^{\prime}$
instead of $x_{1}$ together with the same $y_{1}$, and let $r_{1}^{\prime}$ be
the size of the maximum red matching in $G[U_{1}]-M$. So

$r_{1}\geq r_{1}^{\prime}+4m.$

Case 1:

Both $y_{2}$ and $y_{3}$ are less than four.

From Eq. (11), we have

$y_{1}\geq n-4p+3.$

This also implies that $y_{1}\geq 4$.

Case 1.1:

$x_{1}^{\prime}\geq y_{1}-4$. We have

$r_{1}\geq r_{1}^{\prime}+4m\geq y_{1}-3+4m\geq n.$

Case 1.2:

$x_{1}^{\prime}\leq y_{1}-5$. We have

$\begin{split}r_{1}^{\prime}&\geq\left\lfloor\frac{x_{1}^{\prime}+y_{1}-3}{2}\right\rfloor\\\
&\geq\frac{x_{1}^{\prime}+y_{1}-4}{2}\\\ &\geq\frac{(n-m-1)+(n-4p+3)-4}{2}\\\
&=\frac{2n-4p-m-2}{2}.\end{split}$

Hence,

$r_{1}\geq r_{1}^{\prime}+4m\geq\frac{2n+7m-4p-2}{2}\geq n.$

Case 2:

Exactly of one $y_{2}$ and $y_{3}$ is less than four.

We may assume that $y_{2}\geq 4$ and $y_{3}<4$.

Case 2.1:

$y_{1}<4$.

From Eq. (11), we have

$y_{2}\geq n-4p+3.$

Consider the following situations.

  * •:

$x_{2}\geq y_{2}-4$. We have $r_{2}\geq y_{2}-3\geq n-4p$. Since $r_{1}\geq
r_{1}^{\prime}+4m\geq 4m$, we then get

$r_{1}+r_{2}\geq n-4p+4m\geq n.$

  * •:

$x_{2}\leq y_{2}-5$. We get
$r_{2}\geq\left\lfloor\frac{x_{2}+y_{2}-3}{2}\right\rfloor\geq\frac{x_{2}+y_{2}-4}{2}$.
Since $x_{1}=n+m-1$ and $x_{3}\leq n-1$, Eq. (12) gives

$\begin{split}x_{2}+y_{2}&=4n-3p+6-(x_{1}+x_{3}+y_{1}+y_{3})\\\ &\geq
2n-3p-m+2.\end{split}$

Hence,

$\begin{split}r_{1}+r_{2}&\geq 4m+\frac{2n-3p-m-2}{2}\\\
&\geq\frac{2n-3p+7m-2}{2}\\\ &\geq n\end{split}$

Case 2.2:

$y_{1}\geq 4$.

  * •:

$x_{1}^{\prime}\leq y_{1}-5$. Then,

$r_{1}^{\prime}\geq\left\lfloor\frac{x_{1}^{\prime}+y_{1}-3}{2}\right\rfloor\geq\left\lfloor\frac{2x_{1}^{\prime}+2}{2}\right\rfloor=x_{1}^{\prime}+1=n-m.$

Hence,

$r_{1}\geq r_{1}^{\prime}+4m\geq n.$

  * •:

$x_{1}^{\prime}\geq y_{1}-4$ and $x_{2}\geq y_{2}-4$. From $y_{3}\leq 3$, Eq.
(11) gives $y_{1}+y_{2}\geq n-4p+6$. From Lemma 5, we can conclude that

$r_{1}+r_{2}\geq r_{1}^{\prime}+r_{2}+4m\geq y_{1}+y_{2}-6+4m\geq n.$

  * •:

$x_{1}^{\prime}\geq y_{1}-4$ and $x_{2}\leq y_{2}-5$. Lemma 5 gives

$\begin{split}r_{1}+r_{2}&\geq
y_{1}-3+4m+\left\lfloor\dfrac{x_{2}+y_{2}-3}{2}\right\rfloor\\\ &\geq
y_{1}-3+4m+\frac{x_{2}+y_{2}-4}{2}\\\ &=\frac{x_{2}+2y_{1}+y_{2}+8m-10}{2}\\\
&=\frac{x_{1}+x_{2}+y_{1}+y_{2}+(y_{1}-x_{1})+8m-10}{2}.\end{split}$ (15)

Since $x_{3}\leq n-1$ and $y_{3}\leq 3$, Eq. (12) give

$x_{1}+x_{2}+y_{1}+y_{2}\geq 3n-3p+4.$

Using $x_{1}=n+m-1$ and $y_{1}\geq 4$, we then get $y_{1}-x_{1}\geq 5-n-m$.
Hence,

$\begin{split}r_{1}+r_{2}&\geq\frac{(3n-3p+4)+(5-n-m)+8m-10}{2}\\\
&=\frac{2n-3p+7m-1}{2}\\\ &\geq n.\end{split}$

Case 3:

Both $y_{2}$ and $y_{3}$ are at least four.

Case 3.1:

$y_{1}\leq 3$. From Eq. (11), we have

$y_{2}+y_{3}\geq n-4p+6.$

From Eq. (12), we also have

$x_{2}+x_{3}+y_{2}+y_{3}\geq 4n-3p+6-(n+m-1)-3=3n-3p-m+4.$

We use the two inequalities above together with Lemma 5 in the following
situations.

  * •:

$x_{2}\geq y_{2}-4$ and $x_{3}\geq y_{3}-4$. Then

$r_{1}+r_{2}+r_{3}\geq 4m+y_{2}+y_{3}-6\geq n.$

  * •:

$x_{2}\leq y_{2}-5$ and $x_{3}\leq y_{3}-5$. We have

$\begin{split}r_{1}+r_{2}+r_{3}&\geq
4m+\left\lfloor\dfrac{x_{2}+y_{2}-3}{2}\right\rfloor+\left\lfloor\dfrac{x_{3}+y_{3}-3}{2}\right\rfloor\\\
&\geq 4p+\frac{x_{2}+y_{2}-4}{2}+\frac{x_{3}+y_{3}-4}{2}\\\
&\geq\frac{3n-3p+7m-4}{2}\\\ &\geq n.\end{split}$

  * •:

$x_{2}\geq y_{2}-4$ and $x_{3}\leq y_{3}-5$. (Similarly, $x_{2}\leq y_{2}-5$
and $x_{3}\geq y_{3}-4$.) We get

$\begin{split}r_{1}+r_{2}+r_{3}&\geq
4m+y_{2}-3+\left\lfloor\dfrac{x_{3}+y_{3}-3}{2}\right\rfloor\\\ &\geq
4m+y_{2}-3+\frac{x_{3}+y_{3}-4}{2}\\\ &=\frac{8m+2y_{2}+x_{3}+y_{3}-10}{2}\\\
&=\frac{x_{2}+y_{2}+x_{3}+y_{3}+(y_{2}-x_{2})+8m-10}{2}.\end{split}$

Since $y_{2}\geq 4$ and $x_{2}\leq n-1$, we have $y_{2}-x_{2}\geq 5-n$. Hence,

$\begin{split}r_{1}+r_{2}+r_{3}&\geq\frac{4n-3p+6+5-n+8m-10}{2}\\\
&=\frac{3n-3p+8m+1}{2}\\\ &\geq n.\end{split}$

Case 3.2:

$y_{1}\geq 4$.

If $x_{1}^{\prime}\leq y_{1}-5$, we have

$r_{1}^{\prime}\geq\left\lfloor\frac{x_{1}^{\prime}+y_{1}-3}{2}\right\rfloor\geq\left\lfloor\frac{2x_{1}^{\prime}+2}{2}\right\rfloor=x_{1}^{\prime}+1=n-m.$

Hence, $r_{1}\geq r_{1}^{\prime}+4m\geq n$.

So. we will assume that $x_{1}^{\prime}\geq y_{1}-4$. Lemma 5 then gives

$r_{1}\geq r_{1}^{\prime}+4m\geq y_{1}+4m-3.$

To apply Lemma 5 to $r_{2}$ and $r_{3}$, we consider the following situations.

  * •:

$x_{2}\geq y_{2}-4$ and $x_{3}\geq y_{3}-4$. We have

$r_{1}+r_{2}+r_{3}\geq y_{1}+y_{2}+y_{3}-9+4m=n-4p+4m\geq n.$

  * •:

$x_{2}\leq y_{2}-5$ and $x_{3}\leq y_{3}-5$. Then

$\begin{split}r_{1}+r_{2}+r_{3}&\geq
y_{1}-3+4m+\left\lfloor\dfrac{x_{2}+y_{2}-3}{2}\right\rfloor+\left\lfloor\dfrac{x_{3}+y_{3}-3}{2}\right\rfloor\\\
&\geq y_{1}-3+4m+\frac{x_{2}+y_{2}-4}{2}+\frac{x_{3}+y_{3}-4}{2}\\\
&=\frac{2y_{1}+x_{2}+x_{3}+y_{2}+y_{3}+8m-14}{2}\\\
&=\frac{x_{1}+x_{2}+x_{3}+y_{1}+y_{2}+y_{3}+(y_{1}-x_{1})+8m-14}{2}.\end{split}$

Since $x_{1}=n+m-1$ and $y_{1}\geq 4$, Eq. (12) gives

$r_{1}+r_{2}+r_{3}\geq\frac{3n-3p+7m-3}{2}\geq n.$

  * •:

$x_{2}\geq y_{2}-4$ and $x_{3}\leq y_{3}-5$. Consider

$\begin{split}r_{1}+r_{2}+r_{3}&\geq
y_{1}-3+4m+y_{2}-3+\left\lfloor\dfrac{x_{3}+y_{3}-3}{2}\right\rfloor\\\ &\geq
y_{1}+y_{2}+4m-6+\frac{x_{3}+y_{3}-4}{2}\\\
&=\frac{x_{3}+2y_{1}+2y_{2}+y_{3}+8m-16}{2}.\end{split}$

From Eq. (12), we have

$r_{1}+r_{2}+r_{3}\geq\frac{2n-3p+7m}{2}\geq n.$

From all three cases, we conclude that $r_{1}+r_{2}+r_{3}\geq n$. ∎

##  6\. Proof of the fourth case

Let $k\geq 3n-3+\left\lceil\frac{n}{4}\right\rceil$. From Lemma 10, we can
combine $V_{1},V_{2},\ldots,V_{t}$ and $V^{\prime}$ into four parts, say
$U_{1},U_{2},U_{3}$ and $U_{4}$ where each $G[U_{i}]$ contains at least
$\left\lceil\frac{n}{4}\right\rceil$ disjoint blue copies of $K_{4}$ from $K$.
Thus, $|U_{i}|\geq 4\left\lceil\frac{n}{4}\right\rceil\geq n$ for all $i$.

Since all edges between two parts are red, we can construct a red copy of
$K_{4}$ by choosing one vertex from each part. Each part contains at least $n$
vertices. Therefore, there is a $n$ disjoint red copy $nK_{4}$ in $G$.

##  7\. The case when $n=2$

Although most of the techniques in the proof of Theorem 7 can be applied to
the case when $n=2$, there are still some cases in which such techniques
cannot be directly applied. When $n\geq 3$, at the beginning of the proof of
Theorem 7, we use $R(4,4)=18$ to show that the number of disjoint blue copies
of $K_{4}$ in $K_{23}$ is at least $2n-3+\lfloor\frac{n-1}{4}\rfloor$ disjoint
blue copies of $K_{4}$ which is larger than $n-1$. This implies that there are
at least two blue components. When $n=2$, there may be some coloring that has
only one blue copy of $K_{4}$, hence there is only one blue component. In this
case, we will use $R_{2}(nK_{4})$, instead of $R_{2}(4,4)$. From [2],
$R_{2}(nK_{4})=7n+4$ when $n$ is sufficiently large. To the authors’
knowledge, there is no result on the exact value or the upper bound of
$R_{2}(2K_{4})$ for small $n$. So, if an upper bound of $R_{2}(2K_{4})$ is
small enough, we get the exact value of $R_{2}(\mathscr{C}(2K_{4}))$ as in the
following theorem.

######  Theorem 14.

If $R_{2}(2K_{4})\leq 23$, then $R_{2}(\mathscr{C}(2K_{4}))=23$.

###### Proof.

From Lemma 6, we have $R_{2}(\mathscr{C}(2K_{4}))\geq 23$. Applying the same
setup as in Theorem 7, we consider a $2$-edge-coloring of $G=K_{23}$. Since
$23=18+4+1$, there are at least two monochromatic copies of $K_{4}$ in $G$.
Suppose that red is connected and $G$ contains at most one red copy of
$K_{4}$. Let $k$ be the number of disjoint blue copies of $K_{4}$ in $G$. Then
$1\leq k\leq 5$. Assume that there is no blue copy of a graph in
$\mathscr{C}(2K_{4})$. We partition the set of vertices $V(G)$ of $G$ into
$V_{1},V_{2},\dots,V_{k}$ and $V^{\prime}$ in the way that $G[V_{i}]$ is a
blue component of $G$ containing exactly one blue copy of $K_{4}$ in $K$ and
$V^{\prime}$ is the set of vertices outside $V_{1}\cup\dots\cup V_{k}$.
Consider the following four cases.

Case 1:

$k=1$.

Let $V_{1}^{\prime}$ be the set of vertices in $V_{1}$ other than those in the
blue copy of $K_{4}$. We note that by assumption of $V_{1}$,
$G[V_{1}^{\prime}]$ contains no blue copy of $K_{4}$.

  * •:

$|V_{1}|=23$. This means blue is connected. Since $R_{2}(2K_{4})\leq 23$,
$G[V_{1}]$ contains a red copy of $2K_{4}$.

  * •:

$|V_{1}|=22$. Then $|V_{1}^{\prime}|=18$. Since $R(4,4)=18$, $R(3,4)=9$ but
$G[V_{1}^{\prime}]$ cannot have another blue copy of $K_{4}$, there must be a
red copy of $K_{4}+K_{3}$. Joining the red copy of $K_{3}$ with another vertex
from $V^{\prime}$, we obtain a red copy of $2K_{4}$.

  * •:

$16\leq|V_{1}|\leq 22$. Since $R(3,4)=9$ and $16>12=9+3$, there is a red copy
of $2K_{3}$ in $G[V_{1}]$. Again, we combine a red copy of $K_{3}$ in
$G[V_{1}]$ and one vertex in $V^{\prime}$, then we get a red copy of $2K_{4}$.

  * •:

$10\leq|V_{1}|\leq 15$. Then $|V^{\prime}|\geq 8$. Since $R(2,4)=4$ and
$|V_{1}|,|V^{\prime}|>6$, there are two disjoint red copies of $K_{2}$ in both
$G[V_{1}]$ and $G[V^{\prime}]$. Joining each pair of the copies of $K_{2}$
each from $G[V_{1}]$ and $G[V^{\prime}]$, we get a red copy of $2K_{4}$.

  * •:

$4\leq|V_{1}|\leq 9$. Then $|V^{\prime}|\geq 14$. Since $R(3,4)=9$,
$G[V^{\prime}]$ contains a red copy of $2K_{3}$. Again, joining each red copy
of $K_{3}$ in $G[V^{\prime}]$ with another vertex in $V_{1}$, we get a red
copy of $2K_{4}$.

From all cases, we constructed a red copy of $2K_{4}$, which is a
contradiction.

When $k\geq 2$, let $U_{1}=V_{1}\cup V^{\prime}$ and $U_{i}=V_{i}$ for all
$2\leq i\leq k$. Let $y_{i}=|U_{i}|-4$, which is the number of vertices in
$U_{i}$ not in the blue copy of $K_{4}$.

Case 2:

$k=2$.

There are $8$ vertices containing in these two disjoint blue copies of
$K_{4}$. Thus, $y_{1}+y_{2}=15$ and we may assume that $y_{1}\geq y_{2}$

  * •:

$y_{1}\geq 12$. Since $R(3,4)=9$, there is a red copy of $2K_{3}$ in
$G[U_{1}]$. Combine this red copy of $K_{3}$ in $G[U_{1}]$ and one vertex in
$G[U_{2}]$, then we obtain a red copy of $2K_{4}$.

  * •:

$10\leq y_{1}\leq 11$. Since $R(3,4)=9$, $G[U_{1}]$ contains a red copy of
$K_{3}$. Note that $y_{2}=15-y_{1}\geq 4$. Applying Lemma 5 to
$G[U_{1}]-K_{3}$ and $G[U_{2}]$, each of $G[U_{1}]$ and $G[U_{2}]$ contains at
least one red copy of $K_{2}$. Joining the two disjoint red copies of $K_{2}$,
we get a red copy of $K_{4}$. Then joining the red copy of $K_{3}$ in
$G[U_{1}]$ with any remaining vertex in $U_{2}$, we get another red copy of
$K_{4}$.

  * •:

$8\leq y_{1}\leq 9$. Then $y_{2}=15-y_{1}\geq 6$. By Lemma 5, each of
$G[U_{1}]$ and $G[U_{2}]$ contains two disjoint red copies of $K_{2}$. Joining
each pair of red copies of $K_{2}$, we get a red copy of $2K_{4}$.

Case 3:

$k=3$.

There are $12$ vertices containing in three disjoint blue copies of $K_{4}$.
Therefore, $y_{1}+y_{2}+y_{3}=11$ and we can suppose that $y_{1}\geq y_{2}\geq
y_{3}$.

  * •:

$y_{1}\geq 4>y_{2}\geq y_{3}$. This implies $y_{1}\geq 5$. By Lemma 5,
$G[U_{1}]$ contains a red copy of $2K_{2}$. Construct two disjoint red copies
of $K_{4}$ where each copy is formed by a red copy of $K_{2}$ in $G[U_{1}]$, a
vertex in $U_{2}$ and a vertex in $U_{3}$.

  * •:

$y_{1}\geq y_{2}\geq 4>y_{3}$. By Lemma 5, each of $G[U_{1}]$ and $G[U_{2}]$
contains a red copy of $K_{2}$. The first red copy of $K_{4}$ is constructed
from one red copy of $K_{2}$ in $G[U_{1}]$, one vertex in $U_{2}$ and one
vertex in $U_{3}$. The second red copy of $K_{4}$ is constructed from one red
copy of $K_{2}$ in $G[U_{2}]$, one vertex in $U_{1}$ and one vertex in
$U_{3}$.

Case 4:

$k\geq 4$.

We form two disjoint red copies of $K_{4}$. Each copy is formed by joining one
vertex from each $G[U_{i}]$ for $1\leq i\leq 4$.

From four cases, we get two disjoint red copies of $K_{4}$. This contradicts
the assumption. ∎

##  8\. Conclusion and discussion

We have shown that $R_{2}(\mathscr{C}(nK_{4}))=13n-3$ for $n\geq 3$ and the
formula still holds for $n=2$ if $R_{2}(2K_{4})\leq 23$.

The exact Ramsey number $R_{2}(\mathscr{C}(nK_{r}))=(r^{2}-r+1)n-r+1$ when
$r\geq 5$ are known when $n\geq R_{2}(K_{r})$ [13]. But, the result may not be
true when $n$ is very small. For example, when $n=2$ and $r=5$, we use the
result from [13] and get $R_{2}(\mathscr{C}(2K_{5}))=21(2)-4=38<43\leq
R(5,5)$, which is impossible. It is interesting to know the upper bound of
$R_{2}(\mathscr{C}(nK_{r}))$, or in particular $R_{2}(\mathscr{C}(nK_{5}))$,
for small $n$.

To the authors’ knowledge, there is no result on the Ramsey number
$R_{2}(\mathscr{C}(nG))$ for a non-complete graph $G$. So the results for
other basic graphs $G$ such as cycles, paths, trees, or stars will be very
interesting.

## References

  * [1] Stefan A Burr.  Ramsey numbers involving graphs with long suspended paths.  Journal of the London Mathematical Society, 2(3):405–413, 1981\.
  * [2] Stefan A Burr.  On the ramsey numbers $r(G,nH)$ and $r(nG,nH)$ when n is large.  Discrete mathematics, 65(3):215–229, 1987.
  * [3] Stefan A Burr, P Erdős, and Joel H Spencer.  Ramsey theorems for multiple copies of graphs.  Transactions of the American Mathematical Society, 209:87–99, 1975\.
  * [4] Ernest J Cockayne and Peter J Lorimer.  The ramsey number for stripes.  Journal of the Australian Mathematical Society, 19(2):252–256, 1975\.
  * [5] Michael Codish, Michael Frank, Avraham Itzhakov, and Alice Miller.  Computing the ramsey number r(4,3,3) using abstraction and symmetry breaking.  Constraints, 21:375–393, 2016.
  * [6] Robert E Greenwood and Andrew Mattei Gleason.  Combinatorial relations and chromatic graphs.  Canadian Journal of Mathematics, 7:1–7, 1955.
  * [7] András Gyárfás and Gábor N Sárközy.  Ramsey number of a connected triangle matching.  Journal of Graph Theory, 83(2):109–119, 2016.
  * [8] András Gyárfás and Gábor Simony.  Edge colorings of complete graphs without tricolored triangles.  Journal of Graph Theory, 46(3):211–216, 2004.
  * [9] Peter Lorimer.  The ramsey numbers for stripes and one complete graph.  Journal of graph theory, 8(1):177–184, 1984.
  * [10] Peter J Lorimer and RJ Segedin.  Ramsey numbers for multiple copies of complete graphs.  Journal of Graph Theory, 2(1):89–91, 1978.
  * [11] Stanislaw Radziszowski.  Small ramsey numbers.  The electronic journal of combinatorics, 1000:DS1–Aug, 2011.
  * [12] Frank P Ramsey.  On a problem of formal logic.  Classic Papers in Combinatorics, pages 1–24, 1987.
  * [13] Barnaby Roberts.  Ramsey numbers of connected clique matchings.  Electronic Journal of Combinatorics, 24(1), 2017.
  * [14] Saul Stahl.  On the ramsey number $r(F,K_{m})$ where f is a forest.  Canadian Journal of Mathematics, 27(3):585–589, 1975.
  * [15] Douglas Brent West et al.  Introduction to graph theory, volume 2.  Prentice hall Upper Saddle River, 2001.