I. megoldás. Tekintsünk a gráfban egy tetszőleges $p_0{q}_0$ élt (ami a $p_0$ és a $q_0$ csúcsot köti össze). Egészítsük ki ezt egy tovább már nem bővíthető $U=p_n{p}_{n-1}\text{...}{p}_1{p}_0{q}_0{q}_1\text{...}{q}_{m-1}{q}_m$ úttá. (Ez biztosan megtehető, hiszen a feladat egyik feltétele szerint minden út hossza legfeljebb $k$ lehet.) Ha $p_n$ és a $q_m$ csúcsokat él köti össze, akkor ezzel az éllel a $p_n{q}_m$ út kört határoz meg, ami tartalmazza a kiválasztott élt. ($U$ nem állhat az egyetlen $p_0{q}_0$ élből, mivel akkor mindkét csúcs foka 1 lenne); a továbbiakban feltehetjük, hogy nem ez a helyzet. A fokszámokra adott feltétel miatt $p_n$ és $q_m$ is legalább $k/2$ csúccsal van összekötve; ezek a csúcsok valamennyien $U$-hoz tartoznak, ellenkező esetben ugyanis $U$ legalább az egyik végén bővíthető lenne egy további éllel és annak ($U$-n kívül eső) végpontjával. Mivel feltettük, hogy $p_n$ és $q_m$ nincs egymással összekötve, a $p_n$ és a $q_m$ csúcsok valamennyi szomszédja a $p_{n-1}\mathrm{,}\text{...}\mathrm{,}{p}_1\mathrm{,}{p}_0\mathrm{,}{q}_0\mathrm{,}\text{...}\mathrm{,}{q}_{m-1}$ pontok közül kerül ki; ezek száma $n+m<n+m+1\le k=k/2+k/2$. Ebből következik, hogy a $p_{n-1}\mathrm{,}\text{...}\mathrm{,}{p}_1\mathrm{,}{p}_0\mathrm{,}{q}_0\mathrm{,}\text{...}\mathrm{,}{q}_{m-1}$ pontok között van olyan $y$, amely $p_n$-nel és $q_m$-mel is össze van kötve. Így az $U$ minden éle benne van a $p_n{p}_{n-1}\text{...}y{p}_n$ vagy az $y\text{...}{q}_{m-1}{q}_{m}y$ körök valamelyikében, tehát a $p_0{q}_0$ él is.