Show Proof of correctness and state, and solve the Recurrence using the Master Theorem.
Let G = G(V, E) be an arbitrary, connected, undirected graph with vertex set V and edge set E.
Assume that every edge in E represents either a road or a bridge.
Give an efficient algorithm that takes as input G and decides whether there exists a spanning tree of G where the number of edges that represents roads is floor[ (|V|/ v 2) ]. Do so using the greedy algorithm.