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

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