Изменения

Пусть дан граф $G<V, E>$. '''Дополнительным графом к''' $G$ называется граф $G_1<V, \overline{E}>$, то есть граф с вершинами из $V$ и всеми ребрами из $E$, которые не вошли в $G$.

}}

<br>

<br>

Тогда ребро $(u, v) \notin G \Rightarrow (u, v) \in \overline{G} \Rightarrow u$ и $v$ лежат в одной компоненте связности $\overline{G}$.

<br>

*$v$ и $u$ лежат в разных компонентах связности $G$.

Тогда по предыдущему пункту $(v, w) \in \overline{G}$ и $(u, w) \in \overline{G} \Rightarrow v$ и $u$ лежат в одной компоненте связности $\overline{G}$.

<br>

}}

Будем доказывать по индукции. Для $k = 1$ утверждение справедливо.

Пусть у нас есть самодополнительный граф $G$ с $n$ вершинами, построим самодополнительный граф с $n + 4$ вершинами.

*$v_1 \rightarrow v_2, v_2 \rightarrow v_4, v_3 \rightarrow v_1, v_4 \rightarrow v_3$.

}}