Egy 3x3-as táblázat mezőibe írjunk be az 1,2,3,4,5,6,7,8,9,10 számok közül pontosan kilencet úgy, hogy bármelyik két oldalban szomszédos négyzeten lévő számok összege prímszám legyen. Mi lenne a megoldás?

A gráfos ötletből kiindulva az se nehéz, hogy megtaláljuk az összes megoldást. Ugye középre csak olyan szám kerülhet, aminek a fokszáma 4, ilyenből 6 darab van. Mind a 6 esetben van pontosan 5 – 4 = 1 vele ellentétes paritású szám, amivel nincs összekötve, nyilván ezt a számot nem fogjuk tudni beírni a 10 közül.

Ha töröljük a középső és a kimaradó számot a gráfból, akkor lesz egy 8-pontú gráfunk, amiben MIND a 6 esetben pontosan 1 a középsővel ellentétes paritásúnak lesz 2 a fokszáma, jelöljük őt H-val. Mivel a táblázatot forgathatjuk, ezért vegyük úgy, hogy H felül van. H két szomszédja közül pontosan az egyiknek 2 a fokszáma (megint csak mind a 6 esetben), írjuk ezt tőle balra (mivel a két szélső oszlop felcserélhető, ezért mindegy, hogy hova írjuk a két hely közül). Így az is mind a 6 esetben egyértelmű, hogy mi kerül a jobb felső sarokba (ugye a H másik szomszédja), meg az is, hogy mi kerül a bal középső mezőbe (ugye a H-tól balra levő szám másik szomszédja). Így mind a 6 esetben két-két szám marad a bal alsó és a középső alsó mezőbe, ami azt jelenti, hogy csak 4-4 lehetőséget kell kipróbálnunk mind a 6 esetben.

(Hogy ez tényleg így van, az egyszerűen csak abból látszik, hogy lerajzoljuk mind a 6 darab 8-csúcsú gráfot. Szóval nem tudok rá szép indoklást, hogy így kell legyen, csak fát vágtam.)

A 6-ból 2 esetben (a középső elem 1 vagy 2) lesz jó mind a 4 lehetőség, a maradék 4 esetben (a középső elem 3, 4, 9 vagy 10) pedig 2-2 alapmegoldás lesz. Ez 16 alapmegoldás, ezekre alkalmazva a táblázat szimmetriáit kapjuk az összes megoldást.