theorem of graph theory
THEOREM 1: Let T_0 be minimum cost spanning tree in G. then every in- tree edge in T_0 must be a minimum cost edge in the fundamental cut set associated with it. Proof: Let (X;(X)) ̅ be the fundamental cut set associated with the in- tree edge(i;j)in T_0. So, (i;j)is the only in-tree edge in (X;(X)) ̅, and deletion of (i; j) from T_0disconnects it into smaller trees, one spanning the nodes in X, and the other spanning the nodes in X ̅. Suppose a minimum cost edge in the cut set (X;(X)) ̅ is an out-of-tree edge (p; q) and not (i; j) i, e., c_pq<c_ij . then replacing, (i; j) in T_0 by (p; q) leads to spanning tree T_1 with cost = cost of T_0-(c_ij- c_pq) < cost of T_0, contradicting, the optimality of T_0 hence (i; j) must be minimum cost edge in the fundamental cut set (X;(X)) ̅ associated with it in T_0. THEOREM 2: Let T_0 be minimum cost spanning tree in G. then every in...