Изменения
Нет описания правки
# Граф называется самодополнительным, если он изоморфен своему дополнению. Приведите примеры самодополнительных графов с 4 и 5 вершинами. Докажите, что если граф является самодополнительным, то он содержит либо $4n$ либо $4n+1$ вершину для некоторого целого положительного $n$.
# Докажите, что для любого целого положительного $n$ существует самодополнительный граф, содержащий $4n$ вершин, а также самодополнительный граф, содержащий $4n+1$ вершину.
# Докажите, что каждый циклический путь нечетной длины содержит простой цикл.
# Докажите или опровергните, что объединение двух любых простых путей из вершины $u$ в вершину $v$ содержит цикл.
# Докажите, что граф связен тогда и только тогда когда для любого разбиения его множества вершин $V$ на два непустых непересекающихся множества $X$ и $Y$ существует ребро, соединяющее эти множества.
# Докажите, что в связном графе любые два самых длинных простых пути имеют общую вершину.
# Докажите или опровергните, что в связном графе все самые длинные простые пути имеют общую вершину.
# Обозначим как $\delta(G)$ минимальную степень вершины в графе. Докажите, что если в графе с $n$ вершинами $\delta(G) > (n - 1) / 2$, то он связен.
# Докажите, что либо граф $G$, либо его дополнение $\overline{G}$ связен.
# Будем говорить, что $G$ связан короткими путями, если между любыми двумя вершинами в $G$ есть путь длины не более 3. Докажите, что либо $G$, либо $\overline G$ связан короткими путями.
# Найдите максимальное число ребер в графе с $n$ вершинами, не содержащем четных простых циклов.
# Докажите, что граф с $n$ вершинами и $n + 4$ ребрами содержит два простых цикла, не имеющих общих ребер.
