Given an undirected, connected graph $A$ with the property that every edges have a distinct positive weight attached to them. Now, for a given pair of vertices $m$ and $n$, define $d(p)$ as the maximum edge weights in each path $p$ between $m$ and $n$ (there could be many paths $p$). Furthermore, define $min \ d(p) = t(m, n)$. Prove that there always exists a spanning tree $K$ of $A$ such that for every pairs of vertices $m$ and $n$ in $K$, $t(m, n) = d(p)$.
My attempt. I tried to use contradiction to show otherwise, but I am getting stuck in the situation where we deal with the minimum spanning tree $K$, and the path $p$ between $m$ and $n$ that contains $t(m, n)$ is not in $K$. Then obviously there is the heaviest edge on this path $p$. But how to prove that we could replace this edge by some other edges while still being able to go from $m$ to $n$, thus contradicts the definition of the minimum spanning tree? Could somebody help out with some ideas?
Hint.
Try to proceed like this:
Let us organise the following process. Let $C$ be a cycle of graph $A$. Let $e$ be the edge of the largest weight of cycle $C$. We pass to the graph $A'=A-e$. We do the same for $A'$. The process will end when there are no cycles in the next graph.
This graph will be the desired spanning tree.
Addition.
If a connected graph has no cycles, then it is a tree. In this case you don't need to do anything. The graph $A$ is the desired spanning tree.
Since a new graph is obtained from the old one by removing an edge lying in some cycle, the new graph is connected like the old one and has fewer edges than the old one. Therefore, the process will be terminated at the moment when the next graph will have no cycles, i.e. it will be a tree and therefore a spanning tree of the original graph.
a) Let us denote the tree that results from this process by $K$ and prove that for any two vertices $u,v\in A$, $u\neq v$, we have the equality $t(u,v)=d(P)$, where $P$ is the path in $K$ between $u$ and $v$ (in a tree there is exactly one path between any two vertices).
Let $e\in P$ be an edge of maximal weight in $P$. Let the weight of this edge be $\alpha$.
b) Clearly, $t(u,v)\leq\alpha$. Suppose that $t(u,v)<\alpha$. This means that between $u$ and $v$ there exists a path $P'$ in the graph $A$ for which $d(P')=t(u,v)<\alpha$. Let $\beta=d(P')$ and let $e'\in P'$ have weight $\beta$. Since $P\neq P'$, then $P\cup P'$ contains a cycle, and this cycle contains an edge $e$ (think about why such a cycle exists). We denote it by $C$, since $e\in C$ the weight of this cycle is $\alpha$ (all other edges in $P\cup P'$ have less weight).
c) Now let's think how this could happen. Suppose that at some step of our process of removing edges we have a graph $A'$ with cycle $C$, and at the next step after removing a single edge we have a graph $A''$ with no cycle $C$ (why is there such a step?). But then an edge lying in $C$ was deleted and it was not $e$. The latter is impossible, since at each step we remove the edge of the highest weight in a cycle.
d) The obtained contradiction shows that the inequality $t(u,v)<\alpha$ is impossible. Hence $t(u,v)=\alpha=d(P)$.