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