Megoldás: 11.8
Könnyű ellenpéldát adni. A gráf pontjai legyenek az egész számok, az élek a szomszédos egészeket kötik össze. Ha minden csúcsra önmagát írjuk (a
-1-re a
-1-et, a
0-ra a
0-t, az
1-re az
1-et, a
2-re a
2-t, a
-2-re a
-2-t, stb.), akkor nyilván teljesül a feladat feltétele.