, 2022

Let us use $X \to Y$ to denote that $X$ has a one-way road leading to $Y$, and use $X \rightsquigarrow Y$ to denote a path from $X$ to $Y$. Let
$$\mathcal{F}_X := \{C : X \to C\} \quad \mathcal{F}_X := \{C : X \leftarrow C\}$$
denote the set of cities from (to) which all one-way roads lead to (from) $X$; note that $n_X = |\mathcal{F}_X|$.

We call a path short if and only if the number of roads in it is $\le 2$; otherwise it is called a long path. We first prove the following Lemma:

Lemma: Let $\mathcal{P}$ be an independent set consisting of paths from $X$ to $Y$, with $|\mathcal{P}| = p$. Then there exists an independent set $\mathcal{P}'$ consisting of paths from $X$ to $Y$, satisfying $|\mathcal{P}'| \ge p$ and containing all short paths from $X$ to $Y$.

Proof: Let us perform the following operations on $\mathcal{P}$.

1. If $X \to Y$ and this path is not in $\mathcal{P}$, then add it to $\mathcal{P}$.
2. Suppose there exists a city $C$ satisfying $X \to C \to Y$ and this path is not in $\mathcal{P}$. Note that $\mathcal{P}$ is independent.
- If $\mathcal{P}$ has only one path containing $X \to C$ or $C \to Y$, remove that path and add $X \to C \to Y$.
- If $\mathcal{P}$ contains $X \to C \rightsquigarrow Y$ and $X \rightsquigarrow C \to Y$, remove these two paths, and add $X \to C \to Y$ and $X \rightsquigarrow C \rightsquigarrow Y$ to $\mathcal{P}'$.

It is easy to verify that the resulting $\mathcal{P}'$ is independent, $\mathcal{P}' \ge p$, and contains all short paths from $X$ to $Y$. □

Return to the original problem. Take any two cities $X$ and $Y$, and without loss of generality assume $X \to Y$. Take any independent set of paths $\mathcal{P}$ consisting of paths from $X$ to $Y$ with size $N_{XY}$. Our goal is to obtain, through operations, an independent set of paths $\mathcal{Q}$ consisting of paths from $Y$ to $X$ with size $N_{XY} - (n_X - n_Y)$. In this case, by the maximality of $N_{XY}$, we have
$$N_{YX} \ge N_{XY} - (n_X - n_Y) \quad \text{and similarly} \quad N_{XY} \ge N_{YX} - (n_Y - n_X)$$

Thus we obtain $N_{XY} - N_{YX} = n_X - n_Y$, which proves the original problem.

To obtain $\mathcal{Q}$, we first use the Lemma to obtain $\mathcal{P}'$. Note the following facts:
- $\mathcal{P}'$ contains all short paths from $X$ to $Y$, and the number of these short paths equals $|\mathcal{F}_X \cap \mathcal{F}_Y| + 1$.
- The paths in $\mathcal{P}'$ cannot contain any road that would be used by a short path from $B$ to $A$.
- All long paths in $\mathcal{P}'$ must be of the form $X \to C \sim D \to Y$. Moreover, by the previous property:
* $C \in \mathcal{F}_Y$ (otherwise the path would not be independent from $X \to C \to Y$);
* $D \in \mathcal{F}_X$ (otherwise the path would share the road $Y \to C$ with $Y \to C \to X$);

We construct $\mathcal{Q}$ in the following way:
- Add all short paths from $Y$ to $X$ into $\mathcal{Q}$.
- For every $X \to C \sim D \to Y$ in $\mathcal{P}'$, add $Y \to C \sim D \to X$ to $\mathcal{Q}$.

It is easy to verify that $\mathcal{Q}$ is independent. Moreover, since there are $|\mathcal{F}_X \cap \mathcal{F}_Y| + 1$ short paths from $X$ to $Y$, and $|\mathcal{F}_X \cap \mathcal{F}_Y|$ short paths from $Y$ to $X$,
$$\begin{aligned} |\mathcal{Q}| &= |\mathcal{P}'| - (|\mathcal{F}_X \cap \mathcal{F}_Y| + 1) + |\mathcal{F}_X \cap \mathcal{F}_Y| \\ &\geq N_{XY} - \{(|\mathcal{F}_X \cap \mathcal{F}_Y| + 1) - |\mathcal{F}_X \cap \mathcal{F}_Y|\} \end{aligned}$$
Also note that
$$\begin{aligned} n_X - n_Y &= |\mathcal{F}_X| - |\mathcal{F}_Y| = |\mathcal{F}_X \cap \mathcal{F}_Y| + |\{X \to Y\}| - |\mathcal{F}_X \cap \mathcal{F}_Y| \\ &= (|\mathcal{F}_X \cap \mathcal{F}_Y| + 1) - |\mathcal{F}_X \cap \mathcal{F}_Y|. \end{aligned}$$
Combining the two equations above, we have
$$|\mathcal{Q}'| \geq N_{XY} - (n_X - n_Y),$$
which completes the proof of the original problem.