Простая комбинаторика, графы

[prrrr]

Здравствуйте!

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

Задача:
Каждого из посетителей праздника спросили, сколько у него знакомых среди присутствующих на празднике. Ответы: 2, 2, 2, 3, 3, 6, 6, 7, 7. Нужно доказать, что кто-то ошибся.

Мое решение:
Представим посетителей в виде графа с 9 вершинами степени которых соответствуют числу знакомых (2, 2, 2, 3, 3, 6, 6, 7, 7).
Количество ребер в графе равно сумме степеней его вершин деленое на 2. Таким образом получаем, что число ребер в графе равно: (2+2+2+3+3+6+6+7+7)/2 = 19.
Полученное количество ребер (19) нечетно, значит в графе должно быть нечетное количество пар вершин нечетной степени (вот это доказать не знаю как, если это вообще возможно), а это противоречит условию, т.к. по условию у нас две пары вершин нечетной степени: 3+3 и 7+7. Следовательно, такой граф построить невозможно и значит кто-то ошибся.

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

Большое спасибо за идеи!))

[TOTAL]

Ответы: 2, 2, 2, 3, 3, 6, 6, 7, 7. Нужно доказать, что кто-то ошибся.

Группа $6, 6, 7, 7$ должна иметь минимум $3+3+4+4=14$ знакомств на стороне. А там не хватает.

[prrrr]

TOTAL в сообщении #1546399 писал(а):

Группа $6, 6, 7, 7$ должна иметь минимум $3+3+4+4=14$ знакомств на стороне.

Подскажите пожалуйста, почему так? Не понимаю..

[lel0lel]

Сколько максимальное количество знакомых в группе у каждого участника?

[mihaild]

prrrr в сообщении #1546401 писал(а):

Подскажите пожалуйста, почему так?

В этой группе 4 человека, один из них Вася. Всего у Васи 6 знакомых. Сколько максимум у Васи знакомых в этой группе? Сколько минимум у Васи знакомых не в этой группе?

[prrrr]

lel0lel в сообщении #1546402 писал(а):

Сколько максимальное количество знакомых в группе у каждого участника?

Максимально теоретически у каждого может быть 8 знакомых, т.к. всего 9 человек.

-- 18.01.2022, 16:36 --

mihaild в сообщении #1546403 писал(а):

В этой группе 4 человека, один из них Вася. Всего у Васи 6 знакомых. Сколько максимум у Васи знакомых в этой группе? Сколько минимум у Васи знакомых не в этой группе?

Да, точно, теперь понял) Спасибо!

[prrrr]

Пока получается такое решение:
Представим посетителей в виде графа. Получим граф с $9$ вершинами (по числу ответов), степени которых соответствуют числу знакомых каждого посетителя $(2, 2, 2, 3, 3, 6, 6, 7, 7)$.
Количество ребер в графе равно сумме степеней его вершин деленое на $2$. Таким образом получаем, что число ребер в графе равно: $(2+2+2+3+3+6+6+7+7)/2=19$.
Рассмотрим для примера группу вершин графа в которую входят $4$ посетителя, ответившие $6, 6, 7, 7$. Максимально в данной группе может быть $6$ ребер (в случае, если каждый из группы знаком с каждым). Значит во второй группе вершин (в которую входят $5$ посетителей, ответившие $2, 2, 2, 3, 3$) ребер, связанных с этими вершинами, должно быть $13$ $(19-6=13)$. Однако, сумма степеней вершин во второй группе (количество ребер, прилегающих к вершинам второй группы) равна $12$ $(2+2+2+3+3=16)$, противоречие. Значит такой граф построить нельзя и, следовательно, кто-то ошибся.