In the language of graph theory, we have a simple digraph $G$ which is 2-regular and we seek the number of sub-digraphs which are 1-regular. We now present two solution paths.

First solution, combinatorial We construct a simple undirected bipartite graph $\Gamma$ as follows:
* the vertex set consists of two copies of $V(G)$, say $V_{\text{out}}$ and $V_{\text{in}}$; and
* for $v \in V_{\text{out}}$ and $w \in V_{\text{in}}$ we have an undirected edge $vw \in E(\Gamma)$ if and only if the directed edge $v \to w$ is in $G$.
Moreover, the desired sub-digraphs of $H$ correspond exactly to perfect matchings of $\Gamma$. However the graph $\Gamma$ is 2-regular and hence consists of several disjoint (simple) cycles of even length. If there are $n$ such cycles, the number of perfect matchings is $2^n$, as desired.

**Second solution by linear algebra over $\mathbb{F}_2$ (Brian Lawrence)** This is actually not that different from the first solution. For each edge $e$, we create an indicator variable $x_e$. We then require for each vertex $v$ that:
* If $e_1$ and $e_2$ are the two edges leaving $v$, then we require $x_{e_1} + x_{e_2} \equiv 1 \pmod 2$.
* If $e_3$ and $e_4$ are the two edges entering $v$, then we require $x_{e_3} + x_{e_4} \equiv 1 \pmod 2$.

We thus get a large system of equations. Moreover, the solutions come in natural pairs $\vec{x}$ and $\vec{x} + \vec{1}$ and therefore the number of solutions is either zero, or a power of two. So we just have to prove there is at least one solution.
For linear algebra reasons, there can only be zero solutions if some nontrivial linear combination of the equations gives the sum $0 \equiv 1$. So suppose we added up some subset $S$ of the equations for which every variable appeared on the left-hand side an even number of times. Then every variable that did appear appeared exactly twice; and accordingly we see that the edges corresponding to these variables form one or more even cycles as in the previous solution. Of course, this means $|S|$ is even, so we really have $0 \equiv 0 \pmod 2$ as needed.