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?

  • $\begingroup$ Your problem is not really about graph theory, it is equivalent to having $r$ piles of coins with $n_1,n_2\dots n_r$ piles each and at each step selecting two non-empty piles and removing one coin from each. What you want to know is what is the maximum number of coins you can remove. $\endgroup$ – Jorge Fernández Hidalgo Jul 22 '15 at 8:06
  • $\begingroup$ @dREaM I agree. I essentially suggested a greedy strategy for the problem, but I don't know whether it gives an optimal solution, i.e., a maximal matching. (It seems obvious it does; but I haven't proved it formally.) $\endgroup$ – blazs Jul 22 '15 at 8:10
  • 1
    $\begingroup$ I think you can reach the optimal solution by using an argument similar to that used for the hakimi-havel algorithm. In other words at each step you have to remove a coin from the two largest piles. $\endgroup$ – Jorge Fernández Hidalgo Jul 22 '15 at 8:15
  • $\begingroup$ Hakimi-Havel is used for something different but I am almost 100% sure you can extrapolate the idea mutatis-mutandis. You also have t be carefull because in Hakimi-havel you can only substract from the same two piles once. $\endgroup$ – Jorge Fernández Hidalgo Jul 22 '15 at 8:16
  • $\begingroup$ Did you read what I wrote? $\endgroup$ – Jorge Fernández Hidalgo Jul 22 '15 at 10:31

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$

  • $\begingroup$ I like this a lot. Shouldn't it be $f(i)\longleftrightarrow f(i+n/2)$ for $0\le i\le n/2$, though? (Less than or equal to instead of the strict inequality.) $\endgroup$ – blazs Jul 23 '15 at 11:50
  • $\begingroup$ @user111691 The indices start at $0$, so the last one is $n-1$, not $n$, and the last of the first half is $\frac{n}{2}-1$, because $\frac{n}{2}$ is the first index of the second half. For example let $n=6$, then the first half is $\{0,1,2\}$, while the second is $\{3,4,5\}$ and we would like $0\leq i \leq 2 < 3=\frac{6}{2}$ so that for $i=2$ we have $i+\frac{n}{2} = 2+3 \leq n-1=5 < n = 6$. $\endgroup$ – dtldarek Jul 23 '15 at 13:11
  • $\begingroup$ Oh, wait, you still need to show that the matching has size $\delta(G)$. $\endgroup$ – blazs Jul 23 '15 at 13:40
  • $\begingroup$ @user111691 And what is the size of the matching in the second case? $\endgroup$ – dtldarek Jul 23 '15 at 14:21
  • $\begingroup$ You're right... I just skimmed the proof. Sorry. $\endgroup$ – blazs Jul 23 '15 at 14:22

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.