Problem 1599

1. Graph Construction:
- Let $V$ be the set of cities.
- Construct a bipartite graph $G$ with vertex set $V \times \{0, 1\}$.
- For each city $v \in V$, create two vertices: $(v, 0)$ and $(v, 1)$.
- Draw an edge between $(v, 0)$ and $(w, 1)$ if there is a one-way street from city $v$ to city $w$.

2. Degree of Vertices:
- Each city $v$ has exactly two streets leading out of it and exactly two streets leading into it.
- Therefore, each vertex in $G$ has degree 2.

3. Perfect Matching:
- By Hall's Marriage Theorem, a bipartite graph has a perfect matching if and only if for every subset $S$ of one part, the neighborhood of $S$ (denoted $N(S)$) has at least as many vertices as $S$.
- In our graph $G$, since each vertex has degree 2, the conditions of Hall's Marriage Theorem are satisfied.
- Therefore, there exists a perfect matching in $G$.

4. Coloring the Streets:
- The perfect matching in $G$ corresponds to a set of streets in the original graph.
- Color the streets in the perfect matching as black.
- The remaining streets (not in the perfect matching) are colored white.

5. Verification:
- Each city $v$ has exactly one black and one white street leading out of it:
- Since each vertex $(v, 0)$ and $(v, 1)$ is matched exactly once in the perfect matching, each city $v$ has exactly one black street leading out.
- The remaining street leading out of $v$ must be white.
- Each city $v$ has exactly one black and one white street leading into it:
- Similarly, each vertex $(v, 0)$ and $(v, 1)$ is matched exactly once in the perfect matching, so each city $v$ has exactly one black street leading in.
- The remaining street leading into $v$ must be white.

Thus, we have successfully divided the streets into black and white such that each city has exactly one black and one white street leading out and one black and one white street leading in.

$\blacksquare$