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)). 

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})$.)
