Kössünk össze képzeletben két csúcsot egy ,,piros'' éllel, ha nem szomszédosak, és ,,írjunk rá'' minden ilyen ,,piros'' élre egy prímszámot, mindegyikre különbözőt. A szomszédos csúcsokat összekötő élek mindegyikére írjuk az $1$-es számot. Ezután minden egyes csúcsra számítsuk ki a belőle induló piros és valódi élekre írt számok szorzatát, és írjuk ezt a számot az adott csúcsra.
Két számnak akkor és csak akkor van $1$-nél nagyobb közös osztója, ha van közös prímosztójuk is. Ez most a két csúcshoz kiszámított szorzatra pontosan akkor teljesül, ha a két csúcsot piros él köti össze. Ez pedig éppen akkor fordul elő, ha a két csúcs nem szomszédos a poliéderen. A csúcsokra felírt számok közül így pontosan akkor lesz kettő relatív prím, ha a megfelelő két csúcs szomszédos.
A feladat kérdésére tehát igenlő a válasz.