[10 pts] Imagine a country that has n N cities that are linked by highways, where a highway

(which can be traversed in either direction) links exactly two cities and the only way to enter or

exit a city is via highway(s). The president of this country hates wastefulness, so she ensured

that for any pair of cities in the country, there exists only one sequence of highway(s) linking the

two cities; in other words, the graph formed by the cities (vertices) and the highways (edges) is

a tree.

Further, suppose that there exists at least one city in this country such that there exist d EN

distinct highways via which you can enter or exit the city. Prove that there are at least d cities

such that: for each of the d cities, there is only one highway to enter or exit the city.