A Mycielski graph 
is a triangle-free graph with chromatic
number 
belonging to the following recursively constructed family. Set 
and 
. For 
, retain the vertices 
and edges
of 
,
add a new vertex 
for each 
, and add one more vertex 
. Join 
to every vertex adjacent
to 
in 
,
and join 
to every 
to obtain 
(Jarnicki et al. 2016, §5).
For example, triangle-free graphs with chromatic number 
include the Grötzsch
graph (11 vertices), Chvátal
graph (12 vertices), 13-cyclotomic
graph (13 vertices), Clebsch
graph (16 vertices), quartic
vertex-transitive graph Qt49 (16 vertices), Brinkmann graph (21 vertices),
Foster cage (30 vertices),
Robertson-Wegner graph (30 vertices),
and Wong graph (30 vertices).
The graph 
is the Grötzsch graph,
which is the smallest of these examples.
The first few Mycielski graphs are illustrated above and summarized in the table below.
The 
-Mycielski
graph has vertex count
 |
(1)
|
giving the sequence of vertex counts for 
,
2, ... of 1, 2, 5, 11, 23, 47, 95, 191, 383, 767, ... (OEIS A083329),
and edge count
 |
(2)
|
where 
and 
.
Mycielski graphs are implemented in the Wolfram Language as FromEntity[Entity["Graph",
"Mycielski", n]],
and precomputed properties for small Mycielski graphs are implemented as GraphData[
"Mycielski", n
].
is Hamilton-connected
for all 
except 
(Jarnicki et al. 2016).
de Grey (2026) constructed a unit-distance embedding of the 4-Mycielski (Grötzsch graph)
in three dimensions and attempted to construct one for the 5-Mycielski graph in his
construction of 5-chromatic, triangle-free,
unit-distance graph in 
, though ended up using a different graph on 31 vertices
(the 31-de Grey graph).
The fractional chromatic number of the Mycielski graph 
is given by 
and
 |
(3)
|
(Larsen et al. 1995), giving the sequence for 
, 3, ... of 2, 5/2, 29/10, 941/290,
969581/272890, ... (OEIS A073833 and A073834).
With 61 Vertices." Geombinatorics 35,
2026.House of Graphs. Mycielski Graphs.