Fogalmazzuk át a feladatot a gráfelmélet nyelvére. Rendeljünk a település minden lakójához egy pontot, és az ismerősökhöz tartozó pontpárokat kössük össze éllel. Ekkor a feladat így fogalmazható át: Adott egy 1000 pontú gráf, amelyben bármely két pont között van út, vagyis egymáshoz csatlakozó élek sorozata, amelyek közül az első az egyik pontból indul, az utolsó pedig a másikba érkezik. Ez abból következik, hogy előbb-utóbb mindenki megtud minden hírt; tehát a gráf összefüggő. Bizonyítandó, hogy kiválasztható 90 csúcs úgy, hogy a gráf bármelyik $P$ pontjához létezik ezek között olyan, amelyből vezet $P$-be legfeljebb 10 hosszúságú út.
Ha a gráfban van kör, azaz olyan út, amelynek kezdő és végpontja megegyezik, de minden él legfeljebb egyszer fordul benne elő, akkor annak bármelyik élét elhagyva, a gráf továbbra is összefüggő marad, éleinek száma pedig csökken. Ezt az eljárást folytatva, mivel összesen véges sok él van, előbb-utóbb olyan összefüggő gráfot kapunk, amelyben nincs kör. Az ilyen gráfokat nevezik fának. Ha az állítás erre igaz, akkor az eredetire is, hiszen amit el lehetett érni 10 hosszúságú úttal, azt az új élek behúzása után is el lehet érni. Feltehetjük tehát, hogy a gráfunk fa.
Vizsgáljuk a gráf egyik leghosszabb olyan útját, amelyben minden él legfeljebb egyszer szerepel (ezeket nevezik egyszerű útnak). (Az élek, s így az egyszerű utak száma is véges, azaz van közöttük leghosszabb, esetleg több is.) Jelölje az egyik leghosszabb egyszerű utat $X$‐$A_1$‐$\text{...}$‐$A_k$‐$Y$.
1. eset: ha $k\le 19$. Ekkor $A_{10}$ máris megfelel, vagyis belőle mindenhová eljuthatunk legfeljebb 10 hosszúságú úton.
Bizonyítás. Tegyük fel, hogy valamely $Z$ pontra létezik $u_Z=A_{10}$‐$\text{...}$‐$Z$ egyszerű út, amely hosszabb, mint 10, azaz hosszabb $X$‐$A_1$‐$\text{...}$‐$A_{10}$-nél és $A_{10}$‐$A_{11}$‐$\text{...}$‐$Y$-nál is. Ez az $u_Z$ út nem metszhet bele a két utóbbi út mindegyikébe egyszerre. Tegyük fel ugyanis, hogy $A_i$ és $A_j$ is rajta van, ahol $i\le 9$, $j\ge 11$ és $i$ a legnagyobb, $j$ a legkisebb ilyen index. Ekkor őket $u_Z$ is, valamint az $A_i$‐$A_{i+1}$‐$\text{...}$‐$A_{10}$‐$A_j$ út is összeköti, és ezeknek nincs további közös pontjuk, hiszen az $u_Z$ út $A_i$ és $A_j$ között már nem metszi az $X$‐$A_1$‐$\text{...}$‐$Y$ utat, az indexek választása miatt. Vagyis ezt a kettőt egymás után fűzve kört kapnánk, ami ellentmondás. Amennyiben $u_Z$ az $X$‐$A_1$‐$\text{...}$‐$A_{10}$ szakaszba nem metsz bele, akkor az $X$‐$\text{...}$‐$A_{10}$‐$\text{...}$‐$Z$ út hosszabb az $X$‐$A_1$‐$\text{...}$‐$Y$-nál, holott az leghosszabb volt; és hasonlóan ellentmodásra vezet az, ha $u_Z$ az $A_{10}$‐$\text{...}$‐$Y$ szakaszba nem metsz bele. Ezzel az 1. esetet beláttuk.
2. eset: ha $k\ge 20$. Ekkor válasszuk ki $A_{10}$-et, és hagyjuk el mindazokat a csúcsokat, amelyek belőle nem (csak) $A_{11}$-en keresztül érhetők el (egyszerű úttal). Ezekről később lesz szó. Mivel $X$, $A_1$, $\text{...}$, $A_{10}$ biztos ilyen, így legalább 11 csúcsot elhagytunk. Ekkor egyrészt a megmaradt gráf fa, másrészt az elhagyott pontok $A_{10}$-ből legfeljebb 10 hosszúságú úton elérhetők.
Bizonyítás. A körmentesség nyilvánvaló. Legyen $U$, $V$ két megmaradt csúcs, ekkor az őket az eredeti gráfban $A_{10}$-zel összekötő út $A_{10}$‐$A_{11}$‐$B_1$‐$\text{...}$‐$B_s$‐$U$, illetve $A_{10}$‐$A_{11}$‐$C_1$‐$\text{...}$‐$C_r$‐$V$ alakú. Ezen két út pontjai közül egyet sem hagyhatunk el, hiszen ha lenne valamelyik $B_i$-be vagy $C_j$-be $A_{11}$-et elkerülő út $A_{10}$-ből, akkor véve a legkisebb indexű ilyet, abba két különböző (közös él nélküli) út vezetne $A_{10}$-ből, vagyis ismét kört kapnánk, ami lehetetlen. Tehát az $U$‐$B_s$‐$\text{...}$‐$B_1$‐$A_{11}$‐$C_1$‐$\text{...}$‐$C_r$‐$V$ út megmaradt.
Legyen $W$ egy olyan pont, amely $A_{10}$-ből elérhető egy nem $A_{11}$-en át vezető $W$‐$\text{...}$‐$A_{10}$ úton (is). Ekkor az előzőhöz hasonlóan látszik, hogy $W$‐$\text{...}$‐$A_{10}$-nek az $A_{10}$-en kívül nincs közös pontja az $A_{10}$‐$A_{11}$‐$\text{...}$‐$Y$ úttal (ugyanis kört kapnánk), azaz $W$‐$\text{...}$‐$A_{10}$‐$A_{11}$‐$\text{...}$‐$Y$ hossza nem lehet nagyobb $X$‐$A_1$‐$\text{...}$‐$Y$-énál, ami azt jelenti, hogy a $W$‐$\text{...}$‐$A_{10}$ út hossza legfeljebb 10. Ezzel állításunk mindkét részét igazoltuk.
Innen a bizonyítás már könnyen befejezhető: A megmaradt gráfra ismét végrehajtjuk az eljárást, egymás után legfeljebb 89-szer. Ha bármikor az 1. eset lép föl, készen vagyunk. Ha végig a 2. esettel van dolgunk, akkor a 89. lépés után kiválasztottunk már 89 pontot, és elhagytunk legalább $89\cdot 11$-et, azaz legfeljebb $1000-89\cdot 11=21$ maradt. Erre viszont mindenképpen az 1. eset alkalmazható, ami megadja a 90. pontot.
Ugyanezzel a módszerrel belátható a következő általánosítás is: egy $\left(n+1\right)\left(k+1\right)-1$ csúcsú összefüggő gráfban kiválasztható $n$ csúcs úgy, hogy azokból az összes többi elérhető legyen legfeljebb $k$ hosszúságú úton.