Pokażmy, że χ(μ(G)) > χ(G): w przeciwnym wypadku wszystkie kolory c(ui) (0 ≤ i < n), a także kolor c(w), występują wśród kolorów c(vi) (0 ≤ i < n). Ale kolor c(w) nie występuje wśród c(ui). Zdefiniujmy pokolorowanie d grafu G jak następuje:
d(vi) := c(vi) gdy c(vi) ≠ c(w) d(vi) := c(ui) gdy c(vi) = c(w)
dla i = 0, ..., n−1. Pokolorowanie d, grafu G, użyło nie więcej niż χ(G) − 1 kolorów – sprzeczność. Udowodniliśmy więc, że
χ(μ(G)) > χ(G).
Niech teraz d : G → D będzie minimalnym pokolorowaniem grafu G. Zdefiniujmy:
c(vi) := d(vi) c(ui) := d(vi)
dla i = 0, ..., n−1. Ponadto niech kolor c(w) nie należy do D. Wtedy c jest pokolorowaniem grafu Mycielskiego, które użyło tylko jednego koloru spoza D. Udowodniliśmy więc, że
χ(μ(G)) ≤ χ(G) + 1,
co w połączeniu z poprzednią nierównością (odwrotną) kończy dowód.
Jeśli największa klika w grafie G ma rozmiar ≤ 2, to taką samą własność ma graf μ(G). Co więcej, wszystkie kliki rozmiaru > 2 w grafie μ(G) są zawarte w grafie G, o ile takie kliki w ogóle istnieją (Mycielski 1955).
Jeśli graf G posiada cykl Hamiltona, to graf μ(G) także go posiada (Fisher 1998).