Size of a maximum matching of a complete multipartite graph? Let $G=(V,E)$ be a complete multipartite graph on even number of vertices, with $V(G) = X_1\cup X_2\cup\ldots\cup X_k$, let $n_i := |X_i|$, and suppose $n_1\le n_2\le \ldots\le n_k$.
The problem I am trying to solve is asking for the size of a maximum matching of $G$, in particular, it claims that the answer is $\min(\delta(G), |V(G)|/2)$.
Obviously $\deg v = n-n_i$ for all $v\in X_i$, which means $\delta(G) = n-n_k$.
Let's to construct a matching in the following way. Add $n_1$ edges between vertices from $X_1$ to $X_2$; then add $n_2-n_1$ edges from uncovered vertices of $X_2$ to $X_3$; then add $n_3-(n_2-n_1)$ edges from uncovered vertices of $X_3$ to $X_4$; and so on. This gives us a matching of size $$n_1 + (n_2-n_1) + (n_3-(n_2-n_1)) + (n_4-(n_3-(n_2-n_1))) + \ldots,$$ however, this expression evaluates to the sum of all odd-index terms or all even-index terms, depending on $k$. So clearly, this is not the way to go.
Any hints?
 A: The problem is equivalent to having $r$ piles: pile $1$, pile $2$, pile $3\dots$ pile $r$ with $n_1\leq n_2\leq \dots \leq n_r$ coins respectively, and allowing the following operation: selecting two non-empty piles and removing a coin for each. The number of vertices in the maximum matching is therefore equal to the maximum number of coins we can remove with this process.
When $n_r\geq n_1+n_2+n_3+\dots n_{r-1}$ the maximum number of coins we can remove is clearly $2(n_1+n_2+\dots n_{r-1})$.
When $n_3<n_1+n_2+\dots n_{r-1}$ we can always remove all coins or all coins except for $1$, depending if there is an odd or even number of coins in total. 
The proof is by strong induction over $n_1+n_2+\dots+n_r$, the base case is when there is $1$ coin, it is clear it is true. 
Now suppose we have $n_1\leq n_2+\dots\leq n_r$ so that $n_r<n_1+n_2+\dots + n_{r-1}$ remove one coin from pile $r$ and $r-1$ leaving them with $n_r-1$ and $n_{r-1}-1$ coins. We have to prove we can now remove all coins except for possibly one after this operation.
Notice that if  the largest pile still has less coins than the other piles combined we can apply the induction hypothesis. We will study $2$ cases and try to use this fact to prove each one.
Case 1: Even after the operation pile $r$ is still the pile with the most coins. In this case it is clear the largest pile still has less coins than the rest.This is because both quantities where decrease by one. In this case we can just use the induction hypothesis.
Case $2$: After removing a coin from pile $r$ it is no longer the largest pile, in this case it must be because piles $r,r-1$ and $r-2$ all had the same number of coins, meaning the largest pile is now $r-2$ and has size $n_r$. However we know the sum of piles $r$ and $r-1$ is at least $2(n_r-1)=2n_r-2$. If we had $n_r>2n_r-2$ we would be done because we could apply the induction hypothesis, of course we have $n_r>2n_r-2\iff n_r>2$. So if piles $r,r-1$ and $r-2$ initially had $3$ or more coins we can use the induction hypothesis. If piles $r,r-1$ and $r-2$ had one coin it is also clear we can remove all coins except for one. So all that remains is when piles $r,r-1$ and $r-2$ had size $2$, this is also simple. Remove coins between the piles of size two until one pile of size two or zero piles of size two remain. If there is still as pile of size $2$ remaining then select a pile of size $1$ and remove a coin from the pile of size $2$ and the selected pile of size $1$. After this we only have piles of size $1$, and it is clear we can remove coins so that at most one coin remains.
Therefore the size of the maximum matching is as follows:
$2(n_1+n_2+\dots n_{r-1})$ if $n_1+n_2+\dots n_{r-1}\leq n_r$
In the other case it is $n_1+n_2+\dots n_{r-1}+n_r$ if this sum is even or $n_1+n_2+\dots n_{r-1}+n_r-1$ if there is an odd number of vertices in total.
A: I think you can prove it just fine using the language of graph theory.
Case 1. Suppose that $n_k \leq \frac{n}{2}$.
For simplicity, let's index all the vertices in $V$ so that vertices of $X_1$ are first, then vertices of $X_2$ and so on, i.e., take arbitrary bijection
$f : \{0,1,\ldots,n-1\} \to V$ such that
\begin{align}
X_1 &= f\Big(\big\{0,1,\ldots,n_1-1\big\}\Big)\\
X_2 &= f\Big(\big\{n_1,n_1+1,\ldots,n_1+n_2-1\big\}\Big)\\
&\ \ \vdots\\
X_i &= f\Big(\big\{s_i,s_i+1,\ldots,s_i+n_i-1\big\}\Big)\quad \text{ for } \quad s_i = \sum_{j < i}n_j = \Bigg|\bigcup_{j<i}X_i\Bigg|.
\end{align}
Now match $$f\big(i\big) \longleftrightarrow f\Big(i+\frac{n}{2}\Big)\quad \text{ for }\quad 0 \leq i < \frac{n}{2}.$$
This generates a proper matching, because $n_i \leq n_k \leq \frac{n}{2}$, so we always connect pairs from different sets $X_i$ and $X_j$. Moreover, this is a maximum cardinality matching, because it matches all the vertices.
Case 2. Suppose that $n_k > \frac{n}{2}$. 
Then we match all vertices of $\bigcup_{i < k}X_i$ to $X_k$, we can do that, because $$\sum_{i<k}n_i = n-n_k < \frac{n}{2} < n_k.$$
We can prove this is the maximum cardinality matching via Berge's lemma. In this case no augmenting path exists, because it has to start and end in an unmatched vertex, but free vertices belong only to $X_k$ which makes it impossible for the path to be of odd length.
Alternatively you can observe that no augmenting path will use an edge between $X_i$ and $X_j$ for $i,j < k$, so this becomes effectively a bipartite graph with a matching that saturates the whole smaller partition.
I hope this helps $\ddot\smile$
