Megoldás: 1.31
Minden pont foka három, tehát az élek csak úgy színezhetők jól három színnel, ha minden csúcsból mind a három színű él indul. Számozzuk meg a színeket az 1, 2, 3 számokkal és hagyjuk el a gráfból a 3-színű éleket. Kapunk egy 2-reguláris gráfot, ami körökből áll. Ha több körből állna, akkor az egyik körben az 1-es és 2-es színeket felcserélve és a gráfba visszatéve a 3-as színű éleket kapnánk a gráf éleinek egy olyan jólszínezését, amit nem kaphatunk meg a korábbiból a színek permutációjával. Ez ellentmondana feltételünknek. Tehát az 1-es és 2-es színű élekből álló gráf pontosan egy kör, azaz egy Hamilton-köre a gráfnak.
Megjegyzés. Azt is beláttuk, hogy legalább három Hamilton-köre van a gráfnak.