Задача про 9 мушкётеров

Задача
Среди 9 мушкетеров некоторые поссорились и вызвали друг друга на дуэль. Докажите, что если среди низ нет трех которые должны драться друг с другом, то среди мушкетеров найдутся четверо друзей.
помогите решить пожалуйста))

Переведем задачу на язык теории графов. Надо доказать, что в любом неориентированном графе с 9 вершинами, в котором нет циклов из трех вершин, найдутся 4 вершины, среди которых никакие две не соединены ребром. Будем рассуждать от противного. Надо доказать, что если нет циклов из трех вершин и среди любых четырех вершин две соединены ребором, то такого графа не бывает.
1. Пусть максимальная степень вершины в графе больше трех. Тогда рассмотрим вершину и инцидентные ей. Их будет больше трех, не меньше 4. Берем любые 4 из них, между ними есть ребро — вот он цикл длины три.
2. Пусть максимальная степень вершин не больше 3. Покажем, что если есть вершина со степенью меньше 3 (0, 1 или 2), то найдется цикл длины три.
Пусть есть вершина А степени 2. У нее есть две соседних В, С. Остается 6 вершин, не соединенных с А.
Возьмем четверку, содержащую А и какие-то три вершины из тех шести. А не соединено ни с одной вершиной из тех шести, поэтому среди каждых трех вершин из тех шести найдутся две, соединенные ребром. Несложно показать, что в этом случае степени каждой из тех шести вершин равны трем, поэтому они никак не могут быть соединины с В и С. Противоречие.
3. Для вершины степени 1 и изолированной вершины получится точно такой же результат.
Поэтому изначальное предположение не верно и среди всех девяти вершин найдутся четыре, между которыми не будет ребер, то есть найдутся четверо друзей.

Пытаюсь перевести Ваши рассуждения на понятный язык.

Теорема. Если в графе с 9 вершинами из любых 4 вершин хотя бы две
соединены ребром, то найдутся 3 вершины, соединённые рёбрами попарно.

Доказательство.
1) Пусть существует вершина A степени 4 (или более).
Рассмотрим четырёх её соседей. Из них есть два соседа, соединённых
ребром. Вместе с вершиной A они образуют цикл длины 3.

2) Пусть максимальная степень вершин в графе не более 3.

2а) Пусть при этом существует вершина A степени 2. Её соседей
обозначим B и C, а оставшиеся вершины обозначим D1, D2, D3, D4, D5, D6.

Лемма 1. Среди каждых трёх вершин из набора D1, D2, D3, D4, D5, D6
две какие-то соединены ребром.

Доказательство леммы 1. Действительно, пусть Di, Dj, Dk (1 <= i,j,k <=6) —
произвольные три вершины из этого набора. Рассмотрим четвёрку A, Di, Dj, Dk.
Так как A не соединено ни с одной из вершин Di, Dj, Dk, то какие-то две
вершины из вершин Di, Dj, Dk соединены ребром. Лемма 1 доказана.

Далее сутормин говорит: Несложно показать, что справедлива лемма 2.
Лемма 2. Каждая из вершин D1, D2, D3, D4, D5, D6 соединена ровно с тремя
вершинами из этого же набора. (Это имеется в виду, когда утверждается,
что степень каждой из вершин D1, D2, D3, D4, D5, D6 равна 3?)

А как показать справедливость леммы 2 — непонятно.

Лемма 3. Никакая из вершин D1, D2, D3, D4, D5, D6 не может быть соединена
с B или C.
Доказательство леммы 3. Если Di соединена с B или C, то её степень будет
более 3, что не соответствует рассматриваемому случаю, когда максимальная
степень вершин графа не более 3. Лемма 3 доказана.

Как говорит сутормин, мы получили противоречие.
А в чём и с чем противоречие?

Четверо рабочих изготовили 160 деталей. Второй рабочий изготовил 3/5 количества деталей изготовленным первым, третий изготовил 50% того, что изготовил второй, а четвёртый на 6 деталей больше, чем третий. Сколько деталей изготовил каждый рабочий?

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

В семье четверо детей.Им 5,8,13 и 15 лет. Детей зовут Аня.Боря,Вера и Галя. Сколько лет каждому ребенку,если одна девочка ходит в детский сад, Аня старше Бори и сумма лет Ани и Веры делится на 3,

Четверо отправились на экскурсию. Трое из них захватили с собою еду: первый — 4, второй — 3, третий — 1 бутерброд. Бутерброды разделили между всеми поровну. Четвертый должен был возместить 1руб.20коп., и он дал первому 60 копеек, второму — 45, третьему — 15 копеек. Но первый стал возражать. Прав ли он?"

Пароход от Киева до Херсона идет трое суток, а от Херсона до Киева четверо суток (без остановок). Сколько времени будут плыть плоты от Киева до Херсона?

Среди 9 мушкетеров некоторые поссорились и вызвали друг друга на дуэль. Докажите, что если среди низ нет трех которые должны драться друг с другом, то среди мушкетеров найдутся четверо друзей.
иискал в нете нигде нету