Друзья бродят по графу // ЛКТГ 2023

В этой задаче мы рассматриваем конечные неориентированные графы без петель и кратных ребер. Если G — граф, то через V (G) обозначается множество его вершин, E(G) — множество ребер, δ(G) — минимальная степень вершины. Кроме того, мы используем стандартные обозначения графов: P_{n} — путь из n вершин, C_{n} — цикл из n вершин, K_{m,n} — полный двудольный граф с долями по m и n вершин, граф K_{1, n−1} будем называть звездой и обозначать Star_{n}. Вершина x0 графа G называется точкой сочленения, если после ее удаления из графа G количество компонент связности в образовавшемся графе больше, чем в исходном. Связный граф без точек сочленения называется двусвязным. Мост — это ребро uv, при удалении которого граф распадается на две компоненты. Если ни одна из вершин u, v не является висячей вершиной графа G, будем называть мост существенным. Граф H называется индуцированным подграфом графа G, если V (H) ⊂ V (G) и E(H) = {uv ⊂ E(G) : u ∈ V (H), v ∈ V (H)}. Материалы: Проект представляют Бурсиан О., Кохась Д., Кохась К., Ретинский В. Летняя конференция Международного математического Турнира городов, Дубна 1-10 августа 2023 г.