Yeesh, why not just use the graph theory terms: Reformulated problem wrote: Let $G$ be a finite tournament. Say a set of directed paths is edge-disjoint if no two paths share a common edge. (Directed paths may not visit a vertex more than once.) Choose two distinct vertices $v$ and $w$ in $G$. Let $M$ be the largest possible size of an edge-disjoint set of directed paths which all go from $v$ to $w$. Similarly, let $N$ be the largest possible size of an edge-disjoint set of directed paths which all go from $w$ to $v$. Prove that $M = N$ if and only if $v$ and $w$ have the same outdegree. Partition all the vertices other than $v$ and $w$ into four groups $X$, $Y$, $S$, $T$, as shown depending on whether they point to $v$/$w$ or not. [asy][asy] size(10cm); pair v = (-4,0); pair w = ( 4,0); dot("$v$", v, dir(180), blue); dot("$w$", w, dir(0), blue); draw(box( (-2,-1.5), (2,-0.5) ), red ); draw(box( (-2, 0.5), (2,1.5) ), red ); draw(box( (-2,2), (2,3) ), deepgreen ); draw(box( (-2,-2), (2,-3) ), deepgreen ); draw(v--w, blue, EndArrow, Margins); draw(v--(-2,1), red, EndArrow, Margins); draw((2,1)--w, red, EndArrow, Margins); draw(w--(2,-1), red, EndArrow, Margins); draw((-2,-1)--v, red, EndArrow, Margins); label("$X$", (2,1.5), dir(0), red); label("$Y$", (2,-1.5), dir(0), red); label("$S$", (2,3), dir(0), deepgreen); label("$T$", (2,-3), dir(0), deepgreen); draw((-2,2.5)--v, deepgreen, EndArrow, Margins); draw((2,2.5)--w, deepgreen, EndArrow, Margins); draw(w--(2,-2.5), deepgreen, EndArrow, Margins); draw(v--(-2,-2.5), deepgreen, EndArrow, Margins); pair x = (1.2, 1.1); dot("$x$", x, dir(90)); draw(v--x, dashed, EndArrow(TeXHead), Margins); draw(x--w, dashed, EndArrow(TeXHead), Margins); [/asy][/asy] The main content of the proof is this: Claim: In any maximal set $\mathcal P$ of edge-disjoint paths from $v$ to $w$, we may assume without loss of generality that every path of the form $v \to x \to w$ for $x \in X$ appears. Proof. Replacement argument: If neither $v \to x$ or $x \to w$ are in $\mathcal P$, this contradicts maximality. If exactly one of them is present, say $v \to x$, replace the path $v \to x \to \text{blah} \to w$ with $v \to x \to w$. Suppose both $v \to x$ and $x \to w$ are used, say $v \to x \to \text{blah}_1 \to w$ and $v \to \text{blah}_2 \to x \to w$. Replace with $v \to x \to w$ and $v \to \text{blah}_2 \to \text{blah}_1 \to w$. $\blacksquare$ Assume we are in the situation of the claim. The remaining paths from $v$ to $w$ of the form $v \to t \to \text{blah} \to s \to w$ are in bijection with paths $w \to s \to \text{blah} \to t \to v$. Thus, if we let $K$ be the maximum number of edge-disjoint paths of this form, we conclude \begin{align*} M &= 1 + |X| + K \\ N &= |Y| + K. \end{align*}So $M=N$ if and only if $1+|X|=|Y|$, as needed.

Proposed by Warut Suksompong, Thailand

Represent the problem as a Tournament $G$. Choose 2 vertices $a$ and $b$. Let $A = \{ v : (a,v) \in E(G)\}$, define $B$ similarly. Let $C = A \cap B$. Focus on $N_{AB}$. Consider the vertices $v \in A/C$. Logically, when maximizing $N_{AB}$ all $|A| - |C|$ paths $a \rightarrow v \rightarrow b$ can be taken because it won't really affect other paths. Now, look at the vertices $u \in C$. Now, if there is a path connecting $u$ to $b$. The path must involve a vertex $t \in V(G)/(A \cup B)$ because all vertices $x \in A$, $(x,b)$ is either not an edge or taken. But, both $(t,a)$ and $(t,b)$ are edges. So, the number of paths involving $C$ is equal for both sides. Hence, \[ N_{AB} = N_{BA} \iff |A| - |C| = |B| - |C| \iff |A| = |B| \]

