Question 78
A country has $n$ cities. Between any two cities there is exactly one road, and every road is one-way. A path from city $X$ to city $Y$ is a sequence of one-way roads along which one can travel from $X$ to $Y$ without visiting any city twice. A set of paths is called independent if and only if no two of its paths use a common road.
For a city $X$, let $n_X$ be the number of one-way roads leading out of $X$. For two distinct cities $X$ and $Y$, let $N_{XY}$ be the largest possible number of paths from $X$ to $Y$ in an independent set of paths. Prove that $N_{XY} = N_{YX}$ if and only if $n_X = n_Y$.
For a city $X$, let $n_X$ be the number of one-way roads leading out of $X$. For two distinct cities $X$ and $Y$, let $N_{XY}$ be the largest possible number of paths from $X$ to $Y$ in an independent set of paths. Prove that $N_{XY} = N_{YX}$ if and only if $n_X = n_Y$.