Základní meta-algoritmus můžeme ještě zobecnit o vymazávání hran, které do minimální kostry určitě nepatří. Pro jednoduchost předpokládejme, že všechny hrany mají různé ohodnocení a tím pádem že je minimální kostra určena jednoznačně. Vyhneme se tím pojmu „rozšířitelnost do minimální kostry“ a výklad se zjednoduší.

Na začátku jsou všechny hrany grafu bezbarvé. Postupně je budeme barvit na červeno nebo na modro podle následujících lemmat. Barvíme tak dlouho, dokud není vše obarveno a dokud lze některé lemma aplikovat. Červené hrany ${\check C}\subseteq E$ jsou ty, které do kostry určitě nepatří. Klidně je místo barvení můžeme z grafu vymazávat. Minimální kostru budeme hledat v nečervených hranách. Modré hrany jsou ty, které do minimální kostry určitě patří.

Lemma (červené lemma): Je-li $C$ kružnice v $G$, pak nejdražší hrana na kružnici $e$ nepatří do minimální kostry. Hranu $e$ obarvíme na červeno.

Důkaz: Hrana $e$ nepatří do žádné minimální kostry. Předpokládejme pro spor, že $T$ je minimální kostra obsahující nejdražší hranu $e=xy$ kružnice $C$. Graf $T-e$ má dvě komponenty souvislosti. Protože $x$ leží v jedné a $y$ v druhé komponentě, tak na cestě $P=C\setminus e$ vedoucí z $x$ do $y$ existuje hrana $f$ propojující obě komponenty. Proto je $T’=T+f-e$ kostra. Navíc $c(e) > c(f)$ a tedy $c(T‘)=c(T)+c(f)-c(e) < c(T)$. To je spor s minimalitou kostry $T$. [/proof] [lemma name="modré lemma"] Nechť $e$ je nejlevnější hrana řezu $\delta(A)$. Pak hrana $e$ patří do minimální kostry. Hranu $e$ obarvíme na modro. [/lemma] [proof] Důkaz tohoto lemmatu je shodný s důkazem lemmatu „o nejlevnější hraně řezu“. (Předpokládejme pro spor, že existuje minimální kostra neobsahující $e$. Výměnou jedné hrany za $e$ dostaneme levnější kostru a to je spor.)

Lemma (bezbarvé lemma): Pokud by některá hrana zůstala neobarvená, tak lze ještě aplikovat červené nebo modré lemma.
Důkaz: Označme neobarvenou hranu $e=xy$. Nechť $W$ je množina vrcholů, do kterých se lze dostat z $x$ po modrých hranách.

Buď $y\in W$, ale potom existuje cesta z modrých hran vedoucí z $x$ do $y$ a ta spolu s hranou $e=xy$ tvoří kružnici $C$. Každá kružnice obsahuje alespoň jednu červenou hranu, tu nejdražší. Všechny hrany kružnice $C$ kromě $e$ jsou modré a proto hrana $e$ musí být nejdražší hranou kružnice $C$ a můžeme ji podle červeného lemmatu obarvit na červeno.

Pokud $y\not\in W$, tak je řez $\delta(W)$ určitě neprázdný (obsahuje hranu $e$) a neobsahuje žádnou modrou hranu. Proto na řez $\delta(W)$ můžeme aplikovat modré lemma.

Červenomodrý algoritmus je konečný, protože v každém kroku obarví jednu hranu, hrany nepřebarvuje a všech hran je $m$. Podle lemmat najde minimální kostru, která bude tvořená modrými hranami.