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. Remark: The author's original proposal contained a second part asking to show that it was not always possible for the resulting $H$ to be connected, even if $G$ was strongly connected. This problem is related to IMO Shortlist 2002 C6, which gives an example of a strongly connected graph which does have a full directed Hamiltonian cycle.

v_Enhance said: Quote: 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. I don't understand the methods he used to get to this. Can someone help me understand?

@above Here is the linear algebra solution written out more explicitly. For each edge $e$, create a variable $x_e$. This variable is $1$ if the edge $e$ is present in the new graph obtained by deletion, and is $0$ otherwise. Now suppose for some vertex $v$, $e_1,e_2$ are the two edges directed out, and $e_3,e_4$ are the two edges directed in. We want exactly one of $e_1,e_2$ to be present, and exactly one of $e_3,e_4$ to be present. You can easily check that this is equivalent to demanding that $x_{e_1}+x_{e_2}=1$ and $x_{e_3}+x_{e_4}=1$. So finding such deletion graphs is equivalent to solving all these linear equations where all the variables are in $\{0,1\}$. Now you may be asking, "where is the mod 2 coming in"? The reason is that the solution space is $\{0,1\}^N$ for some $N$, which is not natural to work with. However, we can replace $\{0,1\}$ with $\mathbb{F}_2$, or the integers mod 2, which is a field. This means that we can use Linear Algebra. Note that those equations that we wrote are equivalent to the same equations mod 2. Therefore, we have some huge system of linear equations over a field. The idea from linear algebra is that the set of solutions is a vector subspace of $\mathbb{F}_2^N$, so its size is $2^r$, where $r$ is the dimension of that vector space. It suffices now to show that $r\ge 1$, or that there are at least two solutions. In fact, swapping deleted with not deleted, it suffices to show the existence of just one solution. This can be done greedily, here is a sketch: the idea is to delete an edge, look at the two edges - one that shares a tail with the original edge, one that shares the tip. Then those must be not deleted, so each of those edges have another edge that must be deleted, and so on until we form a cycle. Then we delete that cycle and repeat. Remark: The final greedy idea basically solves the problem anyway, but its harder to write out than the linear algebra.

Interesting fact: As noted above by v_enhance, we can group the edges into even cycles that are independent of each other, and each have exactly 2 ways to be deleted. The groups of edges have 2 forms: 1: We have 2 sets A,B of n vertices where each vertex in A goes to 2 vertices in B, and each vertex in B comes from 2 vertices in A. 2: This graph is sort of hard to explain, but basically there are 2 disjoint paths X to Y(for some X,Y) and some collection of cycles that fill up all the edges of these vertices, it is obtained by taking a 2-dihedral graph with only 2 ways to delete and splitting a vertex.

