In a certain country, 40 roads lead out of each city. When all roads are open, it is possible to travel from any city to any other. Each road leads from one city to another; there are no dead end roads.
If one road is closed for repairs, is it still necessarily possible to travel from any city to any other? Prove your answer.
What I've tried so far: I tried doing it with 3 roads out of each city. I got a connected graph. So K_n, where n is the number of vertices. So with 3 roads out of each city, we can say that there are 4 cities–so K_4. Since there are 6 edges, I tried 6 cases where I removed one edge. Any person from one city could still get to the other cities. In some cases, they would have to travel along the border/perimeter to get there.
HINTS ONLY PLEASE
Best Answer
If (connected component of) a graph has $r$ vertices of odd degree, what can you say about $r$?