Team selection test for 50. IMO

Разглеждаме граф $G$ с върхове градовете в държавата и ребра пътищата между тях. От всички подграфи на $G$ да изберем граф $H$, който има свойството на $G$ и е минимален по отношение на броя на върховете.
Да изберем произволен връх $v_t$ на $H$, който не разделя графа на две несвързани компоненти (не е трудно да се види, че такъв връх съществува). От минималността на $H$ следва, че съществува връх $v_0 \in H$, за който $d(v_0, w) \le t - 1$ за всички върхове $w \ne v_t$. Тъй като $t$ е най-малкото естествено число, за което съществува град, от който до всеки друг град може да се стигне, минавайки по най-много $t$ пътя, то $d(v_0, v_t) = t$. Нека $v_0, v_1, \dots, v_t$ е пътят от $v_0$ до $v_t$. Отново поради свойството на $H$ съществува връх $w$, за който $d(v_2, w) \ge t$ и за този връх също имаме $d(v_0, w) \le t - 1$.

При $t = 2$ търсеният път е $v_0v_1v_2$. Нека $t \ge 3$. Поради $d(v_2, w) \ge t$ имаме, че $w \ne v_i$. Нека $u$ е произволен връх от пътя между $v_0$ и $w$ и нека $d(v_0, u) = p$ и $d(u, w) = q$. Да допуснем, че $d(u, v_i) = 1$ за някое $i \ge 2$. Тогава
$$d(v_0, v_i) = i \le d(v_0, u) + d(u, v_i) = p + 1,$$
$$t \le d(v_2, w) \le d(v_2, v_i) + d(v_i, u) + d(u, w) = i - 2 + 1 + q.$$
Събираме горните неравенства и получаваме $t \le p+q = d(v_0, w) \le t-1$, което е противоречие. Следователно разстоянието от всеки връх от пътя между $v_0$ и $w$ до $v_i$, $i \ge 2$ е поне 2.

Ако няма връх от този път, който е съседен на $v_1$, то този път, заедно с пътя от $v_0$ до $v_t$ е търсеният. Ако съществува връх $u$ от този път, за който $d(u, v_1) = 1$, то $t \le d(v_2, w) \le d(v_2, v_1) + d(v_1, u) + d(u, w)$, откъдето $d(v_2, w) \ge t - 2$. Сега лесно следва, че $d(v_0, u) = 1$ и търсеният път е $w \dots u v_1 \dots v_t$.