Nice problem. Here's my solution: Consider the adjacency matrix of the digraph composed by taking cities of Onewaynia as vertices, and roads as (directed) edges. Then the problem states that given a $n \times n$ $(0,1)$ matrix with exactly $2$ ones in each row/column, prove that the number of ways of removing $n$ ones such that each row/column has exactly $1$ one is $2^m$ for some $m \in \mathbb{N}$. This is quite intuitive. Consider the first one in the first row. Connect it to the next one of this row. Now, turn $90^{\circ}$, and join this one to the second one in its column. Continue in this fashion, i.e. move in the sequence row to column to row to column, and so on, till you hit the first element. Note that you can hit the first element only while moving along the column consisting of it, and so this weird self-intersecting polygon shape must have an even number of vertices and edges. Remove this polygon, and do the same thing with the remaining ones. In the end, we will get a number of such weird polygons, each having an even number of vertices. As this process does not depend on the element from which we start, so we will always get the same polygons for a given matrix. I have shown such a polygon in a $4 \times 4$ matrix below (The dots represent ones):- [asy][asy] /* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki go to User:Azjps/geogebra */ import graph; size(10cm); real labelscalefactor = 0.5; /* changes label-to-point distance */ pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = -14.26, xmax = 11.94, ymin = -6.45, ymax = 4.77; /* image dimensions */ /* draw figures */ draw((-4.36,1.95)--(-3,1.95), linewidth(1.2) + blue); draw((-3,1.95)--(-3,0.59), linewidth(1.2) + blue); draw((-3,0.59)--(-4.36,0.59), linewidth(1.2) + blue); draw((-4.36,0.59)--(-4.36,1.95), linewidth(1.2) + blue); draw((-3,1.95)--(-1.64,1.95), linewidth(1.2) + blue); draw((-1.64,1.95)--(-1.64,0.59), linewidth(1.2) + blue); draw((-1.64,0.59)--(-3,0.59), linewidth(1.2) + blue); draw((-3,0.59)--(-3,1.95), linewidth(1.2) + blue); draw((-1.64,1.95)--(-0.28,1.95), linewidth(1.2) + blue); draw((-0.28,1.95)--(-0.28,0.59), linewidth(1.2) + blue); draw((-0.28,0.59)--(-1.64,0.59), linewidth(1.2) + blue); draw((-1.64,0.59)--(-1.64,1.95), linewidth(1.2) + blue); draw((-0.28,1.95)--(1.08,1.95), linewidth(1.2) + blue); draw((1.08,1.95)--(1.08,0.59), linewidth(1.2) + blue); draw((1.08,0.59)--(-0.28,0.59), linewidth(1.2) + blue); draw((-0.28,0.59)--(-0.28,1.95), linewidth(1.2) + blue); draw((-4.36,0.57)--(-3,0.57), linewidth(1.2) + blue); draw((-3,0.57)--(-3,-0.79), linewidth(1.2) + blue); draw((-3,-0.79)--(-4.36,-0.79), linewidth(1.2) + blue); draw((-4.36,-0.79)--(-4.36,0.57), linewidth(1.2) + blue); draw((-3,0.57)--(-1.64,0.57), linewidth(1.2) + blue); draw((-1.64,0.57)--(-1.64,-0.79), linewidth(1.2) + blue); draw((-1.64,-0.79)--(-3,-0.79), linewidth(1.2) + blue); draw((-3,-0.79)--(-3,0.57), linewidth(1.2) + blue); draw((-1.64,0.57)--(-0.28,0.57), linewidth(1.2) + blue); draw((-0.28,0.57)--(-0.28,-0.79), linewidth(1.2) + blue); draw((-0.28,-0.79)--(-1.64,-0.79), linewidth(1.2) + blue); draw((-1.64,-0.79)--(-1.64,0.57), linewidth(1.2) + blue); draw((-0.28,0.57)--(1.08,0.57), linewidth(1.2) + blue); draw((1.08,0.57)--(1.08,-0.79), linewidth(1.2) + blue); draw((1.08,-0.79)--(-0.28,-0.79), linewidth(1.2) + blue); draw((-0.28,-0.79)--(-0.28,0.57), linewidth(1.2) + blue); draw((-4.36,-0.81)--(-3,-0.81), linewidth(1.2) + blue); draw((-3,-0.81)--(-3,-2.17), linewidth(1.2) + blue); draw((-3,-2.17)--(-4.36,-2.17), linewidth(1.2) + blue); draw((-4.36,-2.17)--(-4.36,-0.81), linewidth(1.2) + blue); draw((-3,-0.81)--(-1.64,-0.81), linewidth(1.2) + blue); draw((-1.64,-0.81)--(-1.64,-2.17), linewidth(1.2) + blue); draw((-1.64,-2.17)--(-3,-2.17), linewidth(1.2) + blue); draw((-3,-2.17)--(-3,-0.81), linewidth(1.2) + blue); draw((-1.64,-0.81)--(-0.28,-0.81), linewidth(1.2) + blue); draw((-0.28,-0.81)--(-0.28,-2.17), linewidth(1.2) + blue); draw((-0.28,-2.17)--(-1.64,-2.17), linewidth(1.2) + blue); draw((-1.64,-2.17)--(-1.64,-0.81), linewidth(1.2) + blue); draw((-0.28,-0.81)--(1.08,-0.81), linewidth(1.2) + blue); draw((1.08,-0.81)--(1.08,-2.17), linewidth(1.2) + blue); draw((1.08,-2.17)--(-0.28,-2.17), linewidth(1.2) + blue); draw((-0.28,-2.17)--(-0.28,-0.81), linewidth(1.2) + blue); draw((-4.36,-2.19)--(-3,-2.19), linewidth(1.2) + blue); draw((-3,-2.19)--(-3,-3.55), linewidth(1.2) + blue); draw((-3,-3.55)--(-4.36,-3.55), linewidth(1.2) + blue); draw((-4.36,-3.55)--(-4.36,-2.19), linewidth(1.2) + blue); draw((-3,-2.19)--(-1.64,-2.19), linewidth(1.2) + blue); draw((-1.64,-2.19)--(-1.64,-3.55), linewidth(1.2) + blue); draw((-1.64,-3.55)--(-3,-3.55), linewidth(1.2) + blue); draw((-3,-3.55)--(-3,-2.19), linewidth(1.2) + blue); draw((-1.64,-2.19)--(-0.28,-2.19), linewidth(1.2) + blue); draw((-0.28,-2.19)--(-0.28,-3.55), linewidth(1.2) + blue); draw((-0.28,-3.55)--(-1.64,-3.55), linewidth(1.2) + blue); draw((-1.64,-3.55)--(-1.64,-2.19), linewidth(1.2) + blue); draw((-0.28,-2.19)--(1.08,-2.19), linewidth(1.2) + blue); draw((1.08,-2.19)--(1.08,-3.55), linewidth(1.2) + blue); draw((1.08,-3.55)--(-0.28,-3.55), linewidth(1.2) + blue); draw((-0.28,-3.55)--(-0.28,-2.19), linewidth(1.2) + blue); draw((-3.68,1.25)--(-0.98,1.27), linewidth(1.2) + red); draw((-0.98,1.27)--(-0.98,-2.89), linewidth(1.2) + red); draw((-0.98,-2.89)--(-2.3,-2.89), linewidth(1.2) + red); draw((-2.3,-2.89)--(-2.3,-1.53), linewidth(1.2) + red); draw((-2.3,-1.53)--(0.44,-1.51), linewidth(1.2) + red); draw((0.44,-1.51)--(0.44,-0.09), linewidth(1.2) + red); draw((0.44,-0.09)--(-3.68,-0.09), linewidth(1.2) + red); draw((-3.68,-0.09)--(-3.68,1.25), linewidth(1.2) + red); /* dots and labels */ dot((-3.68,1.25),dotstyle); dot((-0.98,1.27),dotstyle); dot((-0.98,-2.89),dotstyle); dot((-2.3,-2.89),dotstyle); dot((-2.3,-1.53),dotstyle); dot((0.44,-1.51),dotstyle); dot((0.44,-0.09),dotstyle); dot((-3.68,-0.09),dotstyle); clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); /* end of picture */ [/asy][/asy] Now, we are supposed to remove alternate ones from these polygons, and there are two ways to do so (either first element of each polygon is removed or not). Thus the total number of ways to get the desired matrix will be two raised to the power of the number of polygons formed, which is what we required. Hence, done. $\blacksquare$ REMARKS: This is a beautiful problem, as the idea hidden is really intuitive, but only if you phrase it so. Without knowledge of adjacency matrices (basically one should be aware of the fact that digraphs are closely related to matrices), I guess this problem can be really difficult. Also, I guess this solution is more or less same as the first solution given by v_Enhance. However, I find it much more intuitive than that solution (maybe because I am not that well-versed with bipartite graphs ), since one can remove ones only in the manner given in the above solution.

