random

Sì. Infatti: supponiamo per assurdo che esista un grafo $S\ne T$ (con peso inferiore di $T$) MST di $G^{\prime }$ ma non di $G$. Si avrebbe che $\text{peso\_S}={\sum }_{f\in E(S)}{w}^{\prime }(f)<{\sum }_{e\in E(T)}{w}^{\prime }(e)=\text{peso\_T}$ con $w^{\prime }:G^{\prime }\to R^{+}$.

Ma, poiché la costante $c$ è stata sommata al peso di ciascun arco, abbiamo che $w^{\prime }(x)=w(x)+c$, con $w:G\to R^{+}$.

Avremmo quindi ${\sum }_{f\in E(S)}w(f)+c<{\sum }_{e\in E(T)}w(e)+c$ che, semplificando le costanti, implicherebbe: ${\sum }_{f\in E(S)}w(f)<{\sum }_{e\in E(T)}w(e)$ Questo è impossibile, in quanto implicherebbe che $S$ sia un MST per $G$ (falso per ipotesi), e quindi che $T$ non lo sia. $T$ è quindi MST anche di $G^{\prime }$.

Poiché un grafo fortemente connesso è sempre ciclico, si incontrerà sicuramente almeno un arco all’indietro. Per gli altri tipi di archi, dipende dalla configurazione del grafo.