Every September, somewhere in a far-away mountainous part of the world, the county highway crews get together and decide which roads to keep clear...

Every September, somewhere in a far-away mountainous part of the world, the county highway crews get together and decide which roads to keep clear through the coming winter. There are n towns in this county, and the road system can be viewed as a (connected) graph G = (V, E) on this set of towns, each edge representing a road joining two of them. In the winter, people are high enough up in the mountains that they stop worrying about the length of roads and start worrying about their altitude—this is really what determines how difficult the trip will be. So each road—each edge e in the graph—is annotated with a number ae that gives the altitude of the highest point on the road. We’ll assume that no two edges have exactly the same altitude value ae. The height of a path P in the graph is then the maximum of ae over all edges e on P. Finally, a path between towns i and j is declared to be winter-optimal if it achieves the minimum possible height over all paths from i to j. The highway crews are going to select a set E ⊆ E of the roads to keep clear through the winter; the rest will be left unmaintained and kept off limits to travelers. They all agree that whichever subset of roads E they decide to keep clear, it should have the property that (V, E ) is a connected subgraph; and more strongly, for every pair of towns i and j, the height of the winter-optimal path in (V, E ) should be no greater than it is in the full graph G = (V, E). We’ll say that (V, E ) is a minimum-altitude connected subgraph if it has this property. Given that they’re going to maintain this key property, however, they otherwise want to keep as few roads clear as possible. One year, they hit upon the following conjecture:

The minimum spanning tree of G, with respect to the edge weights ae, is a minimum-altitude connected subgraph. (In an earlier problem, we claimed that there is a unique minimum spanning tree when the edge weights are distinct. Thus, thanks to the assumption that all ae are distinct, it is okay for us to speak of the minimum spanning tree.)

Initially, this conjecture is somewhat counterintuitive, since the minimum spanning tree is trying to minimize the sum of the values ae, while the goal of minimizing altitude seems to be asking for a fairly different thing. But lacking an argument to the contrary, they begin considering an even bolder second conjecture:

A subgraph (V, E ) is a minimum-altitude connected subgraph if and only if it contains the edges of the minimum spanning tree.

Note that this second conjecture would immediately imply the first one, since a minimum spanning tree contains its own edges. So here’s the question.

(a) Is the first conjecture true, for all choices of G and distinct altitudes ae? Give a proof or a counterexample with explanation.

(b) Is the second conjecture true, for all choices of G and distinct altitudes ae? Give a proof or a counterexample with explanation.