Låt $n \geq 1$ vara ett heltal. Konstruera en graf $G_{n} = (V_{n}, E_{n})$ med

V _ {n} = \left\{x _ {1}, x _ {2}, \dots , x _ {n} \right\} \cup \left\{y _ {1}, y _ {2}, \dots , y _ {n} \right\}

och

\begin{array}{l} E _ {n} = \left\{x _ {1} x _ {2}, x _ {2} x _ {3}, \dots , x _ {n - 1} x _ {n} \right\} \cup \left\{y _ {1} y _ {2}, y _ {2} y _ {3}, \dots , y _ {n - 1} y _ {n} \right\} \\ \cup \left\{x _ {i} y _ {i - 1}, x _ {i} y _ {i}, x _ {i} y _ {i + 1} \mid i = 2, 3, \dots , n - 1 \right\} \\ \cup \left\{x _ {1} y _ {1}, x _ {1} y _ {2}, x _ {n} y _ {n - 1}, x _ {n} y _ {n} \right\}. \end{array}

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 matchningar i $G_{n}$ . Härled en rekursionsformel för $a_{n}$ och använde den för att visa att

a _ {n} = \frac {1}{3} (2 ^ {n + 1} + (- 1) ^ {n}), \qquad \text{för alla } n \geq 1.