Using the reformulated problem: Reformulated problem wrote: Let $T$ be a finite tournament. Say a set of directed paths is edge-disjoint if no two paths share a common edge. (Directed paths may not visit a vertex more than once.) Choose two distinct vertices $v$ and $w$ in $T$. Let $M$ be the largest possible size of an edge-disjoint set of directed paths which all go from $v$ to $w$. Similarly, let $N$ be the largest possible size of an edge-disjoint set of directed paths which all go from $w$ to $v$. Prove that $M = N$ if and only if $v$ and $w$ have the same outdegree. - Assign a capacity $1$ to each flow capacity of each directed edge, in the direction that it points. - Let $\text{flow}(v, w)$ equal the maximal flow from $v$ to $w$. By the Max-flow Min-cut Theorem, which holds for integer capacities and flows, we know that there exists some partition of $T$, which we will call $A$ and $B$ (with $v$ inside $A$ and $w$ inside $B$) such that the total capacity coming from $A$ to $B$ equals $\text{flow}(v, w)$. We will define a function $\text{cut}(X, Y)$ to be the total capacity of edges coming from $X$ to $Y$ for any partition $X, Y$ of $T$. Label each vertex in $A$ which is not $v$ with numbers $a_1, a_2, \cdots a_{|A| - 1}$. Then $\text{flow}(v, w) = \text{cut}(A, B) = \text{deg}^{+}(v) + (\sum_{i = 1} ^{|A| - 1} \text{deg}^{+} (a_i)) - \binom{|A|}{2}$. But notice that $$\text{cut}((A - v + w), (B - w + v)) = \text{deg}^{+}(w) + (\sum_{i = 1} ^{|A| - 1} \text{deg}^{+} (a_i)) - \binom{|A|}{2}$$, where $A - v + w$ represents the set obtained by replacing $v$ with $w$ in $A$, and $B - w + v$ defined analogously. So $$\text{flow}(w, v) \leq \text{cut}((A - v + w), (B - w + v)) = \text{deg}^{+}(w) + (\sum_{i = 1} ^{|A| - 1} \text{deg}^{+} (a_i)) - \binom{|A|}{2} = \text{cut}(A, B) = \text{flow}(v, w) - \text{deg}^{+}(v) + \text{deg}^{+}(w)$$. By symmetry, $\text{flow}(v, w) \leq \text{flow}(w, v) - \text{deg}^{+}(w) + \text{deg}^{+}(v)$. If $\text{deg}^{+}(v) = \text{deg}^{+}(w)$, then we conclude that $\text{flow}(w, v) = \text{flow}(v, w)$ so $M = N$. If $\text{deg}^{+}(v) > \text{deg}^{+}(w)$, then $$\text{flow}(w, v) \leq \text{flow}(v, w) + \text{deg}^{+}(w) - \text{deg}^{+}(v) < \text{flow}(v, w)$$ so $M > N$. $\square$ Remark 1: The key observation with this approach is that the total number of edges coming from a subgraph $A$ of a tournament to itself is equal to $\binom{|A|}{2}$, which does not change when replacing a vertex. Remark 2: The Max-flow Min-cut theorem's proof for integer capacities and flows was presented in the Red classroom two days before this problem showed up on one of our tests.

