Condition on $p, q, r$ that is equivalent to 'the complete tripartite graph $K_{p, q, r}$ has a perfect matching'

Question

A $k$-regular bipartite graph has a perfect matching.

So, I feel like a safe guess would be to say that $p=q=r$. Is this correct?

Answer 1

The answer is that the following conditions are necessary and sufficient:

1. $p+q+r$ is even.
2. $p+q \ge r, p+r \ge q, q+r\ge p$

That condition 1) is necessary is evident, $p+q+r$ is the number of vertices of the graph, so it has to be even for a perfect matching to exist. Assume one of the conditions of 2) is violated, say we have $p+q < r$. Since each vertex in the $r$-part only has neighbours in the $p$- and $q$-part, there are not enough vertices available in those 2 parts to match each vertex of the $r$-part.

To show that the conditions are sufficient, we construct such a matching.

Partition the vertices of $r$-part of the graph into 2 subsets, $V_{r,p}$ with $\frac{r+p-q}2$ vertices and $V_{r,q}$ with $\frac{r+q-p}2$ vertices. Both numbers are integers (because of condition 1) and $\lvert V_{r,p}\rvert = \frac{r+p-q}2=\frac{r+p+q}2 - q$, similar for $V_{r,q}$). Those values are also non-negative, as per condition 2). Finally, we have $\frac{r+p-q}2 + \frac{r+q-p}2 =r.$ That means such a partition is possible.

Do the same with the $p$-part ($p=\frac{p+q-r}2 + \frac{p+r-q}2$) and the $q$-part of the graph ($q=\frac{q+p-r}2 + \frac{q+r-p}2$).

Now the perfect matching is any matching between the $\frac{p+q-r}2 = \frac{q+p-r}2$ vertices of $V_{p,q}$ and $V_{q,p}$, plus another matching between the $\frac{p+r-q}2 = \frac{r+p-q}2$ vertices of $V_{p,r}$ and $V_{r,p}$ and finally a matching between the $\frac{q+r-p}2 = \frac{r+q-p}2$ vertices of $V_{q,r}$ and $V_{r,q}$.