#9 Графы I

Сумма степеней равна \(2+2+3+3+4=14\). Каждое ребро считается дважды, поэтому ребер \(14/2=7\).

Сумма степеней равна \(3\), она нечетна. Но сумма степеней любого графа равна \(2E\), то есть четна. Такого графа не существует.

Нужно выбрать две вершины из \(8\). Поэтому число ребер равно \(\binom{8}{2}=28\).

Путь из \(6\) вершин имеет \(5\) ребер, значит сумма степеней равна \(10\). Цикл из \(6\) вершин имеет \(6\) ребер, значит сумма степеней равна \(12\).

Построим граф знакомств. Каждая пара знакомых дает вклад \(1\) в степень каждого из двух людей, то есть вклад \(2\) в общую сумму. Поэтому сумма всех названных чисел равна удвоенному числу пар знакомых и четна.

Сумма всех степеней равна \(2E\), значит она четна. Сумма степеней четных вершин четна. Поэтому сумма степеней вершин нечетной степени тоже четна. Сумма нечетного количества нечетных чисел была бы нечетной, значит число таких вершин четно.

Сумма степеней равна \(36\). Она вдвое больше числа ребер, значит ребер \(36/2=18\).

Каждое ребро получается выбором одной вершины из первой доли и одной из второй. Поэтому ребер \(4\cdot7=28\).

Минимум равен \(10-1=9\). Достигается, например, на пути из \(10\) вершин. Меньше быть не может, потому что для присоединения каждой новой вершины к уже построенной связной части нужно хотя бы одно ребро.

В дереве на \(n\) вершинах ровно \(n-1\) ребер. Поэтому при \(n=15\) получаем \(14\) ребер.

В простом графе между двумя вершинами не более одного ребра. Максимум ребер - в полном графе \(K_8\), где их \(\binom{8}{2}=28\). Поэтому \(29\) ребер быть не может.

Если есть человек, знакомый со всеми \(5\) остальными, то каждый другой знаком хотя бы с ним. Тогда не может быть человека с \(0\) знакомых. Значит набор степеней \(0,1,2,3,4,5\) невозможен.

Степени могут быть числами \(0,1,\ldots,2n-1\). Однако степени \(0\) и \(2n-1\) не могут встречаться одновременно: если кто-то знаком со всеми, то никто не имеет \(0\) знакомых. Поэтому реально доступно не более \(2n-1\) разных значений степеней. Людей \(2n\), значит по принципу Дирихле у двух степени совпадают.

Если в графе нет циклов, то каждая его компонента является деревом. Если компоненты имеют размеры \(n_1,\ldots,n_k\), то ребер в них \((n_1-1)+\cdots+(n_k-1)=n-k\le n-1\). Значит граф без циклов имеет не более \(n-1\) ребер. Если ребер хотя бы \(n\), цикл обязателен.

Предположим, что цикл есть. Удалим одно ребро этого цикла. Между его концами все равно остается путь по остальной части цикла, поэтому граф остается связным. Тогда получится связный граф на \(n\) вершинах с \(n-2\) ребрами, что невозможно, так как связный граф имеет не меньше \(n-1\) ребер. Значит циклов нет.

Рассмотрим самый длинный простой путь в дереве. Пусть его конец - вершина \(v\). Если у \(v\) есть сосед, не лежащий на пути, путь можно продолжить, противоречие. Если у \(v\) есть сосед на пути кроме ближайшего, возникнет цикл, что невозможно в дереве. Значит у \(v\) ровно один сосед, степень \(1\). То же верно для другого конца пути.

Если граф несвязен, его вершины разбиваются как минимум на две компоненты. Одна из компонент имеет не более \(3\) вершин. Внутри такой компоненты любая вершина может быть соединена максимум с \(2\) другими вершинами, значит ее степень не больше \(2\). Это противоречит условию, что все степени не меньше \(3\).

Каждое ребро выходит из ровно одной вершины доли размера \(5\). Поэтому сумма степеней вершин этой доли равна \(20\). Средняя степень равна \(20/5=4\). Значит хотя бы одна вершина имеет степень не меньше \(4\).

Всего партий \(\binom{7}{2}=21\), значит всего побед тоже \(21\). Среднее число побед на игрока равно \(21/7=3\), поэтому кто-то выиграл не менее \(3\) партий. Аналогично всего поражений \(21\), среднее число поражений равно \(3\), значит кто-то проиграл не менее \(3\) партий.

Если граф несвязен, возьмем одну компоненту. Если ее размер не больше \(6\), то степень любой вершины в ней не больше \(5\), противоречие. Значит каждая компонента должна иметь хотя бы \(7\) вершин. Но две такие компоненты уже содержали бы хотя бы \(14\) вершин, больше чем \(11\). Поэтому компонент больше одной быть не может, граф связен.

Возьмем вершину \(v\). У нее есть хотя бы \(5\) соседей. Если среди этих соседей есть ребро, то вместе с \(v\) получаем треугольник. Если ребер между соседями \(v\) нет, то каждый из этих соседей соединен с \(v\) и может быть соединен только с тремя вершинами, не входящими в множество соседей \(v\) и не равными \(v\). Тогда его степень не больше \(1+3=4\), что противоречит минимальной степени \(5\). Значит треугольник существует.

Пусть листьев \(L\), а вершин степени \(3\) - \(T\). Тогда \(L+T=12\). В дереве \(11\) ребер, значит сумма степеней \(22\). Поэтому \(L+3T=22\). Вычитая первое уравнение, получаем \(2T=10\), значит \(T=5\), а \(L=7\).

Так как ребер столько же, сколько вершин, граф содержит цикл. Возьмем любое ребро этого цикла. Если его удалить, концы этого ребра все равно будут соединены путем по остальной части цикла. Все остальные связи тоже сохраняются, значит граф остается связным.

Выберем человека \(A\). Среди остальных \(5\) человек по принципу Дирихле есть либо \(3\), знакомые с \(A\), либо \(3\), не знакомые с \(A\). Пусть сначала \(A\) знаком с \(B,C,D\). Если среди \(B,C,D\) есть знакомая пара, например \(B\) и \(C\), то \(A,B,C\) - три попарно знакомых. Если же среди \(B,C,D\) нет знакомых пар, то \(B,C,D\) - три попарно незнакомых. Второй случай, когда есть \(3\) человека, не знакомые с \(A\), аналогичен: если среди них есть незнакомая пара, она вместе с \(A\) дает тройку незнакомых; если нет, то эти трое попарно знакомы.