Let's first show the following: Lemma. There exists a diverse collection of path from $A$ to $B$ with maximal number, such that all paths in the form of $A\to v\to B$ are included (here $\to$ means directed edge). Proof. Let's consider any such diverse collection $\mathcal{C}$ with $N_{AB}$ such paths. Consider any $v$ such that $A\to v\to B$ is not included. We consider these cases: \textbf{Case 0.} Neither $A\to v$ nor $v\to B$ are in any path contained in $\mathcal{C}$. Then we may even add $A\to v\to B$ directly. \textbf{Case 1a.} $A\to v$ belongs to some path contained in $\mathcal{C}$ but not $v\to B$. Now, if the path is $A\to v\Rightarrow B$ where $\Rightarrow$ denotes a path from $v$ to $B$, then we may replace the paths in $v\Rightarrow B$ to $v\to B$, that gives $A\to v\to B$. \textbf{Case 1b.} $v\to B$ belongs to some path contained in $\mathcal{C}$ but not $A\to v$. Similar case: if this is $A\Rightarrow v\to B$ we may replace $A\Rightarrow v$ with $A\to v$. \textbf{Case 2.} Both $A\to v$ and $v\to B$ are part of the collection but in different paths. This means there exists the two paths \[ A\to v\Rightarrow B\qquad A\Rightarrow v\to B \]such that $A\Rightarrow v$ and $v\Rightarrow B$ are two paths with disjoint roads, and also disjoint from edges $A\to v$ and $v\to B$. Call these two paths $U$ and $V$. Thus $A\Rightarrow v\Rightarrow B$ does contain a path that's subset of $U\cup V$ (basically, take the union, and remove all cycles), so we may replace the two original paths with this path and $A\to v\to B$. So considering all cases above it means we can indeed include $A\to v\to B$ into the collection, for all such eligible $v$. Now, referencing to towns $A$ and $B$, each vertex can be categorized into exactly one of the following: $\vec{AB}$-type ($A\to v\to B$), $\vec{BA}$-type ($B\to v\to A$), in-type ($A\to v\leftarrow B$) and out-type ($A\leftarrow v\to B$). Regardless of the members of the collection, either $A\to B$ or $B\to A$ must also be in a maximally-constructed diverse collection. By above we may assume that we can construct a maximally constructed path by including all paths of the form $A\to v\to B$ for all $\vec{AB}$-type vertices $v$. Thereafter, any new path starting with $A\to v'$ must have $v'$ an in-type and any new path ending with $v''\to B$ must have $v''$ an out-type. Now we claim the following: Lemma. A maximally diverse collection of paths from $A$ to $B$ containing $A\to v\to B$ for all $\vec{AB}$-type vertices $v$. Then the remaining paths are the maximal possible-sized set of paths in the form $A\to v_1\Rightarrow v_2\to B$, where $v_1$ is in-type, $v_2$ is out-type, and any two paths of the form $v_1\Rightarrow v_2$ have disjoint paths and starting and ending vertices. Proof. The disjoint edges condition follows from definition; the disjoint starting and ending vertices follow from $A\to v_1$ and $B\to v_2$ condition. Conversely, if we have such a collection of $A\to v_1\Rightarrow v_2\to B$, then these collections have edges disjoint from $A\to v\to B$, so such addition is valid. It therefore means we can pick the collection with maximum number of paths. To finish, denote $C_{AB}$ as the quantity described in Lemma \ref{lemma_c4b}. Such paths do not depend on $A$ and $B$ other than that we have in- and out-types of edges, so $C_{AB}=C_{BA}$. Therefore, \[ N_{AB} = C_{AB} + 1\{A\to B\} + |\{v: \vec{AB}-\text{type}\}| \qquad N_{BA} = C_{BA} + 1\{B\to A\} + |\{v: \vec{BA}-\text{type}\}| \]where $1\{A\to B\}$ means there's a directed edge $A\to B$. so $N_{AB}-N_{BA} = 1\{A\to B\} + |\{v: \vec{AB}-\text{type}\}| - (1\{B\to A\} + |\{v: \vec{BA}-\text{type}\}|)$. Given also that the out degree of $A$, $\text{out}(A)$ is given by $1\{A\to B\} + |\{v: \vec{AB}-\text{type}\}| + |\{v: \text{out-type}\}|$, we have \[ N_{AB} - N_{BA} = \text{out}(A) - \text{out}(B) \]as desired.

Nice non-standard graph. Here goes my solution: Divide the vertices into 4 groups in terms of what are the orientations of the edges between the vertex and $a,b$. Let $M$ be the type $a\rightarrow m \rightarrow b$, $N$: $a \rightarrow n \leftarrow b$, $P$ : $a\leftarrow p \leftarrow b$ and finally $Q$: $a \leftarrow q \rightarrow b$. Firstly, we consider $N_{ab}$; the paths in it have a vertex after $a$ either from $M$, or from $N$. We claim the following: $\textbf{Lemma}$: We can assume WLOG all paths $a \rightarrow m \rightarrow b$ are in $N_{ab}$. Similar assumption can be made for $N_{ba}$ . $\textbf{Proof}$: Suppose not; assume $l=a\rightarrow m \rightarrow b$ is not. Hence there is either a path in the set containing $a\rightarrow m$, or a path containing $m\rightarrow b$, or both type of paths (these facts are due to the maximality of the set). If there is only one path intersecting $l$, we can interchange them. If there are both types of paths, we take them and make two new paths from them, having the same set of edges: the one is $l$, the other is composed by the two paths from $a$ to $m$ and from $m$ to $b$. That interchange doesn't change anything, so we have proven the lemma. $\square$ Now, it's easy to finish. Indeed, note that $outdeg(a)=|M|+|N|, outdeg(b)=|P|+|N|$, so they are equal iff $|M|=|P|$. Note that the other paths from $N_{ab}$ (not the ones from the Lemma) are from the following type: $a\rightarrow n\rightarrow...\rightarrow q \rightarrow b$, but it's easy to see that a similar path using the same pair $(n,q)$ and the path between them is also valid for $N_{ba}$: $b\rightarrow n \rightarrow...\rightarrow q\rightarrow a$, so $|N_{ab}|=|N_{ba}|$ iff $|M|=|P|$ and we are done. $\blacksquare$

