[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.