Индукция в графах и теорема Турана

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

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