Помогите реализовать связное доказательство на графах

[externo]

Пусть граф G = ⟨V,E⟩ простой, связный, но не полный. Показать, что тогда существуют
три такие точки u, v, w, что ребра (u, v) i (v, w) принадлежат E, а ребро (u, w) – нет.

[Brukvalub]

Раз граф не полный, то есть две вершины u , v которые не соединены ребром. Раз граф связный, то от $u$ к $v$ можно добраться по цепочке соединенных ребрами вершин $u , w_1 , w_2 , ... w_n , v$ . Если $u$ и $w_2$ не соединены ребром, то нужная тройка найдена, иначе... Продолжите рассуждение и придите к противоречию, если нужной тройки не найдется.

[Lia]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);
- отсутствуют собственные содержательные попытки решения задач(и).

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.