Prove that there is always a perfect match Let Gn be a graph with 2n nodes: a0, a1, ..., an-1, b0, b1, ..., bn-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 Gn has a perfect match.

For n = 4, we would get this:

where the perfect match would be (a0, b0), (a1, b2), (a2, b1) and (a3, b3).

My attempt:
I wrote some code which performs a greedy algorithm to find a match and for G4 and G5 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)). 
 A: 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$.
A: 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})$.)
A: 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.
