Feladat: 10.5.
Egy egyszerű poliéder minden csúcsára egy-egy egész számot akarunk írni úgy, hogy ha két csúcs élszomszédos, akkor a rájuk írt számoknak legyen egynél nagyobb közös osztójuk, ha két csúcs nem élszomszédos, akkor ne legyen. (Vagyis két csúcson álló szám pontosan akkor legyen relatív prím, ha a két csúcs nem élszomszéd.)
Megtehető-e ez mindig?
Mi a helyzet, ha fordított eredményt akarok, tehát ha azt akarom, hogy két csúcson álló szám pontosan akkor legyen relatív prím, ha a két csúcs élszomszédos?
Megoldás: 10.5
Vegyük sorra a poliéder éleit, és írjunk mindegyikre egy-egy prímszámot, mindegyikre másikat. Ezután vegyük sorra a poliéder csúcsait és minden csúcsra azt a számot írjuk, amelyet úgy kapunk, hogy összeszorozzuk a belőle induló éleken álló prímeket. Az így kapott számozás megfelelő lesz: két élszomszédos csúcson álló szám közös osztója éppen az összekötő élen álló prímszám lesz, két nem szomszédos csúcsra viszont olyan számok kerültek, amelyeknek nincs közös prímosztójuk, így egynél nagyobb közös osztójuk sem.
Az eljárást bármely egyszerú gráfra ugyanígy elvégezhetjük, tehát például arra a gráfra is, amit úgy kapunk, hogy a poliédert gráfnak tekintjük és vesszük a komplementerét.