Uppgift 10.

Låt $n\ge1$ vara ett heltal. Konstruera en graf $G_n=(V_n,E_n)$ med $V_n=\{x_1,x_2,\ldots,x_n\}\cup\{y_1,y_2,\ldots,y_n\}$ och $E_n=\{x_1x_2,x_2x_3,\ldots,x_{n-1}x_n\}\cup\{y_1y_2,y_2y_3,\ldots,y_{n-1}y_n\}$ $\cup\{x_i y_{i-1},x_i y_i,x_i y_{i+1}\mid i=2,3,\ldots,n-1\}$ $\cup\{x_1y_1,x_1y_2,x_ny_{n-1},x_ny_n\}$. En komplett matchning i en graf är en matchning där alla hörn är matchade. Observera att grafen inte behöver vara bipartit. Låt $a_n$ vara antalet kompletta matchingar i $G_n$. Härled en rekursionsformel för $a_n$ och använde den för att visa att $a_n=\frac13(2^{n+1}+(-1)^n)$, för alla $n\ge1$.