Graf Mycielskiego lub Mycielskian nieskierowanego grafu G – graf μ(G) stworzony dzięki konstrukcji podanej przez Jana Mycielskiego w roku 1955, pokazującej istnienie grafu, w którym największa klika ma rozmiar ≤ 2, o bezwzględnie dużej liczbie chromatycznej.
Uogólniona wersja konstrukcji została przedstawiona przez Wensonga Lin w roku 2006.
Konstrukcja thumb|360px| Graf Grötzscha jako Mycielskian 5-grafu cyklicznego Niech n wierzchołków grafu G będzie oznaczonych v0, v1, ..., vn−1. Graf Mycielskiego μ(G) zawiera graf G jako izomorficzny podgraf oraz n+1 dodatkowych wierzchołków: ui odpowiadające wierzchołkom vi oraz wierzchołek w. Każdy wierzchołek ui jest połączony krawędzią z wierzchołkiem w tak, że tworzą one razem podgraf przypominający gwiazdę o n+1 wierzchołkach. Dodatkowo, dla każdej krawędzi vivj w ramach konstrukcji dodawane są krawędzie uivj oraz viuj.
Dla grafu G o n wierzchołkach i m krawędzich powstaje graf μ(G) o 2n+1 wierzchołkach i 3m+n krawędziach.
Przykłady Ilustracja przedstawia konstrukcję grafu Mycielskiego zastosowana dla grafu cyklicznego o 5 wierzchołkach. Powstały graf jest nazywany grafem Grötzscha, ma 11 wierzchołków i 20 krawędzi.