# Linear deterministic algorithm for finding spanning tree T with minimal maximum edge

Given an undirected connected graph $$G = (V, E)$$ with weights $$w :$$E → $$R^+$$, define for a spanning tree T the value $$λ$$(T) = $$max_e$$$$T$${w(e)} (the maximal edge weight in T ).

I need to find a linear deterministic algorithm of finding a spanning tree T with minimum maximum edge e. We were given a hint of using binary search.

I already proved that for MST of G, $$λ$$(MST) <= $$λ$$(T) for every T spanning tree of G.

The problem that using Prim or Kruskal algorithm is not linear, and I'm trying to find a special property for such tree.

We need to find such $$W$$ that the graph with edges of weight $$\leq W$$ is connected. Consider an edge with median weight $$M$$, like you do in the binary search.
• What if the graph with all edges with weight $$\leq M$$ is connected? Can we discard some edges completely and reduce the problem to the one where the graph has twice as less edges?
• What if the graph will all edges with weight $$\leq M$$ is not connected? Can we take some edges unconditionally now, process the graph somehow and reduce the probem to the one where the graph has twice as less edges?