292
правки
Изменения
Нет описания правки
# Докажите, что наименьшее число вершин в кубическом графе, в котором есть мост, равно 10.
# Докажите, что любой кубический граф, который содержит точку сочленения, содержит также мост.
# Докажите или опровергните, что в связном графе все простые (а) любые два пути, имеющие максимальную возможную длину в этом графе, имеют общую вершину.(б) Верно ли что все самые длинные простые пути обязательно имеют общую вершину?
# Докажите, что либо граф $G$, либо его дополнение $\overline{G}$ связен.
# Будем говорить, что $G$ связан короткими путями, если между любыми двумя вершинами в $G$ есть путь длины не более 3. Докажите, что либо $G$, либо $\overline G$ связан короткими путями. Приведите пример графа, что ни он, ни его дополнение не связаны путями длины не больше 2.
