Man betrachte MST T von G mit $T' \subset T$. Die Endpunkt v sei $\in$ S und w sei $\in$ S \ V.  Da T MST ist, gibt es einen Weg P von v
nach w in T.

P muss eine Kante $e'
= (u', v') \in E_{S} $ enthalten. Nach der
Voraussetzung gilt $e' \notin T'$. Dadurch bildet $T'' :=(T \ \{e'\} \ \cup \{e\}$ ebenfalls einen
Spannbaum. Dadurch, dass c(e) in $E_{S} $ minimal ist, folgt daraus c(T'') $\leq$ c(T). Also ist dafür T'' ebenfalls MST (mit c(T'') = c(T) und T' $ \cup  \{e\} \subset T''$.

Kreis
Ein Spannbaum von G' ist ebenfalls Spannbaum von G.
Also genügt zu zeigen, dass sich minimale Kosten ebenfalls übertragen.
Betrachte dazu MST T von G.

Wenn $e \notin T$, folgt sofort, dass alle MSTs
von G'
die gleichen Kosten wie T haben.

Nehmen wir nun an e = (v, w) $\in$ T. Wenn man e aus T entfernt,
entstehen zwei Teilbäume $T_{v} $
und $T_{w}$ mit $v \in T_{v} $
und $w \in T_{w} $

Da C ein
Kreis ist, gibt es eine Kante e'
= (v', w') \neq e auf C mit v'
\in T_v
und w'
\in T_w.

Dann ist $T'
:= (T\ \{e'\}) \cup \{e\}$ ebenfalls ein Spannbaum in G'
mit
c(T') = c(T) − c(e) + c(e) $\leq$ c(T).

Wir können also daraus schließen, dass alle MSTs in G'
die gleichen Kosten wie T haben.