Para ver que hemos ganado, simplemente observamos que siL es el conjunto de vértices etiquetados, yU es el conjunto de vértices sin etiquetar, entonces cada bordee=(x,y) conx∈L y\(...Para ver que hemos ganado, simplemente observamos que siL es el conjunto de vértices etiquetados, yU es el conjunto de vértices sin etiquetar, entonces cada bordee=(x,y) conx∈L yy∈U está lleno, es decir,ϕ(e)=c(e) . Si este no fuera el caso, entoncesy calificaría para una etiqueta conx como la primera coordenada.