v_Enhance wrote: The kingdom of Anisotropy consists of $n$ cities. For every two cities there exists exactly one direct one-way road between them. We say that a path from $X$ to $Y$ is a sequence of roads such that one can move from $X$ to $Y$ along this sequence without returning to an already visited city. A collection of paths is called diverse if no road belongs to two or more paths in the collection. Let $A$ and $B$ be two distinct cities in Anisotropy. Let $N_{AB}$ denote the maximal number of paths in a diverse collection of paths from $A$ to $B$. Similarly, let $N_{BA}$ denote the maximal number of paths in a diverse collection of paths from $B$ to $A$. Prove that the equality $N_{AB} = N_{BA}$ holds if and only if the number of roads going out from $A$ is the same as the number of roads going out from $B$. Proposed by Warut Suksompong, Thailand Great problem! Shows the beauty of GT. Define the set \(\mathcal{A}\) as the number of outdegrees from vertex \(a\), and set \(\mathcal{B}\) analogously. Define \[C=\mathcal{A}\cap\mathcal{B}\]Now, notice that all the vertices \(v\) in the set \(\mathcal{A}/C\) have the path \(a\rightarrow v\rightarrow b\). I claim that, we can assume \(N_{AB}\) contains the paths \(a\rightarrow v\rightarrow b\) where \(v\in\mathcal{A}/C\) without losing generality. This holds simply because if a path in \(N_{AB}\) ends with \(v\rightarrow b\) where the path is now \(a\rightarrow v\rightarrow b\), then we can let \(v\) be, and if there is no such path, we can simply add \(a\rightarrow v\rightarrow b\) into \(N_{AB}\), since it wont affect the definition of \(N_{AB}\). That means, whether we include all the paths \(a\rightarrow v\rightarrow b\) or not, \(N_{AB}\) will remain the same, so without loss of generality, we assume that all such paths are included in \(N_{AB}\). Similarly for \(N_{BA}\), so we have \(\lvert\mathcal{A}\rvert-\lvert C\rvert\) paths in \(N_{AB}\) and \(\lvert\mathcal{B}\rvert-\lvert C\rvert\) paths in \(N_{AB}\) first. Now, assume that there is a path that goes like this: \[a\rightarrow u\rightarrow\hdots\rightarrow v\rightarrow b\]where \(u\in C\). That means, \(v\) is in the set of vertices which has both indegrees to \(a\) and \(b\). But then that means \[b\rightarrow u\rightarrow\hdots\rightarrow v\rightarrow a\]is a path as well! And moreover this doesnt intersect with any roads from the first set of paths we mentioned earlier. That means, apart from those set of paths, if there exists a path in \(N_{AB}\) passing from a vertex \(u\in C\), then there exists a path in \(N_{BA}\) that passes from \(b\) to \(a\), which means the set \(X\) that contains vertices from \(C\) which are the next vertex in a path contained in \(N_{AB}\) has the same cardinality with that contained in \(N_{BA}\). Therefore, \[N_{AB}=N_{BA}\iff\lvert\mathcal{A}\rvert-\lvert C\rvert=\lvert\mathcal{B}\rvert-\lvert C\rvert\]and we are done. $\blacksquare$

v_Enhance wrote: Assume we are in the situation of the claim. The remaining paths from $v$ to $w$ of the form $v \to t \to \text{blah} \to s \to w$ are in bijection with paths $w \to s \to \text{blah} \to t \to v$. I think It should be $w \to t \to \text{blah} \to s \to v$ right?

