Let $G=(V,E)$ be an undirected, weighted, connected graph with no self-loops. Typically, given a path between two vertices, one defines the cost of a path between those vertices as the sum of the costs of the edges traversed in the path. For this question, we'll consider an alternative notion of path cost: the max-cost. The max-cost of a path $P$ connecting two vertices $u,v$ is $c(P) = \max_{e \in P} c_e$, that is, it's equal to the largest single edge-cost in the path. Now, given two vertices $u,v$, we define a minimum max-cost path between $u,v$ as a path between $u,v$ of minimum max-cost.
(I don't know if this has a standard terminology, so I sort of made up my own above).
Below, we will refer to minimum spanning trees. The minimum spanning tree is defined as usual, with the sum cost definition.
One curious observation I've proven is that the minimum spanning tree $T$ produced by running Kruskal's algorithm on $G$ has the property that the (unique) path in $T$ connecting vertices $u,v$ is also a minimum max-cost path among all paths connecting $u,v$ in $G$. I'm wondering if this generalizes to all MSTs of $G$, rather than just the one produced by Kruskal (recall that, in general, graphs might have numerous MSTs), and also if this property in some sense characterizes MSTs.
More precisely:
Suppose $G=(V,E)$ is undirected, weighted, connected, and without self-loops. A spanning tree $T \subset G$ is minimally connecting if for every $u,v \in V$, the path between $u,v$ through edges only in $T$ is a minimum max-cost path, among all paths between $u,v$ in $G$. Is it true that a spanning tree $T$ is minimally connecting if and only if it is a minimum spanning tree? (Again, note a minimum spanning tree is defined in the 'standard' way).
As always, if there is any lack of clarity in what is being asked, feel free to comment. For further intuition, consider checking out this picture of a minimum spanning tree, noting how given any two vertices in the graph, the path between them through the MST (i.e., the 'black' path) minimizes the max-cost.
Best Answer
Yes, it is true in general. Note that even though MSTs are non-unique, they are not that non-unique: the only non-uniqueness comes from ties between edges of equal weight. If all edge weights are unique, the MST is also unique.
In particular, from your proof, it follows that if all edge weights are unique, the MST is also minimally connecting.
But suppose you have a general weighted graph $G'$, with possibly non-unique edge weights, and $T$ is one of its MSTs. We can break ties on the edges by adding some very small $\epsilon_i$ to the weight of the $i^{\text{th}}$ edge (taking every $\epsilon_i$ to be much smaller than any actual difference between the cost of any two spanning trees), creating a new graph $G'$ with a unique MST. We can make sure that ties are broken in favor of the edges in $T$ (giving them smaller $\epsilon_i$'s than any edges not in $T$), so that $T$ is also the unique MST of $G'$.
Since $T$ is the unique MST of $G'$, it will be the MST found by Kruskal's algorithm in $G'$, and therefore it is minimally connecting for $G'$ by your definition.
But if we now wipe away all the $\epsilon_i$'s, $T$ should also be minimally connecting for $G$, because $\epsilon_i$'s were much less significant than any actual difference between edge weights. (If some path in $T$ had used an edge of too-high cost in $G$, that edge would have been equally problematic in $G'$.)
Since $T$ was an arbitrary MST, we conclude that all MSTs are minimally connecting.
We can also observe than in a graph with unique edge weights, looking for a minimally connecting tree is forced to find the tree found by Kruskal's algorithm, because we only use an edge of weight $w$ once we've connected all we can by edges of weight $<w$. So in $G'$, MSTs and minimally connecting trees are equivalent, and therefore the same thing is true in $G$. (Start with a minimally connecting tree $T$ in $G$, break ties so that it's minimally connecting in $G'$, conclude that it's an MST in $G'$, and therefore that it's an MST in $G$.)