Úgy fogjuk megszámozni az éleket, hogy már két olyan él is tartozzék minden legalább másodfokú csúcshoz, amelyekre egymáshoz relatív prím számokat írtunk; ez nyilván elegendő a feladatbeli állítás bizonyítására.
Legyenek a gráf legalább másodfokú csúcsai $A_1\mathrm{,}{A}_2\mathrm{,}\text{...}\mathrm{,}{A}_n$ (ha ilyen csúcs nincsen, akkor triviális az állítás). Mivel a gráf összefüggő, ezért bármely csúcsból bármely csúcsba vezet út a gráfban. Menjünk el $A_1$-ből $A_2$-be, $A_2$-ből $A_3$-ba, $\text{...}\mathrm{,}{A}_{n-1}$-ből $A_n$-be, végül $A_n$-ből $A_1$-be a gráf egy-egy tetszőleges élsorozatán keresztül! Így egy olyan utazást teszünk a gráfban, amelynek során minden $A_i$-t $\left(i=\mathrm{1,2,}\text{...}\mathrm{,}n\right)$ érintünk és elhagyunk legalább egyszer. Tegyük fel, hogy utazásunk alatt sorra számozzuk az érintett éleket az $\mathrm{1,2,}\text{...}\mathrm{,}l$ számokkal $\left(1\le l\le k\right)$ ‐ azzal a kikötéssel, hogy ha egy élre
a) már írtunk számot, akkor arra új számot már nem írunk.
b) még nem írtunk számot (tehát az utazás során először érintjük), akkor 1-gyel nagyobb számot írunk rá, mint amilyet utoljára használtunk.
Ezek szerint mindig csak az "új'' ‐ addig még nem érintett ‐ élekre kell számot írnunk, és összesen $l$ db élt számoztunk meg a $k$ db él közül.
Az utazásnál még egy dologra kell ügyelnünk:
Ha valamelyik $A_i$ csúcsot $\left(i=\mathrm{2,3,}\text{...}\mathrm{,}n\right)$ először érintjük utazásunk során (ez biztosan bekövetkezik minden $i$-re valamikor), akkor $A_i$-t másik élén keresztül hagyjuk el, mint amilyenen keresztül megközelítettük; ez megtehető, mert $A_i$ legalább másodfokú. Mivel az $A_i$-ből kiinduló élek egyikét sem érintettük azelőtt, ezért a számozási algoritmus szerint ebben a lépésben $A_i$-nek $2$ élére $2$ szomszédos számot kell írnunk.