Egy 60 csúcsú összefüggő gráf minden pontjának foka 4. Mutassuk meg, hogy élei kiszínezhetők pirossal és kékkel úgy, hogy minden csúcsba két piros és két kék él fusson! És ha nem összefüggő?

Ha minden csúcs fokszáma 4, akkor van benne zárt Euler-körvonal. A színezést a következőképpen tudjuk véghezvinni; elindulunk valamelyik csúcsból egy másikba, a használt él pirossal színezzük, átmegyünk egy másikba, azt kékre. Aztán pirosra, kékre, és ezt addig csináljuk, amíg nem jutunk haza. Mivel minden csúcsba kétszer lépünk és kétszer lépünk ki, ezért ezzel elérjük, hogy csúcsonként legyen 2-2 azonos színű él.

Ha a gráf nem összefüggő, akkor sincs nagy probléma, mivel a komponensekben mind-mind lesz zárt Euler-vonal, tehát a komponensekre is el lehet játszani a fenti színezési metódust.