yayups wrote: The idea from linear algebra is that the set of solutions is a vector subspace of $\mathbb{F}_2^N$, so its size is $2^r$, where $r$ is the dimension of that vector space. Can someone explain this to me? It does not seem like the set of solutions $(x_1, \dots, x_{N}) \in \mathbb{F}_2^N$ to the given set of $N$ equations $\{x_{e_i} + x_{e_j} =1\}$ is a subspace (e.g. $\vec{0}$ is not a solution, it's not closed under addition, etc.). Currently my understanding is that these equations represent an $N$ by $N$ matrix that, when applied to a variable vector $(x_1, \dots, x_{N})$, yields $\vec{1}$, but the solution set of $T\vec{v} = \vec{1}$ is not a subspace of $\mathbb{F}_2^N$. It would make more sense to be solving something of the form $T\vec{v} = \vec{0}$, in which case the kernel of a linear map is indeed a subspace, but I can't seem to make the connection. Thanks in advance.

rocketscience wrote: yayups wrote: The idea from linear algebra is that the set of solutions is a vector subspace of $\mathbb{F}_2^N$, so its size is $2^r$, where $r$ is the dimension of that vector space. Can someone explain this to me? I think it should instead say that the set of solutions $\mathcal{S}$ is an affine subspace of $\mathbb{F}_2^N$ (if nonempty). This still implies $|\mathcal{S}|$ is a power of 2, because an affine subspace is a shift of a vector subspace.

Remark: A A A A A A h. Interpret this as a directed graph $G$ where directed edges are roads and vertices are cities. Each vertex has indegree and outdegree $2$. Now take a directed edge $V_1 \to V_2$. Then, consider the edge $V_i \to V_2$ where $V_i$ is the other vertex that leads to $V_2$. Then, consider the edge $V_i \to V_j$ where $j \neq 2$. This way, given a single directed edge, we can find a unique cycle of directed edges such that adjacent directed edges are not directed in the same orientation (CW or CCW). Clearly all such cycles must be even because the orientation of the original edge changes every edge so it must change an even number of times to go back to the original orientation. Hence, in the original graph $G$, we can partition all vertices and directed edges into such disjoint even cycles described above. Note that these cycles could be self intersecting or hit some vertex more than once. Claim: If there are $k$ such cycles, then our answer is $2^k$. Proof: We must remove exactly half of the edges in each cycle. Two adjacent edges cannot be removed since some vertex will have either indegree or outdegree zero. The only way to remove half the edges without removing any two adjacent is removing every other edge, and since there are 2 possible distinct starting points, there are $2$ ways to remove edges of each cycle. There are $k$ cycles, and thus $2^k$ ways of removal, as desired. $\square$ Clearly each graph $G$ has at least one vertex and thus at least one cycle, and we are done. $\blacksquare$

Kaguya sama love is war Let's say we closed a road from town $A$ to town $B$. Let the other road from town $A$ go to $C$, and the other road going to $B$ be from $D$. Then, since these two roads can not be chosen, we have to choose the road going from another town to $C$, and a road going from $D$ to another town. We can keep doing this until we repeat a town; this results in a set of towns $S$ such that each town has one road going into it that is closed. Define this set as the kaguya set of road $AB$. This must form a cycle because, if it didn't, it must repeat somewhere, and that would imply 3 roads going into one town, a contradiction. Again, consider the town $A$; there are two ways to choose the first road, and it will result in the same kaguya set. Then, for the rest of the towns, we can not close a road going into the kaguya set, so all of those roads can be ignored. We can now consider another town, of which there are two ways to choose the roads, and remove all of its the roads going into its kaguya set. Clearly these two kaguya sets are disjoint. We can keep doing this, and since at each step there are two ways to remove it, it results in a power of two ways to close the roads.

Very nice problem. Consider the obvious directed graph interpretation, and call the directed graph $G_{\text{full}}$. Call an opposite-cycle a cycle of edges where consecutive edges in the cycle are of opposite orientation. Claim: The edges of $G_{\text{full}}$ can be partitioned into opposite-cycles. Proof: Actually, we claim any directed graph $G$ which has each indegree and outdegree is either $0$ or $2$ can be partitioned into opposite-cycles. Induct on the number of edges, the base case of the empty graph being partitioned into nothing. The following algorithm aims to find an opposite-cycle in $G$: Start with a vertex $v_1$ with nonzero outdegree. Traverse $v_1\to v_2$. Now, $\text{indeg } v_2=2$ since it is at least one, so there is a unique $v_3$ such that $v_3 \leftarrow v_2$. Traverse $v_1 \to v_2 \leftarrow v_3$. Now, $\text{outdeg } v_3=2$ since it is at least one, so there is a unique $v_4$ such that $v_3\to v_4$. Traverse $v_1\to v_2 \leftarrow v_3 \to v_4$. $\ldots$ and so on. The key above was that since the in/out-degree is nonzero, it is exactly $2$. The algorithm will not be ``stuck'' since whenever we come $v\to v'$, then we can go out also $v\to v' \leftarrow v''$. The algorithm is only stuck when we come back to $v_1$ since we initially ``used up'' one of its outdegrees. But in particular if we cannot end with $v_1 \rightarrow \cdots \rightarrow v_1$, since we can go out of $v_1$ again. So the above algorithm will terminate only when we have $v_1\to \cdots \leftarrow v_1$. In particular, the cycle created has even length. Now, delete the opposite-cycle found. For each vertex of the opposite-cycle, we used up $0$ or $2$ outs and $0$ or $2$ ins. So deleting the cycle preserves the fact that all indegrees and outdegrees are $0$ or $2$, and now we induct down. This finishes the induction and proves the generalized claim. Therefore, in particular, the edges of $G_{\text{full}}$ can be partitioned into opposite-cycles. $\blacksquare$ Suppose a specific edge $e$ is deleted. Then every other edge in the opposite-cycle that $e$ is part of must also be deleted, and the other half of the edges must be kept. This is because if we delete two consecutive edges of an opposite-cycle, say $v_1\to v_2 \leftarrow v_3$ and we delete $v_1\to v_2$ and $v_2\leftarrow v_3$, then the indegree of $v_2$ will have decreased from $2$ to $0$, which is bad since we want all the indegrees and outdegrees to be $1$. Therefore, we can delete at most half of the edges in each opposite-cycle, which means actually that in each opposite-cycle, exactly half the edges are deleted, and in particular, every other edge is deleted.

An opposite-cycle: Red means deleted edge Thanks to nukelauncher for help with the diagram! There are $2$ choices for each opposite-cycle for which evenly-spread-half of the cycle that is deleted. Any combination of these choices over the opposite-cycles will give us the final desired outcome since either choice makes the vertex lose $1$ of the $2$ ins or outs, and are independent in this regard. So the answer is $2^{\text{\#(opposite cycles)}}$, and we are done.

Use the obvious directed graph interpretation. Instead of deleting edges, we color them blue, and color the remaining ones red. Now perform the following algorithm: Take any edge and color it arbitrarily, WLOG red Take the edge which points into the same vertex as the edge selected in the previous step: it must be blue Take the edge which points away from the same vertex as the edge selected in the previous step: it must be red And so on, until we get back to the original edge. Because of the directions of the edges, there will not be any contradiction in the coloring. Then repeat the algorithm starting with any edge that is uncolored up to now. Then the number of ways is $2^m$ where $m$ is the number of times we go through the algorithm, the end.

Suppose $A_1\to B_1$ is an edge. Let $A_2$ be the second vertex with $A_2\to B_1$ and suppose $B_2$ is the second vertex with $A_2\to B_2$. Using this rule, we can define $A_i, B_i$ recursively. Notice that if $B_j=B_i$ for some $j>i$ then $A_j=A_i$ or $A_{i+1}$ and so $A_j=A_k$ for some $j>k$. Let $j$ be the smallest $j$ such that $A_j=A_k$ for some $j>k$, then obviously $k=1$ and $B_{j-1}$ is the other vertex where there is an edge from $A_1$ to it. Now we create two sets of vertices $A_1,...,A_{j-1}$ and $B_1,...,B_{j-1}$ where $A_i\to B_i,B_{i-1}$. We call such a pair of sets a block. Repeating this procedure then all vertices are divided into different blocks. Now obviously in each block there are two ways to delete the edges, namely by deleting the edges $A_i\to B_i$ or deleting all the edges $A_i\to B_{i-1}$, therefore the number of ways of deleting the edges is $2^a$, where $a$ is the number of blocks, this completes the proof.

v_Enhance wrote: In the nation of Onewaynia, certain pairs of cities are connected by one-way roads. Every road connects exactly two cities (roads are allowed to cross each other, e.g., via bridges), and each pair of cities has at most one road between them. Moreover, every city has exactly two roads leaving it and exactly two roads entering it. We wish to close half the roads of Onewaynia in such a way that every city has exactly one road leaving it and exactly one road entering it. Show that the number of ways to do so is a power of $2$ greater than $1$ (i.e.\ of the form $2^n$ for some integer $n \ge 1$). Victor Wang

Interpret the problem as a directed graph $G$ on $n$ vertices where each vertex has indegree $2$ and outdegree $2.$ Claim: $G$ can be partitioned into disjoint cycles whose edges have opposite orientation. Proof: Consider an arbitrary edge $v_1 \to v_2.$ Clearly, this edge can be apart of at most $1$ cycle, since we must have the path $v_1 \rightarrow v_2 \leftarrow v_3 \dots,$ and since $v_2$ has indegree $2,$ no other cycles can contain both $v_1 \rightarrow v_2$ and $v_3 \rightarrow v_2.$ Then, perform the following steps: Starting at $v_1,$ go to $v_2.$ Then, consider the unique vertex $v_3$ such that there is an edge $v_3 \to v_2.$ Draw this edge. From $v_3,$ consider the unique vertex $v_4$ such that there is an edge $v_3 \to v_4.$ And so on Suppose this process never results in a cycle, and ends in vertex $v_k.$ However, this implies that $v_k$ has degree $1$ in the cycle, meaning we can find another vertex $v_j \in G$ such that $v_k$ and $v_j$ have a road in between them, of the correct orientation. Eventually, this $v_j$ must be some vertex in the sequence of vertices $v_1 \rightarrow v_2 \leftarrow v_3 \rightarrow v_4 \dots,$ meaning that there must be a cycle. Furthermore, due to parity reasons, this cycle must be of even length since each otherwise there would be some sequence of vertices $v_i \to v_{i+1} \to v_{i+2}.$ To finish, suppose we delete some arbitrary edge $E$ in $G.$ This must be in exactly one cycle $v_1 \rightarrow v_2 \leftarrow v_3 \dots \rightarrow v_1.$ Suppose we delete $v_1 \rightarrow v_2.$ Then, we must keep $v_2 \leftarrow v_3,$ but then discard $v_3 \rightarrow v_4$ since each vertex has indegree/outdegree $1.$ That is, by deleting an edge in a cycle, we must delete exactly half of the edges in the cycle in order to have a series of vertices with in/outdegree $1.$ Furthermore, we must delete alternate edges. Thus, for each cycle, there are exactly $2$ ways to delete edges such that the resulting subgraph has every vertex with in/outdegree $1.$ Since each cycle is distinct, suppose there are $k$ such cycles. Then, as there are $2$ ways for each cycle, there must be $2^k$ ways in total to remove edges, and we are done.

Claim: There exists at least two routing plans. Proof: Create a bipartite graph with two vertices $u_i,v_i$ corresponding to each vertex $i$ in the original graph. For each directed edge $i\rightarrow j$, draw an undirected edge between $u_i$ and $v_j$. Since the degree of each vertex is $2$, there exists an Eulerian cycle; simply taking every second edge of the Eulerian cycle in two different ways suffices. Now, create two bits $x_i,y_i$ corresponding to each vertex $i$, indicating which edge outgoing from $i$ is in the routing plan. Each routing plan has $x_i\oplus y_i=1$ for each $i$, hence the XOR of any two routing plans is a solution to $x_i\oplus y_i=0$ for each $i$. The set of routing plans then form an affine subspace of $\mathbb{F}_{2}^{2\cdot |\text{Onewaynia}|}$; combined with our claim, this implies the desired.

Sketch: The idea is that we can partition the graph into even "alternating" cycles (i.e. the adjacent edges have "opposite" orientations; to see this, take some edge $v_1 \rightarrow v_2$, then there is an unique $v_3$, such that $v_3 \rightarrow v_2$, etc. until you get back to $v_1$ and get a cycle). Now there are exactly two ways to delete half of the edges in each cycle (we have to delete edges in an alternating manner), so we are done.

Assign to every city of Onewaynia a vertex of digraph $O$ and to every one-way road it's directed edge. Claim. $O$ can be uniquely partitioned onto (undirected) cycles, with every two adjacent edges going both from or into the common vertex. Proof. Take any edge $\overrightarrow{v_1v_2}$ until it lefts; there is exactly one vertex $v_3$ in $O$ with ingoing edge $\overrightarrow{v_2v_3}.$ Continuing we get the sequence of vertices $v_n,$ which should cycle in desired way $\Box$ Now observe that in all $n$ cycles we should remove half of edges, which can be done in exactly $2^n$ ways.

The problem equivalently asks to show that there are $2^n$ partitions of the edges of a simple 2-regular digraph $G$ into two (distinguishable) 1-regular digraphs. Construct a simple, undirected bipartite graph $G'$ such that The bipartite vertex partitions are two copies of $V(G)$: $V_1$ and $V_2$, essentially corresponding to "in-vertices" and "out-vertices" respectively. If $a \in V_1$ and $b \in V_2$, then we draw edge $\overline{ab}$ iff $a \to b$ in $G$. Then every vertex in $G'$ has degree $2$. As such, it can be partitioned into cycles (start at a vertex, move along an edge, and keep on going until we hit a vertex we've arrived at before: it must be the starting vertex, otherwise we get a vertex with degree 3), which are even because $G'$ is bipartite. It is clear that each cycle admits $2$ partitions, independently of the other cycles—the choice of partition set must alternate. Then we have $2^{\text{\# cycles}}$ partitions of $G$ which is the desired result. $\blacksquare$

Call two roads related if they emanate from the same city, or they have the same destination. Notice that for any road, it has two relatives. We color a road green if we are keeping it, and red if we are deleting it. Notice that if roads are relatives of each other, they must be different colors. Notice that if we color a certain road a color (there are $2$ ways to do this) then a subset of the roads' colors will be determined. Call this subset $S$. Notice that if a road is in $S$, then its relatives are in $S$, and if a road is not in $S$, then its relatives are not in $S$. Therefore we can simply remove $S$ from the picture and induct down. Now notice there are $2$ ways to color $S$, so the number of ways is clearly a power of $2$ which is greater than $1$.

Claim: At least one solution exists. Proof. Greedily decompose into disjoint cycles. $\blacksquare$ Claim: We can embed the solutions to this as a subspace of ${\mathbb F}_2^{2n}$. Proof. Take a solution $S$. Define $2n$ indicator variables for each city and input or output to mark whether its the edge in $S$. Thus, $S$ is the identity element of this solution. We claim that adding any two solutions $A$ and $B$ gives another solution. Evidently, the new vector gives each city indegree and outdegree $1$. It remains to show that this is consistent on indicator variables for each edge. This follows since for any active edge in $A$ or $B$, the two corresponding indicator variables are in the same state. Thus, their sum also has a equal indicator variable as desired. $\blacksquare$ As such, if the subspace has a basis $b_1, b_2, \dots b_m$, then it has $2^m$ solutions.

IAmTheHazard wrote: The problem equivalently asks to show that there are $2^n$ partitions of the edges of a simple 2-regular digraph $G$ into two (distinguishable) 1-regular digraphs. Construct a simple, undirected bipartite graph $G'$ such that The bipartite vertex partitions are two copies of $V(G)$: $V_1$ and $V_2$, essentially corresponding to "in-vertices" and "out-vertices" respectively. If $a \in V_1$ and $b \in V_2$, then we draw edge $\overline{ab}$ iff $a \to b$ in $G$. Then every vertex in $G'$ has degree $2$. As such, it can be partitioned into cycles (start at a vertex, move along an edge, and keep on going until we hit a vertex we've arrived at before: it must be the starting vertex, otherwise we get a vertex with degree 3), which are even because $G'$ is bipartite. It is clear that each cycle admits $2$ partitions, independently of the other cycles—the choice of partition set must alternate. Then we have $2^{\text{\# cycles}}$ partitions of $G$ which is the desired result. $\blacksquare$ Linear algebra over $\mathbb{F}_2$ solution: for each edge $e$ define a variable $x_e$ which equals $1$ if it is included and $0$ otherwise, so we wish to count the number of solutions such that for every vertex $v$, if $a$ and $b$ are the in-edges to $v$ and $c$ and $d$ are the out-edges, we have $x_a+x_b=1$ and $x_c+x_d=1$. For "linear algebra reasons" we automatically get that the number of solutions is either a power of $2$ or $0$, with the latter only occurring if we can sum a number of equations to get $0=1$. However, this is impossible, since we have to sum the same amount of "in-edge equations" and "out-edge equations" to include each edge an even number of times. Furthermore, since solutions come in pairs $(x_1,x_2,\ldots)$ and $(x_1+1,x_2+1,\ldots)$, the desired conclusion follows. $\blacksquare$

We can represent the road system in Onewaynia with an undirected biparte graph, $n$ vertices on each side, where $n$ is the number of towns. One side is the departures side, and the other side is the arrivals side; we draw an undirected edge from each departure city to the two arrival cities. The answer is just $2^k$ where $k$ is the number of cycles in this biparte graph. First of all, clearly the biparte graph is composed of disconnected cycles, since each vertex has degree $2$. Our task at hand with this bijection is to remove half the edges so that every vertex has degree $1$; this means every vertex is paired with another one. Since cycles in biparte graphs have even lengths, we have two choices as to how we remove edges in each cycle.

The idea here is to look at anticycles, or cycles that have edges which alternate orientation. Claim. We can partition $G$ into anticycles, each of which has even length. Proof. Just do it greedily! We're guaranteed we only arrive at a previous vertex once after an even number of edges because every vertex has indegree and outdegree exactly $2$. $\blacksquare$ Now for every anticycle, we have to choose to delete exactly half of the edges to ensure the indegree and outdegree of every vertex is exactly $1$. Thus the number of choices is $2$ to the number of anticycles, hence the result.

Nice question My solution is same as pi271828

Let the directed graph of Onewaynia be $G$. Consider the (possibly non-simple) undirected graph $H$ such that $u$ and $v$ are connected by one edge for each $w$ such that $u\ne v$, $w\rightarrow u$, and $w\rightarrow v$ in $G$. The idea is that for each edge in $H$, we may choose one of its vertices. This corresponds to having the vertex in $G$ corresponding to the edge connecting to that vertex. We want to choose one of each vertex in $H$. Clearly this guarantees an indegree and outdegree of $1$ for edge vertex in $G$. Note that every vertex has degree exactly $2$ then. So each connected component is either a cycle or a double edge, in which there are two ways to choose. So we win! $\blacksquare$