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_0{v}_1{v}_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$.