A direct proof that every $r$-colored complete graph on $n=(r+1)m-(r-1)$ vertices has a monochromatic matching of size $m$?

Question

Cockayne and Lorimer ("The Ramsey number for stripes" 1975) prove that in every $r$-colored complete graph on $n=\sum_{i=1}^rm_i+m_1-(r-1)$ vertices, where $m_1\geq \dots\geq m_r\geq 1$, has a monochromatic matching in color $i$ of size $m_i$ (and this is tight). When $m_1=\dots=m_r$, we get $n=(r+1)m-(r-1)$. Their proof is a clever induction argument, but it seems to fundamentally use the fact that they are proving the more general ("non-diagonal") version. There should be no complaints since they are able to prove the statement by proving something more general. However, if you think about the problem for a few minutes, you will be able to come up with a proof of the 2-color case, and a few minutes more, you'll get the three color case, but I haven't found a proof for the $r$-color case which does not rely on proving the more general non-diagonal statement. Basically, I'm curious if there is another proof of the diagonal version of their result along the lines of the $r=2$ and $r=3$ case below. Beyond that, I'm wondering if there is a non-inductive proof which uses the Berge-Tutte theorem/formula (for instance) on the size of a largest matching in a graph.

First note that the result holds when $r=1$ or $m=1$, so suppose $r, m\geq 2$ and the result holds for all $1\leq r', m'$ with $r'+m'<r+m$.

Proof for $r=2$: We have $n=3m-1$, so if we can find a set of three vertices which contain both a red edge and a blue edge, we can apply induction on the remaining $n-3$ vertices to get a matching of size $m-1$ in one of the colors, which together with either the red edge or the blue edge gives a matching of size $m$. If we can't find such a set, then only one color is used.

Proof for $r=3$: We have $n=4m-2$, so if we can find a set of at most four vertices which contain edges of all three colors, we can apply induction on the remaining at least $n-4$ vertices as before. If we can't find such a set, then we can deduce that only two colors are used. Indeed, we are done if some vertex is incident with edges of all three colors or all vertices are incident with edges of only one color, so some vertex is incident with say only red and blue edges. But now if there is a green edge anywhere, this will give a set of size at most 4 which sees edges of all three colors.

Answer 1

Here goes a direct proof of a general fact. It is not inductive, so you may substitute $m_1=m_2=\dots=m_r=m$ into it, but it does not become any shorter. It uses Tutte/Berges formula of the maximal matching, as you ask for.

We use two easy lemmas.

Lemma 1. A graph on $N$ vertices with at least $N-k$ components has at most $\binom{k+1}2$ edges.

Proof. Let $C_0$ denote a maximal component. If certain component $C\ne C_0$ contains at least two vertices, move one of them to $C_0$. The number of edges increases. After several steps all components different from $C_0$ contain 1 vertex, and $C_0$ at most $k+1$ vertices, thus the number of edges does not exceed $\binom{k+1}2$.

Lemma 2. If $p=0$ or $p\geqslant 1$, and $p_1,\dots,p_r\in [0,p]$ are real numbers, than $\sum_i \binom{2p_i+1}2\leqslant \binom{p+p_1+\dots+p_r+1}2$.

Proof. The case $p=0$ is clear, assume that $p\geqslant 1$. Fix $p$ and note that the difference LHS-RHS is a quadratic trinomial in $p_i$ with positive leading coefficient, thus its maximal value (with all other $p_j$'s being fixed and $p_i$ varying from 0 to $p$) is attained either for $p_i=0$ or $p_i=p$. So, we need to check it only when $p_1=\dots=p_s=p,p_{s+1}=\dots=p_r=0$ for certain index $s$. This rewrites as $sp(2p+1)\leqslant (s+1)p((s+1)p+1)/2$, $2s(2p+1)\leqslant p(s+1)^2+s+1$, $p(s-1)^2\geqslant s-1$, which is true.

Now assume that $n\geqslant 2m_1+m_2+\dots+m_r-(r-1)$ and $G$ is a complete graph on the ground set $V$, $|V|=n$, edges of $G$ are colored in $r$ colors so that the maximal matching of color $i$ contains $f_i<m_i$ edges. Then $n\geqslant \max(f_i)+f_1+\dots+f_r+2$. By Tutte/Berges there exist subsets $U_i$ of the vertex set $V$ such that the graph $G_i$ formed by the edges of color $i$ on the vertex set $V\setminus U_i$ has $|U_i|+(n-2f_i)$ odd components. Actually I need only that it has at least $|U_i|+(n-2f_i)$ components. In particular this implies $n-|U_i|=|V\setminus U_i|\geqslant |U_i|+(n-2f_i)$, $|U_i|\leqslant f_i$. Denote $p_i=f_i-|U_i|$, these are non-negative integer numbers, and denote $p=\max(p_i)\leqslant \max(f_i)$.

Denote $U=\cup U_i$, $W=V\setminus U$. The number of components formed by color $i$ on the set $W$ is not less than $|U_i|+n-2f_i-|U\setminus U_i|=|W|-2p_i$. Thus the number of edges of color $i$ between the vertices from $W$ does not exceed $\binom{2p_i+1}2$ by Lemma 1, and the total number of edges between the vertices of $W$ does not exceed $\binom{p+p_1+\dots+p_r+1}2$ by Lemma 2. On the other hand, we have $|W|=n-|U|\geqslant n-\sum |U_i|\geqslant 2+p+\sum p_i$. This gives a contradiction.

Answer 2

Strictly speaking, no. Because the implication "there are at least $C$ colors" => "there is a complete subgraph in $C+1$ vertices that has at least $C$ colors" is true only for $C<4$.

In fact, for $C<4$ is even true that "there are at least $C$ colors" => "there is a connected subgraph with $C$ edges all of different color".

Instead, for $C\geq 4$ we can have examples as the following: a complete graph with vertices $\{1,2,3,4,5,6\}$ and all edges red, except for $(1,2):=blue$, $(3,4):=green$, $(5,6):=yellow$.

Of course this doesn't exclude that some clever and relatively simple observation may solve the general induction step, but at least this shows why the steps $r=1,2,3$ are so easy in comparison.