Let an undirected, connected graph $G=(V,E)$ with the weight funciton $w:E\to \mathbb{R}$, an edge $e$, and $0<k\in\mathbb{N}$. Describe an algorithm determines if there are at most $k$ edges could be removed to make a minimum spanning tree including the edge $e$.
So basically the algorithm works as follows:
- Remove edges where $w(\hat{e}) > w(e)$.
- Count the number of disjoint paths from $u$ to $v$ where $e=\langle u,v\rangle$.
- If there are more than $k$ paths return $false$. Otherwise, remove (I guess) the "heaviest" edge from each path and return the new graph which is the desired MST.
Well, I'm trying to prove the validity of this algorithm:
Basically, if there are more than $k$ disjoint paths than there must be a disjoint path we didn't change (i.e. removed an edge from it) and therefore, there must be a cycle. Contradiction to the definition of MST
Now, I'm trying to prove the second part: If there are at most $k$ disjoint paths than there's an MST which includes $e$.
I think I need to claim that for every MST: each disjoint path may lose at most one edge. Is that correct?
I'd be glad for help with the second part of the proof.
Thanks!