# Find all edges of G contained in some MSP

I have the following question in a homework:

Let $$G = (V,E)$$ be an undirected graph, and let $$A = \{ e \in E \mid \text{ s.t. exists an MSP T containing } e\}.$$

We were asked to find $$A$$ in $$O(m \log n)$$ time.

Any suggestions?

• You don't write anything about weights, but I assume that the graph is weighted? Commented Jan 22, 2020 at 15:45
• Can you clarify what an MSP is? Should it be MST?
– Juho
Commented Jan 22, 2020 at 17:23

We call an edge superheavy if it is the unique heaviest edge in some cycle. This post shows that an edge $$e\in A$$ if and only if $$e$$ is not superheavy.
Now we can check whether an edge $$e$$ is superheavy by checking whether it connects two vertices in different connected components in the graph with edges whose weights are less than $$w(e)$$: If $$e$$ is superheavy, then the two endpoints of $$e$$ are connected by a path on which the edges have weights less than $$w(e)$$, so the two endpoints must lie in the same connected components in the graph with edges whose weights are less than $$w(e)$$. On the other hand, if $$e$$ connects two vertices in the same connected components in the graph with edges whose weights are less than $$w(e)$$, then we can find a path connecting the two endpoints of $$e$$ on which the edges have weights less than $$w(e)$$, so $$e$$ along with this path forms a cycle and $$e$$ has the largest weight in this cycle, so $$e$$ is superheavy.