Rephrased problem wrote: In a tournament $G$ with $n$ vertices, prove that $N_{AB}=N_{BA}$ if and only if $\text{deg}_{\text{out}} (A)=\text{deg}_{\text{out}} (B)$. WLOG, let the edge between $A$ and $B$ be $A\rightarrow B$. To get rid of this special edge in our argument, add a vertex $u$ in the middle of this edge so that it becomes $A\rightarrow u\rightarrow B$. (Note that $u$ is connected to only $A$ and $B$.) First, we categorize the vertices $v\neq A,B$ in $G$ into the following $4$ types: Type 1: $A\rightarrow v\rightarrow B$ Type 2: $A\leftarrow v\leftarrow B$ Type 3: $A\rightarrow v\leftarrow B$ Type 4: $A\leftarrow v\rightarrow B$ Claim 1: There exists a maximal diverse group of path from $A$ to $B$, denoted $S_{AB}$, such that for all vertices $v$ of type $1$, $A\rightarrow v\rightarrow B$ is a path in $S_{AB}$. Proof: Pick a $S_{AB}$, we will modify it as follows: for each type-$1$ vertex $v$, if a path $A\rightarrow v\rightarrow B$ is already in $S_{AB}$, do nothing. if $A\rightarrow v$ and $B\rightarrow v$ are both not in $S_{AB}$, we can add $A\rightarrow v\rightarrow B$ to $S_{AB}$, a contradiction to its maximality. if exactly one of $A\rightarrow v$, $B\rightarrow v$ is in $S_{AB}$, delete the path containing it and add $A\rightarrow v\rightarrow B$ to $S_{AB}$ instead. if both $A\rightarrow v$ and $B\rightarrow v$ are in $S_{AB}$ but not the same path, let the two paths be $A\rightarrow v\rightarrow\text{group of edges 1} \rightarrow B$ and $A\rightarrow\text{group of edges 2}\rightarrow v\rightarrow B$. We then rearrange them to $A\rightarrow v\rightarrow B$ and $A\rightarrow\text{group of edges 2}\rightarrow \text{group of edges 1}\rightarrow B$. We can check that the resulting graph will satisfy the claim. $\blacksquare$ Claim 2: There exists a maximal diverse group of path from $B$ to $A$, denoted $S_{BA}$, such that for all vertices $v$ of type $2$, $B\rightarrow v\rightarrow A$ is a path in $S_{BA}$. Proof: Similar to the previous claim. $\blacksquare$ By choosing $S_{AB},S_{BA}$ according to claim 1 and 2, we see that all other paths in $S_{AB}$ must start with $A\rightarrow v_3\ (\text{a type-3 vertex})$ and end with $v_4\ (\text{a type-4 vertex})\rightarrow B$. Similarly, all other paths in $S_{BA}$ must start with $B\rightarrow v_3\ (\text{a type-3 vertex})$ and end with $v_4\ (\text{a type-4 vertex})\rightarrow A$. Let $M_{AB},M_{BA}$ be the number of these paths in $S_{AB},S_{BA}$, respectively. We now show the following: Claim 3: $M_{AB}=M_{BA}$. Proof: Remove all paths contributing to $M_{BA}$ from $S_{BA}$. For each path $$A\rightarrow v_3\rightarrow \text{group of edges}\rightarrow v_4\rightarrow B$$in $S_{AB}$, we now construct the path $$B\rightarrow v_3\rightarrow \text{the same group of edges}\rightarrow v_4\rightarrow A$$in $S_{BA}$. This implies that $M_{BA}\ge M_{AB}$. By repeating the same process using paths in $S_{BA}$ to rewrite paths in $S_{AB}$, we also get $M_{AB}\ge M_{BA}$, implying the desired result. $\blacksquare$ Let $N_1,N_2,N_3$ be the number of type-1, type-2, type-3 vertices in $G$, respectively. Using claim 3, we have \begin{align*} N_{AB}-N_{BA} &= (M_{AB}+N_1)-(M_{BA}+N_2)\\ &= (N_1+N_3)-(N_2+N_3)\\ &=\text{deg}_{\text{out}}(A)-\text{deg}_{\text{out}}(B), \end{align*}as needed.

v_Enhance wrote: Assume we are in the situation of the claim. The remaining paths from $v$ to $w$ of the form $v \to t \to \text{blah} \to s \to w$ are in bijection with paths $\color{red}w \to s \to \text{blah} \to t \to v$. Shouldn't this be $w \to t \to \text{blah} \to s \to v$?

Use Evan's restated problem statement. Partition $T \setminus \{v,w\}$ into $A,B,X,Y$, such that $x \to v,w$ for all $x \in A$, $x \leftarrow v,w$ for all $x \in B$, $v \to x \to w$ for all $x \in X$, and $w \in x \in v$ for all $x \in Y$. Also WLOG let $v \to w$. The key idea is the following: Claim: If $S$ is a maximal set of edge-disjoint paths from $v$ to $w$, then there exists a maximal set of edge-disjoint paths containing every path of the form $v \to u \to w$ for $u \in X$. Proof: Pick some $u$ such that $v \to u \to w$ is not in $S$. First note that at least one of the edges $v \to u$ and $u \to w$ must be contained in some path in $S$, else we can add the path $v \to u \to w$, which contradicts maximality. If only $v \to u$ is contained, then replace that path with $v \to u \to w$, and do the same if only $u \to w$ is contained. If both are contained, say we have paths $v \to u \cup P_1$ and $P_2 \cup u \to w$, where $P_1$ and $P_2$ are (disjoint) paths with that start at $u,v$ and end at $w,u$ respectively. Then replace them with $v \to u \to w$ and $P-1 \cup P_2$, which has the same edge set. $\blacksquare$ Suppose that our choice of edge-disjoint sets satisfies the condition in the claim (of course, the claim is symmetric wrt $v,w$, so this applies for the edge-disjoint set of paths from $w$ to $v$). Because all the edges between vertices in $X,Y$ and $v,w$ are used, any path from $v$ to $w$ that starts through $B$ (i.e. the vertex after $v$ is in $B$) must end through $A$ (i.e. the vertex before $w$ is in $A$), and the same applies for paths from $w$ to $v$. In particular, for $b \in B, a \in A$, every path from $v$ to $w$ starting through $b$ and ending through $a$ can be bijected to a path from $w$ to $v$ starting and ending through the same vertices. If there are at most $k$ edge-disjoint paths of one form, there are at most $k$ edge-disjoint paths of the other, we can easily see that \begin{align*} M&=|X|+1+k\\ N&=|Y|+k, \end{align*}where the $+1$ comes from the path $v \to w$. Thus $M=N \iff |X|+1=|Y|$. Since the outdegree of $v$ is exactly $|X|+|B|+1$ and the outdegree of $w$ is exactly $|Y|+|B|$, we are done. $\blacksquare$ Remark: I named my $A$ and $B$ wrong lmao

