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).