ПитерГор 2017

Подсказка 1

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

Подсказка 2

Разумеется, это означает, что граф связный, то есть в графе ровно 1 компонента связности. И доказать нас просят, что какая-то штука равна 1. Но пока что рано выдвигать гипотезы. Посмотрим на хордовый граф с двумя компонентами, каждая из которых — треугольник. Посчитаем выражение из условия для этого экспериментального графа. Чему же оно равно?

Подсказка 3

Оно равно двум! И компоненты у нас две. Хмм... А вот сейчас уже можно выдвинуть гипотезу.
Как же будет звучать наше предположение?

Подсказка 4

"Для хордового графа с k компонентами связности выражение из условия равно k". Звучит масштабно. Кажется, доказывать это напрямую будет сложновато, придётся всё считать и доказывать... Попробуем сделать это по-другому. Предположим противное... Но этого будет маловато. Запомните, что в подобного рода утверждениях стоит попробовать применить принцип крайнего!

Подсказка 5

Пусть G — наименьший по количеству вершин граф, который не удовлетворяет предположению. Как-то хотим начать работать с графом. Хотим как-то в ходе доказательства сослаться на минимальность примера, то есть как-то перейти к графам меньших размеров. Как же это можно сделать?

Подсказка 6

Поудалять вершины! Начнём с одной — вершины Y. Пусть наш граф распался на n компонент связности G₁, G₂, ..., Gₙ. Для дальнейшего удобства обозначим с₁ - с₂ + … за f(X) для графа Х. Здесь мы как-раз таки воспользуемся тем, что граф G — минимальный контрпример для нашего предположения, то есть f(G₁) = ... = f(Gₙ) = 1. Хотим как-то связать f(G) и f(G₁), .., f(Gₙ). Но в f(Gᵢ) учтены только клики без Y. Как бы нам посчитать или хотя бы учесть клики с вершиной Y?

Подсказка 7

Клики с участием Y построены на соседях Y (смежных с Y вершинах). Значит, нам нужно отдельно поработать с соседями Y. Пусть Hᵢ — вершины в Gᵢ, которые связаны с Y (соседи) для всех i. Как же нам теперь учесть клики с вершиной Y?

Подсказка 8

f(Hᵢ) — количество клик с участием Y на вершинах, принадлежащих Gᵢ (формально, это клики без участия Y, образованные на вершинах Hᵢ, но все они становятся нужными кликами, если к ним добавить Y, поэтому численные значения совпадают). Итак, какая же итоговая формула для f(G) через f(Hᵢ) и f(Gᵢ)?

Подсказка 9

Докажите, что f(G) = 1 + Σ f(Gᵢ) - Σ f(Hᵢ). Хотим доказать, что f(G) = 1, то есть Σ f(Hᵢ) = n или же f(Hᵢ) = 1 для всех i. Утверждение равносильно тому, что все подграфы Hᵢ — связные. Вспомните, что мы ещё не использовали.

Подсказка 10

Именно! Хордовость графа G. Предположите, что (не умаляя общности) H₁ — не связный, то есть в нём есть хотя бы две компоненты A и B. Осталось доказать, что в этом случае есть цикл длины хотя бы 4 без хорды внутри, иначе говоря, получить, что G — не контрпример. Уверены, у Вас получится! Успехов!