Дополнением G¯ графа G называется такой граф на том же множестве вершин, что и у графа G,в котором пара вершин связана ребром тогда и только тогда, когда в G эта пара вершин ребром н связана. Докажите, что если в графе больше 5 вершин, либо сам граф, либо его дополнение содержат цикл длины 3.

Предположим, был дан граф G. Рассмотрим граф $ G_1 $ такой, что если две вершины соединены ребром
в графе G, то они соединены ребром (далее будем называть обычным) в $ G_1 $, а если две вершины не
соединены ребром в графе G, то они соединены пунктирным ребром в $ G_1 $.
Тогда граф $ G_1 $ будет представлять из себя полный граф, где некоторые ребра пунктирные. Рассмотрим произвольную вершину $ v_1 $ в графе $ G_1 $. Так как $ G_1 $ – полный граф и по условию количество вершин хотя бы 6, то найдется либо 3 пунктирных, либо 3 обычных ребра, исходящих из вершины $ v_1 $
(иначе из $ v_1 $ исходит не более 4 ребер). Не умоляя общности пусть из $ v_1 $ исходило 3 обычных ребра
в вершины $ v_2 $, $ v_3 $ и $ v_4 $(если исходит 3 пунктирных ребра, то рассуждения аналогичны).
Если среди ребер, соединяющих вершины $ v_2 $, $ v_3 $, $ v_4 $ найдется обычное, то тогда искомый цикл длины 3 находится в графе G, соединяющий вершину $ v_1 $ и 2 вершины из $ v_2 $, $ v_3 $, $ v_4 $, которые соединены обычным ребром. Если же все ребра, соединяющие $ v_2 $, $ v_3 $, $ v_4 $ пунктирные, то найдется цикл длины 3
с вершинами $ v_2 $, $ v_3 $, $ v_4 $ в графе G¯. ЧТД.