A Vizing-tétel a gráfok élkromatikus számára ad alsó és felső becslést:
\( \Delta(G) \leq \chi_e(G) \leq \Delta(G) + 1 \)
Vagyis a $G$ egyszerű gráfok két osztályba sorolhatók:
Első osztály: $\chi_e(G) = \Delta(G)$
Második osztály: $\chi_e(G) = \Delta(G)+1 $
A Vizing-tétel a gráfok élkromatikus számára ad alsó és felső becslést.
1.
a) Mennyi a Petersen gráf élkromatikus száma?
b) Egy 1001 csúcsú gráf úgy keletkezik, hogy egy 1000 csúcsot tartalmazó kör minden pontját összekötjük az 1001-edik csúccsal. Mekkora ennek a gráfnak az élkromatikus száma?
