234
правки
Изменения
Нет описания правки
|proof=
Будем доказывать по индукции. Для графа с одной вершиной $k = 1$ утверждение очевидно. Докажем его для остальных графовсправедливо.
*Добавим ребра $(v_1, v_2), (v_2, v_3), (v_3, v_4)$
*Если $u$ была вершиной в $G$, добавим ребра $(u, v_1), (u, v_4)$
Назовем полученный граф $A$. Докажем, что $A$ самодополнителен.
Рассмотрим биекцию на множестве вершин $A$ и $\overline{A}$:
*Среди всех вершин, принадлежавших $G$ биекция будет такая же, как и у $G$ с $\overline{G}$;
*$v_1 \rightarrow v_2, v_2 \rightarrow v_4, v_3 \rightarrow v_1, v_4 \rightarrow v_3$.
}}
