# 100 roads in a city, 1 is closed

In a certain country, 100 roads lead out of each city, and one can travel along those roads from any city to any other. One road is closed for repairs. Prove that one can still get from any city to any other.

-
I assume “100 roads” means exactly 100 roads, not at least 100 roads. For in the latter case, I can think of a counterexample. (Two complete graphs of 101 nodes/cities each, joined by a single edge/road between two cities, one in each group.) –  Harald Hanche-Olsen Nov 9 '12 at 8:37
Welcome to math.SE: since you are new, I wanted to let you know a few things about the site. In order to get the best possible answers, it is helpful if you say in what context you encountered the problem, and what your thoughts on it are; this will prevent people from telling you things you already know, and help them give their answers at the right level. Also, many find the use of imperative ("Prove", "Solve", etc.) to be rude when asking for help; please consider rewriting your post. –  Julian Kuelshammer Nov 9 '12 at 8:43

## 2 Answers

Here is a hint: Eulerian path.

Taking the hint too literally will yield a massively inefficient way of traveling between cities, but that's beside the point.

-
Nice +1, though it is hardly the easiest way to reach the conclusion. –  Marc van Leeuwen Nov 9 '12 at 12:11

First a little observation, for every graph $G=(V,E)$ we have $$\sum_{v \in V} \text{deg}(v)=2|E|,$$ by a simple double counting argument.

So assume we can disconnect two cities $x$ and $y$ by deleting one road. Let $G$ be the graph of the city network for the cities reachable from $x$ after the road deletion. In $G$ every vertex has degree 100, except of one node that has degree 99. Hence the degree sum is an odd number, which is a contradiction.

-