Interpret the road system in Anisotropy as a directed graph; if edge $XY$ goes to $Y$ we write $X\rightarrow Y.$ Consider four distinct sets $P,Q,R,S$ of vertices $C$ in graph, satisfying $A\leftarrow C\rightarrow B$ for $C\in P;$ $A\rightarrow C\rightarrow B$ for $C\in Q;$ $A \leftarrow C\leftarrow B$ for $C\in R;$ $A\leftarrow C\rightarrow B$ for $C\in S.$ Claim. There exist a maximal diverse collection of paths from $A$ to $B$, which $\forall D\in Q$ contains path $A\rightarrow D\rightarrow B.$ Proof. Assume for some collection $\mathcal{C}$ and $D\in Q$ it doesn't hold. By maximality at least one of edges $AD,DB$ is included at path $l$ of $\mathcal{C}.$ It exactly one, exchange $l$ onto $A\rightarrow D\rightarrow B.$ If both paths are included in paths $A\rightarrow D \rightarrow \dots \rightarrow B$ and $A\rightarrow \dots \rightarrow D \rightarrow B$ we can swap these paths with $A\rightarrow D \rightarrow B$ and $A\rightarrow \dots \rightarrow D \rightarrow \dots \rightarrow B.$ Exchanging doesn't affect on maximality of set, so we can obtain the required set $\Box$ Assume that our maximal diverse collection satisfies the condition of lemma and of analogous claim for $D\in R;$ observe that all other paths of type $A\rightarrow E\rightarrow \dots \rightarrow F \rightarrow B$ are in bijection with paths of type $B\rightarrow E\rightarrow \dots \rightarrow F\rightarrow A,$ therefore $$\text{outdeg }(A)=\text{outdeg }(B)\iff |Q|=|R|\iff N_{AB}=N_{BA}\text{ } \blacksquare$$

