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.
100 roads in a city, 1 is closed
2
$\begingroup$
graph-theory
recreational-mathematics
-
4Welcome 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. – 2012-11-09
2 Answers
4
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.
-
0Nice +1, though it is hardly the easiest way to reach the conclusion. – 2012-11-09
4
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.
-
1The node (in one connected component) for which the edge was deleted. The other component has als such a node. – 2018-10-23