Граф Гевирца

Граф Гевирца можно построить следующим образом. Рассмотрим единственную систему Штейнера ${\displaystyle S(3,6,22)}$ с 22 элементами и 77 блоками. Выберем произвольный элемент и будем считать вершинами 56 блоков, не связанных с этим элементом. Соединяем ребром два блока, если они не пересекаются.

По этому построению можно вложить граф Гевирца в граф Хигмана — Симса.

Характеристический многочлен графа Гевирца равен

${\displaystyle (x-10)(x-2)^{35}(x+4)^{20}.\,}$

Поэтому граф является целым графом — графом, спектр которого полностью состоит из целых чисел. Граф Гевирца полностью определён своим спектром.

Число независимости графа равно 16.