Задача про самодополнительный граф

[rendall]

Мучаюсь над решением задач по теории графов по Гаврилову, Сапоженко с переменным успехом. Удручает что совсем нет примеров решения. Существует ли вообще "решебник" по теории графов где разбирались бы варианты решения типовых задач этой области?

В частности сейчас застрял на задаче: Граф ${G}$ называется самодополнительным, если графы ${G}$ и $\bar{G}$ изоморфны. Показать что диаметр самодополнительного графа равен 2 или 3.

От индукции не могу понять как решать, да и вряд ли этот вариант. Вероятно надо идти от противного: предполагаем, что диаметр не равен 2 или 3. Для варианта менее 2 всё тривиально. А для варианта больше или равно 4 доказать не получается.Наверное надо увидеть, что графы ${G}$ и $\bar{G}$ неизоморфны.

[vpb]

Элементарная теория графов --- это такая область, где не требуется какой-то продвинутой науки, и ожидать наличия "типовых решебников" было бы странно, хотя, возможно, они и есть.
Разве что детские книжки с занимательной математикой и олимпиадными задачами. ( "Подумаешь, бином Ньютона" (с) )
Тут надо просто думать головой. Данная задача вполне может быть доступна и 7-8-класснику.

Конкретно в данной задаче, если уж совсем трудно, можно дать такую подсказку: если какой-то граф $\Gamma$ (не обязательно самодополнительный, как в задаче) имеет достаточно большой диаметр, то дополнительный к нему $\overline\Gamma$ --- наоборот, малый. (Подумайте, почему).