210
правок
Изменения
Нет описания правки
# Рассмотрим отношение на рёбрах - $R$. $ab R cd$, если 1) $ab$ и $cd$ имеют общую вершину; 2) $ab$ и $cd$ лежат на простом цикле. Доказать, что вершинная двусвязность - это $R^*$.
# Доказать, что ребро $uv$ - мост тогда и только тогда, когда $uv$ вершинно двусвязно только с самим собой.
# Обозначим как $\delta(G)$ минимальную степень вершины $G$. Докажите, что если в графе с $n$ вершинами $\delta(G) > (n - 1) / 2$, то он связен.
# Докажите, что наименьшее число вершин в кубическом графе, в котором есть мост, равно 10.
# Докажите, что любой кубический граф, который содержит точку сочленения, содержит также мост.
