# 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

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.
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}