7 друзей за столом

[jrock]

Я догадываюсь, что это стандартная олимпиадная задача. Эта задача идет в контексте этих:
topic68318.html
topic68141.html

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

Доказательство.
Построим граф: вершины - люди, ребра- знакомства. Если получиться пройтись гамильтоновым циклом (г.цикл) по всем вершинам, то получим решение.
Теперь в графе есть 6 реберно-простых циклов, нужно доказать что есть г.цикл.
Очевидно, что степень каждой вершины хотя бы 2 (иначе как бы она была в цикле). Но если степень какой-то вершины 2, то рассмотрим цикл по вершинам без одной смежной с рассматриваемой. По условию задачи должен появится цикл. Значит, степень каждой вершины хотя бы 3.
Но в нечетных вершин четное число, значит есть вершина степени 4.
Если был г.цикл и граф по 6-ти вершинам, очевидно, связен, то был и г.путь по всему графу для каждой пары вершин.
Если был г.путь, начало которого был степени 4, а конец пути - любая другая вершина, то получится г.цикл: сумму степеней крайних вершин г.пути равна длине пути. ч.т.д.



Вообще у меня есть сильное ощущение, что это утверждение верно в общем случае: есть г.цикл в графе, где между любыми n-1 есть ребрено-простой путь.
Доказывать, видимо, нужно опираясь на то, что появятся треугольники. Если появится хотя бы один треугольник, то возьмем г.путь из любых двух его вершин и превратим в г.цикл.
Вот только проблема в том что на этом форуме я вообще не получаю фидбека никакого и кажется что всем не очень-то интересно :)

[Aritaborian]

(Оффтоп)

Позабавило «Вы можете выбрать до двух вариантов ответа» ;-)

[Sender]

jrock в сообщении #679798 писал(а):

Вообще у меня есть сильное ощущение, что это утверждение верно в общем случае: есть г.цикл в графе, где между любыми n-1 есть ребрено-простой путь.

Кажется, при ощущениях подобного рода помогает граф Петерсена.

[jrock]

Sender в сообщении #679817 писал(а):

jrock в сообщении #679798 писал(а):

Вообще у меня есть сильное ощущение, что это утверждение верно в общем случае: есть г.цикл в графе, где между любыми n-1 есть ребрено-простой путь.

Кажется, при ощущениях подобного рода помогает граф Петерсена.

Вот все и сломалось.

-- 04.02.2013, 17:02 --

Ранее я писал следующее:

jrock в сообщении #679798 писал(а):

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

Утверждение сомнительно. Попробуем расписать и упростить.

Итак, докажем что есть г.цикл в графе. Действительно, возьмем вершину $u$ степени 4. Если рассмотреть граф на 6-ти вершинах, в котором не будет $u$, то будет г.цикл по условию. Значит, через $u$ можно добраться до каких-то 4-х вершин в г.цикле на 6-ти вершинах.
Пускай не получилось так, что вершина $u$ знакома с 4-мя товарищами, но не получилось треугольника. Тогда покрасим колечко из 6-ти друзей в разные цвета: красный и зеленый, где красный - эта вершина незнакома с $u$, а зеленый- знакома с $u$. В таком колечке обязательно между двумя зелеными хотя бы одно красное. Значит, если взять кольцо из 4-х вершин, то туда нужно вставить хотя бы еще 4-ре красных. Но у нас всего шесть вершин. Значит, есть два (и даже три) зеленых, между которыми нет красного. Значит, верно следующее:
Получилось так, что $u$ знает двух знакомых: теперь просто уберем ребро между двумя знакомыми и получится, что $u$ знакома с концами г.пути. Это автоматически г.цикл.