Question

Верно ли что все регулярные графы типа (7,4( ( 7 вершин степень которых равна 4) изоморфны ?

Answer 1

Будем рассматривать не сами графы, а их дополнения. (Дополнение графа - это граф, в котором 2 вершины смежны тогда и только тогда, когда они не смежны в исходном). Легко видеть, что все дополнения представляют собой регулярные графы типа (7,2). Приведём пример 2 графов, не изоморфных между собой - цикл длины 7 и объедининие цикла длины 4 и цикла длины 3. В последнем графе есть треугольник, а в первом треугольника нет. Значит, 2 исходных графа тоже не изоморфны -  в одном есть 3 вершины, никакая из которых не смежна с другой, а в другом таких 3 вершин нет.