Max-flow-min-cut and some wishful thinking! Interpret the problem setting as a directed graph $(V, E)$. Assign a capacity of $1$ to each edge. Then $N_{st}$ equals the maximum $s-t$ flow, which equals the minimum $s-t$ cut capacity, from the max-flow-min-cut theorem. For $Q, R \subseteq V$, define $\text{deg}(Q,R) = |\{(u, v) \in E \mid u \in Q, v \in R\}|$. Let $S \subseteq V \setminus \{A, B\}$, $S' = V \setminus (S\cup\{A, B\})$. Then the capacity of the cut $(S \cup \{A\}, S' \cup \{B\})$ is: $$\text{deg}(S, S')+\text{deg}(S, \{B\})+\text{deg}(\{A\}, S')+\text{deg}(\{A\}, \{B\})$$$$=\text{deg}(S, S')+|S|-\text{deg}(\{B\}, S)+\text{deg}(\{A\}, S')+\text{deg}(\{A\}, \{B\})$$ Similarly calculating the capacity of the cut $(S \cup \{B\}, S' \cup \{A\})$ and taking the difference of the two gives us: $$(\text{deg}(\{A\}, S)+\text{deg}(\{A\}, S')+\text{deg}(\{A\}, \{B\}))-(\text{deg}(\{B\}, S)+\text{deg}(\{B\}, S')+\text{deg}(\{B\}, \{A\}))$$which is just $\text{outdegree}(A)-\text{outdegree}(B)$. So the minimum $A-B$ cut capacity equals the minimum $B-A$ cut capacity iff $\text{outdegree}(A)=\text{outdegree}(B)$, and we're done. Motivation: Viewed with the context of the max-flow-min-cut theorem in mind, the condition $\text{outdegree}(A) = \text{outdegree}(B)$ intuitively seems like a small part of a bigger picture. The difference calculations we do are obvious and immediate for the case $S = \{\}$ and $S = V \setminus \{A, B\}$, so we're motivated to do it for a general $S$, and things work out after that.

If there is a road from towns $X$ to $Y$ then we say $X\to Y$. Let $S_1$ be the set of towns $T$ such that $A,B\to T$; let $S_2$ be the set of towns $T$ such that $A\to T\to B$; let $S_3$ be the set of towns $T$ such that $T\to A,B$; let $S_4$ be the set of towns $T$ such that $B\to T\to A$. Assume WLOG $A\to B$. The number of roads outgoing from $A$ is $|S_1|+|S_2|+1$ and the number of roads outgoing from $B$ is $|S_1|+|S_4|$. Let the set of maximum path from $A$ be $M_A$ and similar for $B$. Note that if for $T\in S_2$, $A\to T$ road is not used and $T\to B$ road is not used, we can add a path. If $A\to T$ road is used but $T\to B$ road is not used, we can break the path from $T$ to $B$ and use $T\to B$ road. If $A\to T$ road is used and $T\to B$ road is used on a different path, say for $A\to \{X_1\}\to T\to B$ and $A\to T\to \{X_2\}\to B$ then construct paths $A\to T \to B$ and $A\to \{X_1\} \to T\to \{X_2\} \to B$. We can do similar things to $M_B$. Note that any other path from $A$ must consist of a road from $A$ to a town $T_1$ in $S_1$ and then a town $T_3$ in $S_3$ to $B$. For each path in $M_A$ that is $(A\to T_1) (\text{untitled path}) (T_3\to B)$ we also have $(N\to T_1) (\text{untitled path}) (T_3\to A)$, so there is a bijection between the rest of the paths. Thus, the number of paths in the maximal set is equal if and only if $|S_2|+1=|S_4|$ as desired.

v_Enhance wrote: Claim: In any maximal set $\mathcal P$ of edge-disjoint paths from $v$ to $w$, we may assume without loss of generality that every path of the form $v \to x \to w$ for $x \in X$ appears. Proof. Replacement argument: If neither $v \to x$ or $x \to w$ are in $\mathcal P$, this contradicts maximality. If exactly one of them is present, say $v \to x$, replace the path $v \to x \to \text{blah} \to w$ with $v \to x \to w$. Suppose both $v \to x$ and $x \to w$ are used, say $v \to x \to \text{blah}_1 \to w$ and $v \to \text{blah}_2 \to x \to w$. Replace with $v \to x \to w$ and $v \to \text{blah}_2 \to \text{blah}_1 \to w$. $\blacksquare$ I'm seeing this argument a lot, but isn't the proof incomplete? In order for the argument to work, we need to make sure that the replacement process terminates. This is pretty easy to prove, but I think you need to at least mention it, since it isn't obvious that the writer of the proof understands this condition.

What do you mean, it is not a process, just a casework: in each case you make one appropriate replacement?

Yes, but the hidden assumption is that by repeating the replacement argument, we can satisfy the conditions of the claim. As it stands, the proof only shows that for each $x$, the path $v \to x \to w$ can appear, but it doesn't show that all such paths can simultaneously appear.

Use the graph theory formulation, and replace $A, B$ with $u, v$. Let $W$ be the set of vertices which point from $u$ and towards $v$ and $X$ similarly; define $Y$ and $Z$ to be the sets of vertices that point out or point in to both $u$ and $v$ respectively. Claim. For any vertex $v_1 \in W$, the path $u \to v_1 \to v$ will be in the maximal collection. Proof. Suppose otherwise. We will prescribe an operation that strictly increases the number of such paths. If $u \to v_1 \to v$ is completely unoccupied, simply add it. If $u \to v_1$ (or $v_1 \to v$) is occupied by some path, replace that path with $u \to v_1 \to v$. If both $u \to v_1$ and $v_1 \to v$ are occupied, we can differentiate the paths into $u \to v_1 \to v$ and $u \to \cdots \to v_1 \to \cdots \to v$. In each case, the number of such paths increases. $\blacksquare$ Now it remains to look at $Y$ and $Z$. Fortunately, any path from $u$ to $v$ through $Y, Z$ bijects to a path from $v$ to $u$ through $Z, Y$. Thus it follows that $$M - N = |X|+1-|Y| = \mathrm{outdeg} \ v - \mathrm{outdeg } \ w,$$as needed.

Lol Let $u, v$ be any two vertices in $G$. WLOG, assume there is edge $u \to v$. Partition all the vertices other that $u, v$ into four groups $A, B, C, D$ such that the following holds: If $x \in A$, then there is edges $u \to x$ and $x \to v$. If $x \in B$, then there is edges $u \to x$ and $v \to x$. If $x \in C$, then there is edges $x \to u$ and $v \to x$. If $x \in D$, then there is edges $x \to u$ and $x \to v$. Claim: We can assume for all paths $u$ to $v$, different from $u \to$ some vertex in $B$ $\to$ blah2 $\to$ some vertex in $D \to v$, the form $u \to x \to v$, for some $x \in A$. Proof: Fix $x \in A$. If neither $u \to x$ nor $x \to v$ is used, this contradicts maximality of $M$. If either $u \to x$ or $x \to v$ is used, assume $u \to x$ is used, then replace the path $u \to v \to \dots \to v$ to $u \to x \to v$. If both of $u \to x$ and $x \to v$ is used, replace the two path $u \to x \to \dots v$ and $u \to \dots \to x \to v$ to $u \to x \to v$ and $u \to \dots \to \dots \to v$. Thus we can assume all path are the form $u \to x \to v$. $\blacksquare$ Now let $T$ be number of paths $u$ to $v$ of the form $u \to$ some vertex in $B$ $\to$ blah2 $\to$ some vertex in $D \to v$. Then $M = T + 1 + |A|$ and $N = T + |B|$. So $M = N \iff |A| + 1 = |B|$. Thus we're done. $\blacksquare$

Storage (I'd already seen the solution so that made it much easier oops.) Consider sets $S_1,S_2,S_3,S_4$ consisting of elements: \[A,B\to S_1\]\[A\to S_2\to B\]\[S_3\to A,B\]\[B\to S_4\to A\] also note we have the last edge WLOG $A\to B$ which we may as well remove (it doesn't affect anything). The rest of the problem is basically just local, we have $|S_2|=|S_4|$. Notice that proving the optimal $N_{AB}$ occurs when every element $v\in S_2$ has $A\to v\to B$ selected would suffice, as the remaining cases form something along the lines of $A\to S_1\to \dots \to S_3\to B$ which is analogous to the reverse. Basically we need to show that performing series of nondecreasing swaps from some configuration to the desired can be found. In any optimal configuration, a vertex $v\in S_2$ has at least one edge in $A\to v$ and $v\to B$ selected. If $A\to v$ is selected and $v\to B$ is not, then just replace whatever path $A\to v\to \dots\to B$ with the more direct $A\to v\to B$. If $v\to B$ is selected and $A\to v$ is not, then just replace whatever path $A\to \dots\to v\to B$ with the more direct $A\to v\to B$. If both $A\to v$ and $v\to B$ are selected, then replace ($P$ and $Q$ represent the paths) \[A\to v\to Q\to B\]\[A\to P\to v\to B\]with \[A\to P\to v\to Q\to B\]\[A\to v\to B.\] Obviously the number of paths will not decrease, and we're done!

Paths of length $1$ and $2$ are no-brainers to include in maximal diverse collections. If we close all the roads involved in these length $1$ and $2$ paths, consider what remains: for each city $X$ that is not $A$ or $B$, its roads to $A$ and $B$ are either both closed down, both outbound or both inbound. Thus, the remaining roads are symmetrical WRT $A$ and $B$, so the number of paths we can add to each diverse collection is the same, as well as the number of outgoing roads from $A$ and $B$. If we now reopen the roads in length $1$ and length $2$ paths, each outgoing road we open from $A$ corresponds to a path of length $1$ or $2$ from $A$ to $B$, and each outgoing road we open from $B$ corresponds to a path of length $1$ or $2$ from $B$ to $A$. Thus, $N_{AB} = N_{BA}$ iff we reopen the same number of outgoing roads from each city.

We will divide all vertices apart from $A$ and $B$ into $4$ categories: 1. $A \leftarrow X \leftarrow B$ 2. $A \rightarrow X \rightarrow B$ 3. $A \leftarrow X \rightarrow B$ 4. $A \rightarrow X \leftarrow B$ Now consider the biggest collection of diverse pathes from $A$ to $B$, and among same sizes choose the one in which the number of pathes of the form $A \rightarrow X \rightarrow B$, where $X$ is from second type, is the biggest. We will prove that for every $X$ from type two, path $A \rightarrow X \rightarrow B$ is in the collection Suppose for some second-type $X$ this path is not in the collection. If none of the edges $AX$ and $XB$ occur in the collection, we can add path $A \rightarrow X \rightarrow B$, contradiction with maximality. If only one of them occurs, we may replace it with $A \rightarrow X \rightarrow B$ - contradiction with maximality. So both of the edges is in the collection and the edges are in different pathes. Call $S_1$ the path from $X$ to $B$ in the first path and $S_2$ the path from $A$ to $X$ in the second path. Then we want to replace both pathes with $AXB$ and $A-S_1-X-S_2-B$. If in the second path some vertice repeats twice, just delete everything in between its occurances. So once again contradiction with maximality. Now we add $A$ and $B$ to either categories $1$ or $2$ (depending on the direction of $AB$). Therefore, $N_{AB}=|Type 2|+M$, where $M$ is the biggest number of pathes that do not intersect by edges and do not have any of the edges of the form $AX$ or $XB$, where $X$ is of the first or second type. Because types $3$ and $4$ are symmetric across swaping $A$ and $B$, $M$ is the same for $N_{BA}$. So $N_{BA}=|Type 1|+M$. So $N_{AB}=N_{BA}$ is equivilant to $|Type 2|=|Type 1|$, which is the desired.