Задание №180816: Командная олимпиада 2024

Решение. Легко убедиться, что при k = 1 можно выбрать какое-то ребро. Пусть
n
k = 2. Тогда в нашем графе на n вершинах есть больше ребер, а значит какие-
2
то два имеют общую вершину. В дальнейшем будем считать, что k ⩾ 3. Заметим
также, что в любой момент граф можно считать связным. В противном случае
можно выбрать компоненту, в которой неравенство на ребра будет выполнятся
в силу линейности, и свести все к меньшему числу вершин.
Зафиксируем k. Докажем утверждение задачи с помощью индукции по n. Ба-
за при n = 2 очевидна. Докажем индукционный переход. Пусть для n вершин
мы доказали утверждение для всех таких графов, удовлетворяющих условию.
Рассмотрим граф на n + 1 вершине. Если найдется вершина с маленьким ко-
k + 1
личеством ребер (а именно менее ), то можно ее отбросить и применить
2
предположение индукции. Тогда можно считать, что каждая вершина имеет
k + 1
степень хотя бы .
2
Выберем самый длинный путь v v ...v в этом графе. С учетом рассмотренного
0 1 t
ранее можно считать, что t ⩾ 2. Первая ситуация: v и v соединены ребром.
0 t

Вспомним про связность и заметим, что если есть еще вершины, то от нашего
цикла v v ...v должно быть ребро к ним, а тогда можно построить более длин-
0 1 t
ный путь. Тогда t = n. Но тогда естественная оценка на суммарное число ребер
t(t + 1) (t + 1)(k − 1)
> эквивалентно t ⩾ k, а это значит, что есть путь длины
2 2
k.
Вторая ситуация: между v и v нет ребра. Рассмотрим вершину v . В силу
0 t 0
выбора максимального пути ее соседи могут быть только среди v , ..., v . С
1 t−1
k + 1
другой стороны у каждой вершины степень хотя бы . Тогда среди внутрен-
2
k − 1
них вершин пути v , ..., v у нее не менее соседей. Рассмотрим какую-то
2 t−1 2
из этих вершин v . Если она соседствует с v , то v не будет соседствовать с
r 0 r−1
v , поскольку в этом случае можно построить цикл v v v v ...v v v ...v и
t r 0 1 2 r−1 t t−1 r+1
свести все к первому случаю. Следовательно, у вершины v в этом пути соседей
t
k − 1 k + 1 k − 1
не более (t−2− )+1. Получаем оценку ⩽ d(v ) ⩽ (t−2− )+1,
2 2 t 2
а значит t ⩾ k, поэтому нужный путь найдется.
Форум Art of solving problems