Supongamos que enG hay un camino dev1 av3, y que los vértices a lo largo de este camino son alternativamente coloreados de rojo y verde; llamar a dicho camino camino un camino alterno ro...Supongamos que enG hay un camino dev1 av3, y que los vértices a lo largo de este camino son alternativamente coloreados de rojo y verde; llamar a dicho camino camino un camino alterno rojo-verde. Esta sigue siendo una coloración adecuada de todos los vértices deG exceptov, y ahora ningún vecino dev es púrpura, por lo que al colorearv púrpura obtenemos una coloración adecuada deG.