Recently I came across a problem:

Given an undirected graph $$$n$$$ vertices with $$$m$$$ weighted edges. Find a simple cycle with the value "Max weighted edge" + "Min weighted edge" maximized and print that value.

So my algorithm is:

• Build a Maximum Spanning Tree

• With an edge $$$u-v$$$ weight $$$w$$$ that is not in the MST, take max answer $$$w$$$ + Max weighted edge on that path $$$u-v$$$ on the MST.

In the second point, I could not prove if "Max weighted edge on that path $$$u-v$$$ on the MST" is maximized. What if there is another path from $$$u$$$ to $$$v$$$ with "Max weighted edge" larger.

I tried to prove that the Maximum Spanning Tree guarantees that the path $$$u-v$$$ have "max weighted edge" maximized but it turned out quite wrong in my mind as we can use edges that is not belong to the current MaxST to lead $$$u$$$ to a large edge then lead to $$$v$$$.

So how my algorithm actually guarantees with an edge $$$u-v$$$ weight $$$w$$$ that is not in the MST, the "Max weighted edge on that path $$$u-v$$$ on the MST" is the maximum "Max weight edge" path from $$$u$$$ to $$$v$$$?

How to prove that from $$$u$$$ to $$$v$$$ there is not any other path that have "Max weighted edge" larger than the one in the MST which will make the answer better?

Thanks in advanced.