Matematické Fórum

Platí. Pro spor předpokládejme, že máme graf G, pro který to neplatí a navíc má nejmenší počet vrcholů ze všech grafů, pro které to neplatí.
Eulerova věta říká V-E+F=2, zřejmě F<=2E/3, po dosazení do Eulerovy věty -E/3<=2-V, E/3>=V-2, 2E>=6V-12. Protože 2E je součet stupňů vrcholů, nemohou mít všechny vrcholy stupeň 6 a výš. Jeden vrchol  má stupeň nejvýše 5.

Kdyby měl stupeň nejvýše 3, nemohl by být vrcholem, který narušuje podmínku nejvýše tří hran -- jeho odstraněním z grafu (i s příslušnými hranami) bychom dostali menší graf, který ji porušuje.

Pokud by měl stupeň 4 a sousedil po řadě s vrcholy a,b,c,d, pak ho můžeme odstranit (i s hranami, které z něj vedou) a přidat hranu z a do c. Vzniklý graf má méně vrcholů, lze jej tedy správně orientovat. Pak z něj můžeme odstranit hranu ac, čímž z a vedou nejvýše dvě hrany. Pak můžeme přidat původně odstraněný vrchol, vést do něj hranu z a a z něj hrany do b,c,d. Dostaneme tak orientovanou podobu grafu, o němž jsme předpokládali, že jej orientovat nelze. Analogickou úvahou vyloučíme i případ, kdy má daný vrchol stupeň 5.