Prove that there is always a perfect match

Question

Let G_n be a graph with 2n nodes: a₀, a₁, ..., a_n-1, b₀, b₁, ..., b_n-1. Let the edges be formed like this:

Node $a_i$ connects with $b_j$ and $b_k$, where $j = 2i \pmod n$ and $k = (2i + 1) \pmod n$

Prove that every G_n has a perfect match.

---

For n = 4, we would get this:

where the perfect match would be (a₀, b₀), (a₁, b₂), (a₂, b₁) and (a₃, b₃).

---

My attempt:

I wrote some code which performs a greedy algorithm to find a match and for G₄ and G₅ I see that the output is a perfect match. However, I am not sure how to prove that in math (that there is a perfect match (not necessarily found with the greedy algorithm)).

Answer 1

Observe that for each $i=0,1,\ldots,n-1$, $a_i$ is joined to $b_{2i}$ and $b_{2i+1}$, where the subscripts are taken modulo $n$. This means the degree of vertex $a_i$ is 2 for each $i$.

The degree of vertex $b_i$ is also 2 for each $i$. One way to prove this is to consider the case of even $n$ and odd $n$ separately. Observe that the neighbors of $a_0$ are the first two vertices on the right side, the neighbors of $a_1$ are the next two vertices on the right side, and so on. If $n$ is even, then the vertices $b_{2i}$ and $b_{2i+1}$ have the same set of neighbors, namely $a_i$ and $a_{i+n/2}$. If $n$ is odd, then the argument is only slightly more complicated - some vertex will have the last vertex $b_{n-1}$ and the first vertex $b_0$ as a neighbor.

So the bipartite graph is 2-regular. By Hall's theorem, the graph has a perfect matching.

Answer 2

I think one can prove this by Hall's marriage theorem. Now all we have to show is that for any $X \subset A$, $\mid N(X) \mid \geq \mid X \mid $. where $A=$ {$a_0,a_1,a_2 \dots a_{n-1}$}. I feel that this should be clear as well, because any vertex $a_i$ is connected to two vertex $b_j$ and $b_{j+1}$ for some $j<n$.

From here I think we can do a proof by contradiction. If $\mid N(X) \mid \geq \mid X \mid $ is not true for some $X \subset A$ there must exist $a_i,a_r\in A$ with the same neighbors. This should imply $i=r$.

Answer 3

When $n$ is odd, for $0\leqslant i\leqslant \frac{n-3}{2}$, $a_i$ is connected to $b_{2i}$ and $b_{2i+1}$. For $\frac{n+1}{2}\leqslant i\leqslant n-1$, $a_i$ is connected to $b_{2i-n}$ and $b_{2i+1-n}$. Also, $a_{\frac{n-1}{2}}$ is connected to $b_{n-1}$ and $b_0$. Now, $(a_i,b_{2i})$ for $0\leqslant i\leqslant \frac{n-3}{2}$, $(a_j, b_{2j-n})$ for $\frac{n+1}{2}\leqslant j\leqslant n-1$, and $(a_{\frac{n-1}{2}},b_{n-1})$ is a perfect matching. (i.e. $(a_0, b_0)(a_1,b_2)\dots (a_{\frac{n-1}{2}},b_{n-1})(a_{\frac{n+1}{2}},b_{1})(a_{\frac{n+3}{2}},b_{3})\dots (a_{n-1},b_{n-2})$.)

When $n$ is even, for $0\leqslant i\leqslant \frac{n}{2}-1$, $a_i$ is connected to $b_{2i}$ and $b_{2i+1}$. For $\frac{n}{2}\leqslant i\leqslant n-1$, $a_i$ is connected to $b_{2i-n}$ and $b_{2i+1-n}$. Now, $(a_i,b_{2i})$ for $0\leqslant i\leqslant \frac{n}{2}-1$, and $(a_j, b_{2j-n})$ for $\frac{n}{2}\leqslant j\leqslant n-1$ is a perfect matching. (i.e. $(a_0, b_0)(a_1,b_2)\dots (a_{\frac{n}{2}-1},b_{n-2})(a_{\frac{n}{2}},b_{1})(a_{\frac{n}{2}+1},b_{3})\dots (a_{n-1},b_{n-1})$.)