### dang_252's blog

By dang_252, history, 5 weeks ago,

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?

 » 5 weeks ago, # | ← Rev. 2 →   +9 If there would be a larger edge on the path from $u$ to $v$, then the maximum spanning tree algorithm would naturally replaced that edge with the smallest edge on the path. When the smallest on the path from $u$ to $v$ be discarded, the tree would be separated into two components. Also adding the larger edge would merge those two components. Since the order of iteration of the edges while adding to the maximum spanning tree is from the largest to the smallest, rather than the smaller edge, the larger edge would be priorly considered to be added to the maximum spanning tree. As mentioned, since the larger edge merges those two components too, it would be added to the maximum spanning tree.
•  » » 5 weeks ago, # ^ |   +21 Consider this graph:We have the MaxST will be: 1 4 32 4 42 3 5But if we go by the path $1 \rightarrow 3 \rightarrow 2$ which will have max weight ($5$) larger than using the edges on the MaxST : $1 \rightarrow 4 \rightarrow 2$ for path $1 \rightarrow 2$So if your point is to prove that there can't be larger max edge path by not using edges on the MaxST then this example was the counter for that.If I misread your comment or something, pls fix me. Thanks
•  » » » 5 weeks ago, # ^ |   +8 I think your counterexample is right and my comment proves that the maximum spanning tree maximizes the smallest edge on the path from $u$ to $v$. Sorry for misunderstanding.