Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
4  
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 2

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.

share|improve this answer
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.