Изменения
Нет описания правки
# Приведите пример связного графа $G$, содержащего $n$ вершин, для которого граф $S_G$ имеет диаметр $n - 1$.
# Докажите, что для любого $k$ существует связный граф $G$, содержащий $n$ вершин, такой что диаметр $S_G$ не превышает $n - k$.
# Графы $G_1$, содержащий $n_1$ вершин и $m_1$ ребер, и $G_2$, содержащий $n_2$ вершин и $m_2$ ребер, гомеоморфны. Докажите, что $n_1+m_2 = n_2+m_1$.
# Докажите, что планарный эйлеров граф содержит эйлеров цикл, не имеющий самопересечений.
# Пусть планарный граф $G$ без петель и параллельных ребер содержит $n$ вершин. Какое максимальное число ребер он может содержать?
# Приведите пример планарного графа, который не является гамильтоновым.
# Докажите, что планарный четырехсвязный граф гамильтонов.
# Пусть $G$ - планарный граф, в котором каждый треугольник ограничивает область, не содержащую ребер, причем добавление любого ребра нарушает это свойство.
Докажите, что $G$ гамильтонов.
# Докажите или опровергните, что циклы вокруг граней образуют базис циклического пространства графа.
# Докажите, что любой трехсвязный планарный граф имеет остов, у которого наибольшая степень равна 3.
# Докажите, что все колеса самодвойственны.
# Найдите максимальное $k$, что граф $K_k$ можно уложить на торе.
# Найдите максимальное $k$, что граф $K_k$ можно уложить на сфере с двумя ручками.
# Докажите, что для любого $m$ существует $k$, такое что граф с $K_k$ нельзя уложить на сфере с $m$ ручками.
</wikitex>
