Доказательство нескольких утверждений по графам

[Piteryo]

Никак не получается, понять как грамотно доказать некоторые утверждения, например:

1) Доказать, что если в графе (без петель и кратных ребер) более 4 вершин, то либо в самом графе, либо в его дополнении содержится цикл.

попытки доказать

Если предположить, что в исходном графе нет циклов, то получается, что между 2 любыми вершинами существует единственный маршрут. А в дополнении графа эти 2 вершины соединены с какой-то еще(как обосновать этот момент?), соответственно между этими 2 вершинами существует 2 маршрута, и образуется цикл. Верно ли такое доказательство?


2) Если v - разделяющая вершина графа, то она не является разделяющей в его дополнении.

домыслы

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


3) Показать, что самодополнительный граф связен

@темы: Теория графов, Дискретная математика