I find myself yet again stucked in one of the assignment's problems for my Graph Theory Course at my local university.
Let G = (V, E) be a connected (multi)graph and c : E → R be a cost function on its edges. Let $T^∗$ be a minimum cost spanning (MST) tree of G (with respect to c). We said that a connected subgraph H of G is c-extendable if $T^*_H$ = (V (H), E(H) ∩ E($T^∗$)) is a spanning tree of H.
Here is where i am getting stucked.
~Prove that if H is c-extendable, then $T^∗_H$ is a MST of H.
The solution which I've worked my way through a certain point is supposing that $T^*_H$ is not the MST of H.Considering this I assumed that there is a MST of H called $A^*$.A property of $T^*_H$ considering $A*$ is $\sum_{(e \ from \ c(T^*_H))} c(e)$ > $\sum_{(f \ from \ c(A^*))} c(f)$ . How should i proceed next?
Any hint is welcomed!
The key here is to recognize that $A^*$ can be used to construct a spanning tree $\bar A$ of G with lower total cost than $T^*$ which gives a contradiction because $T^*$ was presumed to have the smallest possible total cost.
$\bar A$ can be constructed by taking all the edges of $A^*$ and all the edges of $T^*$ that aren’t in $T*_H$.
All you need to do from there is prove that $\bar A$ is in fact a spanning tree, and that it has lower cost than $T^*$.