Albero ricoprente e aggiunta elemento

[nato_pigro1]

Sia $G$ un grafo connesso, non orientato e pesato e sia $T$ il minimum spanning tree. Supponiamo di aggiungere un vertice $j$ al grafo $G$ e di sapere che l'arco $(i,j)$ appartiene a $T'$, il MST di $G'=G \cup {j}$. Posso concludere che $T'=T \cup {(i,j)}$?

[Intermat]

Direi di si.
Questo perchè $T=T^(**)$. Infatti, aggiungendo un nodo, per generare un albero basterà collegarlo ad un qualsiasi altro nodo poichè in ogni caso non chiuderà con nessuno un ciclo perchè al momento è una componente connessa. Se si sceglierà l'arco $(i,j)$ tale che $l_(i,j)=min{l_(i,j): AA i !=j} $ si congiungerà il nuovo nodo con un nodo dell'albero $T$ con l'arco di costo minimo. Se, in particolare si sceglierà $T=T^(**)$ allora si avrà un albero formato dall'albero di costo minimo su $G$ più l'arco di costo minimo che unisce $j$ ad un nodo $i in V(G)$. Quindi si avrà un albero di costo minimo su $G'=(V',E(V'))$