= Solution
Use the two-colour <matching Ramsey number>
$$
R(rK_2,sK_2)=2r+s-1
\qquad(r\geq s).
$$
Its upper bound follows by induction on $s$. If there is a blue edge, remove its endpoints and apply the induction hypothesis to the remaining $K_{2r+s-3}$: it contains either a red $r$-edge matching or a blue $(s-1)$-edge matching, and in the latter case the removed edge completes a blue $s$-edge matching. If there is no blue edge, the graph itself contains a red $r$-edge matching. For $r=s=t$, this gives the required monochromatic matching in $K_{3t-1}$.
The result never remains true for $K_{3t-2}$, including $t=1$. Partition its vertices into $A$ and $B$ with $|A|=2t-1$ and $|B|=t-1$. Colour edges within $A$ blue and every other edge yellow. A blue matching has at most $t-1$ edges, while every yellow edge meets $B$, so a yellow matching also has at most $t-1$ edges.
Back to article page
