Return to Answer

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{2p+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+p(s+1)$, $p(s-1)^2\geqslant s-1$, that 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{2p+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.

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.

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{2p+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+p(s+1)$, $p(s-1)^2\geqslant s-1$, that 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{2p+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.

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{2p+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+p(s+1)$, $p(s-1)^2\geqslant s-1$, that 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{2p+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.

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.

Denote by $f_i$ the size of a maximal matching of color $i$. Assume that $f_i\leqslant m_i-1$, but $n\geqslant 2m_1+m_2+\dots+m_r-(r-1)\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, also 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$. We have $|W|=n-|U|\geqslant n-\sum |U_i|\geqslant 2+p+\sum p_i$. Note that any graph on the vertex set $W$ with at least $n-2p_i$ components has at most $\binom{2p_i+1}2$ edges (if we replace two components of sizes $a$, $b$ to two components of sizes $1,a+b-1$, the number of edges does not decrease, and a finite number of such steps reduces the sizes of components to many 1's and at most $2p_i+1$). Thus totally the complete graph on $W$ has at most $\sum_i \binom{2p_i+1}2$ edges. I claim that $\sum_i \binom{2p_i+1}2\leqslant \binom{2p+p_1+\dots+p_r+1}2<\binom{|W|}2$, this gives a contradiction. For proving this inequality for all non-negative $p_i\in [0,p]$ where $p\geqslant 1$ we may, for example, 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 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+p(s+1)$, $p(s-1)^2\geqslant s-1$, that is true.

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{2p+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+p(s+1)$, $p(s-1)^2\geqslant s-1$, that 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{2p+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.