Пост из http://dxdy.ru/topic12472.html

[El Mar]

В задаче 5 имеется в виду путь с длиной <= 2.

Доказательство индукцией по числу вершин.
Для 2 - очевидно.
Пусть верно для G(n), и s - вершина, удовлетворяющая условию.
=> множество вершин G(n) разбивается на {s}, множество вершин с расстоянием 1 от s, P, и множество вершин с расстоянием - 2.
Если одна из вершин {s} U P входит в (n+1)-ю, то s - остается вершиной, удовлетворяющей условию.
В противном случае сама (n+1)-я вершина удовлетворяет условию.

[Deggial]

Пост перемещён в Карантин по следующим причинам:
1. Формулы не оформлены $\TeX$ом. Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
2. Правилами форума запрещено выкладывать полное решение простых учебных задач, можно лишь помогать участнику в их решении.
3. Некропост: в архивные темы не нужно постить, исключая случая нерешенных сложных задач.

Если есть, что исправить и сообщить в тему, то исправьте пост, а после исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.