Теория графов, задача на клики

[TheOne]

Привет, всем)))
Помогите, пожалуйста, решить задачу по теории графов, нужно срочно:

Некоторые участники олимпиады дружат, и дружба взаимна. Назовем группу участников кликой, если все они дружат между собой. Их число называется размером клики. Известно, что максимальный размер клики четен. Докажите, что участников можно рассадить по двум аудиториям так, что максимальные размеры клик в обеих аудиториях совпадают.


Буду очень благодарна)

AKM:

Ознакомьтесь с Правилами форума. Заголовок отредактирован

Цитата:

I-1-и. Заголовки тем должны быть информативными. Не допускается использование "кричащих" выражений типа "Help!!!", "Помогите", "Горю", "Очень срочно надо" и т.п. Сообщения подобного типа могут быть удалены администрацией.
I-1-к. Запрещается злоупотребление средствами форматирования с целью привлечь внимание к своему сообщению (в частности, КАПСЛОКИНГ), а также чрезмерное использование знаков препинания и смайлов.

[gris]

Возьмите эту максимальную клику и разделите на две равные части. Заведите в аудитории. А остальных начните разводить по аудиториям так, чтобы размер первоначальных клик не увеличивался. Только вот не может ли образоваться новая клика...

[Brukvalub]

Сначала посадите максимальную клику в первую аудиторию, а всех остальных участников - во вторую. Затем пересадите несколько пар участников из первой аудитории во вторую так, чтобы либо размеры максимальных клик сравнялись, либо число людей в первой аудитории превосходит размер максимальной клики во второй аудитории на 1, после чего пересадите во вторую аудиторию еще 1 чел. Детали доказательства того, что описанный мной процесс решает задачу - додумайте сами.