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
Hint: does any graph with degree 40 have a bridge?
Hint: what happens when 40 is replaced with 41 instead?
Hint: consider cycles, which can be removed without changing bridges (if any). Consider the 2-regular graph that remains.