MST: Prim, Korrektheit

beruht auf Lemma:

• Wenn U $\subseteq$ V und e₀ eine Kante zwischen U und V $\setminus$ U mit minimalem Gewicht,
• dann existiert ein Minimalgerüst T für G mit e₀ $\in$ E(T).

Beweis: Sei T' ein Minimalgerüst für G, das e₀ nicht enthält. Konstruiere daraus ein Gerüst T für G mit e₀ $\in$ E(T) und w(T)$\le$w(T').