Граф Джонсона — це неорієнтований граф, вершинами якого є -елементні підмножини множини з елементів; дві вершини суміжні, коли вони мають спільну -елементну множину.. Граф Джонсона та споріднена з ним названо за ім'ям (1916—1996).
Спеціальні випадки
— повний граф . — октаедральний граф. — граф, обернений до графу Петерсена, тобто реберний граф до графу . Більш загально, для кожного граф Джонсона — це граф, обернений до графу Кнезера
Примітки