Список заданий по ДМ 2к 2023 осень

1. Постройте граф с $n$ вершинами, $m$ ребрами и $k$ компонентами связности. Здесь и далее """"постройте граф с $n$ вершинами, ..."""" означает, что вы должны рассказать способ для любого $n$ построить искомый граф, либо рассказать, для каких $n$ такой граф существует и указать способ его построить, а для остальных $n$ доказать, что такого графа не существует. Аналогично следует поступить с другими параметрами, указанными в условии задачи.
2. Обозначим как $N(u)$ множество соседей вершины $u$. Постройте граф с $n$ вершинами, в котором множества $N(u)$ совпадают для всех вершин $u$. Опишите все такие графы. Обозначим как $N[u]$ множество, содержащее вершину $u$, а также соседей вершины $u$. Постройте граф с $n$ вершинами, в котором множества $N[u]$ совпадают для всех вершин $u$. Опишите все такие графы.
3. Постройте граф с $n$ вершинами, где каждая вершина имеет степень $d$.
4. Докажите, что любой граф, содержащий хотя бы две вершины, имеет две вершины одинаковой степени.
5. Докажите, что в графе число вершин нечетной степени четно. Докажите, что если в графе ровно две вершины нечетной степени, то они лежат в одной компоненте связности.
6. Докажите, что для любого графа $G$ можно записать в каждой вершине $u$ такое число $d(u)$, что числа $d(u)$ и $d(v)$ имеют общий делитель, отличный от 1, тогда и только тогда, когда в графе $G$ есть ребро $uv$.
7. В графе $G$ можно записать в каждой вершине $u$ такое число $d(u)$, что числа $d(u)$ и $d(v)$ равны тогда и только тогда, когда в графе $G$ есть ребро $uv$. Что можно сказать про граф $G$?
8. Граф называется кубическим, если степень всех вершин равна 3. Три вершины графа образуют треугольник, если они попарно соединены ребром. Постройте кубический граф с $n$ вершинами, не содержащий треугольников.
9. Доказать или опровергнуть, что если ребро $uv$ - мост, то $u$ и $v$ - точки сочленения. Доказать или опровергнуть, что если $u$ и $v$ - точки сочленения, то $uv$ - мост.
10. Рассмотрим отношение на рёбрах - $R$. $ab R cd$, если 1) $ab$ и $cd$ имеют общую вершину; 2) $ab$ и $cd$ лежат на простом цикле. Доказать, что вершинная двусвязность - это $R^*$.
11. Доказать, что ребро $uv$ - мост тогда и только тогда, когда $uv$ вершинно двусвязно только с самим собой.
12. Обозначим как $\delta(G)$ минимальную степень вершины $G$. Докажите, что если в графе с $n$ вершинами $\delta(G) > (n - 1) / 2$, то он связен.
13. Докажите, что наименьшее число вершин в кубическом графе, в котором есть мост, равно 10.
14. Докажите, что любой кубический граф, который содержит точку сочленения, содержит также мост.
15. Докажите, что граф связен тогда и только тогда когда для любого разбиения его множества вершин $V$ на два непустых непересекающихся множества $X$ и $Y$ существует ребро, соединяющее эти множества.
16. Докажите, что либо граф $G$, либо его дополнение $\overline{G}$ связен.
17. Будем говорить, что $G$ связан короткими путями, если между любыми двумя вершинами в $G$ есть путь длины не более 3. Докажите, что либо $G$, либо $\overline G$ связан короткими путями. Приведите пример графа, что ни он, ни его дополнение не связаны путями длины не больше 2.
18. Граф называется самодополнительным, если он изоморфен своему дополнению. Приведите примеры самодополнительных графов с 4 и 5 вершинами. Докажите, что если граф является самодополнительным, то он содержит либо $4n$ либо $4n+1$ вершину для некоторого целого положительного $n$.
19. Докажите, что для любого целого положительного $n$ существует самодополнительный граф, содержащий $4n$ вершин, а также самодополнительный граф, содержащий $4n+1$ вершину.
20. Докажите, что в связном графе любые два самых длинных простых пути имеют общую вершину.
21. Докажите или опровергните, что в связном графе все простые пути, имеющие максимальную возможную длину в этом графе, имеют общую вершину.