ALG-B2-M01-P026 Степени соседних вершин

Подсказка 1. Разбейте вершины на классы \(X_i\) по степени.

Подсказка 2. Рассмотрите максимальную степень \(m\): случаи \(m\le k-1\), \(m\ge k+1\), \(m=k\).

Ответ: \(k(k-1)\). Пример: возьмём одну изолированную вершину, остальные разобьём на множества \(X\) и \(Y\) размеров \(k\) и \(k-1\), и проведём все рёбра между \(X\) и \(Y\). Тогда степени вершин из \(X\) равны \(k-1\), из \(Y\) равны \(k\), условие выполнено, рёбер \(k(k-1)\).

Докажем оценку. Пусть \(X_i\) — множество вершин степени \(i\), а \(m\) — максимальная степень. Если \(m\le k-1\), то \(2E\le2k(k-1)\), значит \(E\le k(k-1)\).

Если \(m\ge k+1\), возьмём вершину степени \(m\). Все её соседи имеют степень \(m-1\), значит \(|X_{m-1}|\ge m\). Любая вершина из \(X_{m-1}\) имеет \(m-1\) соседей в \(X_m\cup X_{m-2}\), поэтому вместе классы \(X_{m-1},X_m,X_{m-2}\) содержат как минимум \(m+(m-1)>2k\) вершин, противоречие.

Остался случай \(m=k\). Рёбра соединяют только соседние по степени классы, поэтому граф двудолен относительно \(Y=X_k\cup X_{k-2}\cup\cdots\) и \(Z=X_{k-1}\cup X_{k-3}\cup\cdots\). С одной стороны, \(E\le k|Y|\), с другой — \(E\le(k-1)|Z|\). Если \(|Y|\le k-1\), то \(E\le k(k-1)\). Если \(|Y|\ge k\), то \(|Z|\le k\), и \(E\le(k-1)k\). Оценка доказана.

A. Анализ источника. Главные объекты: неравенства, порядок, экстремальный элемент или инвариант. Очевидный первый ход обычно даёт только локальную оценку. Скрытое наблюдение: надо выбрать правильную величину, которая не может уменьшаться, либо перемножить/сложить неравенства только после проверки знаков. Нужный шаг: переход к упорядоченной записи, инварианту, произведению или граничному случаю.

F. Обоснование сложности. Региональный уровень 7: это счётная оценка с тремя случаями по максимальной степени.

G. Почему это не одноходовая задача. Пример не доказывает максимум; верхняя оценка требует разбиения по степеням.