задачка для небольшой разминки

ну тогда очевидно длина цикла С не меньше k+1. k+1 > sqrt(k)

Сам цикл C может быть и короче, потому что не сказано что путь принадлежит циклу.

А почему именно sqrt(k), можно поинтересоваться?

ну тогда очевидно длина цикла С не меньше k+1

нет.

А почему именно sqrt(k), можно поинтересоваться?

ну такая вот граница

Сам цикл C

А какая разница, может и не цикл C, так даже лучше, получается ещё джва цикла (путь длиной k + пути от v к w через C), длина которых больше k

получается ещё джва цикла (путь длиной k + пути от v к w через C), длина которых больше k

не факт, что такие циклы существуют. Для этого пути от v к w через C должны не пересекаться с путем, который k.

а что нужен простой цикл, условия не было

Ещё можно тупо мотать круги через C, пока длина не превзойдёт sqrt(k)

а что нужен простой цикл, условия не было

очевидно, что подразумеваются именно такие.

Кто-то в пятом классе знал, что такое граф?

Я в 5 классе знал, что граф - это титул

Граф ориентированный или нет?

нет

А если бы тебе сказали, что в титуле какой-то цикл?

Рассмотрим путь v=v0, v1, v2,..., vk=w. Пусть S={i | vi принадлежит C}. Очевидно, 0 и k принадлежат S. Если #S >= sqrt(k), то цикл C содержит как минимум sqrt(k) вершин, то есть имеет длину не меньше sqrt(k). Предположим, что #S < sqrt(k); перенумеруем элементы S: S = {i0=0, i1, i2,..., in=k}. Тогда (i1-i0) + (i2-i1) + ... + (in-i{n-1}) = in-i0 = k, и количество слагаемых равно #S-1 < sqrt(k). Значит, при каком-то j, ij - i{j-1} > sqrt(k); в противном случае вся сумма была бы не больше sqrt(k)*(#S-1) < k. По определению S, все вершины vm при i{j-1}<m<ij не принадлежат циклу C; значит, добавив к отрезку нашего пути между i{j-1} и ij кусок цикла C, соединяющий ij с i{j-1}, мы получаем простой цикл, и его длина будет не меньше sqrt(k).

Предположим, что #S < sqrt(k); перенумеруем элементы S: S = {i0=0, i1, i2,..., in=k}. Тогда (i1-i0) + (i2-i1) + ... + (in-i{n-1}) = in-i0 = k,

вот тут непонятно. Почему in=k? Или эта нумерация как-то связана с v0...vk?

Потому что k принадлежит S.

Сейчас и в 6 классе не знают. Но бегут и постят свои догадки на ЛОР.

все верно.

PS
можно получить кстати еще лучшую оценку, но идея все равно та же.