Smallest maximal matching in $K_{p_1,p_2,p_3,p_4,p_5}$ Suppose $0<p_1\leq p_2\leq p_3\leq p_4\leq p_5$ are integers. Find the size of a smallest maximal matching in $K_{p_1,p_2,p_3,p_4,p_5}$ in terms of $p_1,p_2,p_3,p_4,p_5$.
I have attempted to solve this but made no substantial progress.  I do know that a maximal matching must saturate 4 out of 5 of the independent sets of vertices. If $p_1+p_2+p_3\leq p_4$ then it is easy to see that there is a maximal matching of size $p_4$, and by the previous comment this is a smallest maximal matching. But I do not know about the other case, or if splitting into cases is even necessary.
 A: Hint:


*

*You won't be able to discard more than $p_5$, because that would mean that you have at least one unmatched vertex in at least two different partitions.

*Beacuse of parity there might be some $+1$'s or $-1$'s or $\lceil x/2\rceil$, etc.

*In which cases you can find a way to use all (but perhaps one) vertices of $p_1, p_2, p_3, p_4$?


I hope this helps $\ddot\smile$
A: Here is the solution I just discovered. I would still like to see other solutions!
Case 1: $p_1+p_2+p_3\leq p_4$. Then $p_4$ is the size of a smallest maximal matching (see my original post).
Case 2: $p_1+p_2+p_3\geq p_4$. Then $\left \lceil{(p_1+p_2+p_3+p_4)/2}\right \rceil$ is the size of a smallest maximal matching. Every maximal matching must have size at least $\left \lceil{(p_1+p_2+p_3+p_4)/2}\right \rceil$, since at least $p_1+p_2+p_3+p_4$ vertices must be saturated. Now we show that such a maximal matching is possible. Start with a bipartition  with $p_4$ on the left and $p_1+p_2+p_3$ on the right. Since $$p_1+p_3\leq (p_1+p_2+p_3+p_4)/2,$$ it is possible to move some of $p_2$ to the left so that the right side has size $\left \lceil{(p_1+p_2+p_3+p_4)/2}\right \rceil $. I can match the part of $p_2$ that moved with part of $p_3$, and then match $p_4$ with the rest of the right side (this is easier to see if you draw a picture).  There is possibly one vertex remaining on the right side, which I can connect to something in $p_5$. Now I have a matching which saturates $p_1$ through $p_4$ (so is maximal), and has size $\left \lceil{(p_1+p_2+p_3+p_4)/2}\right \rceil$.
Note: If $p_1+p_2+p_3=p_4$ then $p_4=\left \lceil{(p_1+p_2+p_3+p_4)/2}\right \rceil$, so it seems that my answers are consistent.
