Let G=(V,E) a connected graph, and p:E−>R a weight function. We denote |v|=n and E={e1,e2,...,em}, we suppose that ∀i p(ei)≤p(ei+1).
1-Show that in a connected graph G, if T and T′ are two distinct partial graphs of G then ∃e∈T such as T′+{e} creates a unique cycle.
Given Ti the family defined by:
Ti = $\begin{cases} E & \text{ if } i=0 \\ T_{i-1}/e_{i}& \text{ if } {i>0} \text{ and G(V,} T_{i-1}/e_{i}) \text{ is connected} \\ T_{i-1 }& \text{ otherwise} \end{cases}$
2-Show that Tm is a maximum spaninnig tree on G.
3- Give the complexity of the determination of Tm.
Can some one help me in the second and third question? Thank you.