Riešenie: Z definície eulerovského grafu vieme, že graf sa nazýva eulerovský, ak všetky jeho stupne sú párneho stupňa. Skontrolujeme teda stupne oboch grafov. Ako je to znázornené na predchádzajúcom obrázku, v grafe \(G_1\) máme aj vrcholy stupňa \(3\), teda nepárne. To znamená, že graf \(G_1\) nie je eulerovský. Naopak, graf \(G_2\) má vrcholy len stupňov \(2\) a \(4\), teda je eulerovský.

Riešenie: Graf \(G_1\) je eulerovský, pretože všetky jeho vrcholy majú párny stupeň. Keďže je eulerovský, dá sa pokryť jedným uzavretým ťahom. Samotné pokrytie (nakreslenie diagramu jedným ťahom) uzavretým ťahom nechávame na čitateľa.
Graf \(G_2\) nie je eulerovský, keďže obsahuje dva vrcholy nepárneho stupňa. Nedá sa ani pokryť uzavretým ťahom, pretože eulerovskosť je nutnou podmienkou pokrytia grafu jedným uzavretým ťahom. No tento graf, keďže má práve dva vrcholy nepárneho stupňa, dá sa pokryť otvoreným ťahom. Musíme však začať v jednom z týchto vrcholov a skončiť v druhom. To nech čitateľ tiež vyskúša sám.

Riešenie: Vyriešiť problém okružnej cesty (známy tiež pod názvom problém poštára) znamená zistiť, ako prejsť všetkými hranami a vrátiť sa do východzieho bodu tak, aby ohodnotenie výsledného sledu bolo čo najmenšie.
V eulerovskom grafe to nie je žiaden problém, stačí pokryť graf uzavretým ťahom. Keďže daný graf je eulerovský, ohodnotenie výsledného sledu bude súčet ohodnotení všetkých hrán, a to \(56\).

Riešenie: Tento graf nie je eulerovský, takže sa nedá pokryť uzavretým ťahom. Vrcholy \(C\) a \(E\) majú nepárny stupeň. Ak teda chceme začať okružnú cestu v nejakom vrchole, prejsť všetky hrany a vrátiť sa späť, tak musíme niektoré hrany prejsť dvakrát. Konktétne cestu z vrcholu \(C\) do vrcholu \(E\). Pomocou napríklad Dijkstrovho algoritmu (viď cvičenie 4), nájdeme najkratšiu cestu z \(C\) do \(E\). Je to cesta \(C-F-H-E\) a jej dĺžka je \(10\). K súčtu ohodnotení všetkých hrán daného grafu: \(89\) pripočítame toto číslo a dostaneme \(99\), čo je dĺžka hľadanej minimálnej okružnej cesty.

Riešenie: Graf nie je eulerovský, má \(4\) vrcholy nepárneho stupňa :\(C, D, E, F\). Ak teda chceme začať okružnú cestu v tomto grafe, tak musíme niektoré hrany prejsť dvakrát. Otázkou je, ako máme poprepájať nepárne vrcholy tak, aby súčet ohodnotení vybraných ciest bol najmenší.
Všetkých dvojíc ciest je \(3\), sú to: \(CD,EF\), \(CE,DF\) a \(CF,DE\). Pomocou napríklad Dijkstrovho algoritmu (viď cvičenie 4), nájdeme najkratšie cesty z pre každú dvojicu vrcholov nepárneho stupňa:

\(CD\)	\(CE\)	\(CF\)	\(DE\)	\(DF\)	\(EF\)
\(3\)	\(4\)	\(6\)	\(4\)	\(7\)	\(4\)

Naše tri možnosti dvojíc ciest budú mať nasledujúce hodnoty:

\(CD, EF\)	\(CE, DF\)	\(CF, DE\)
\(7\)	\(11\)	\(10\)

Pridanie hrán na minimálnych cestách medzi dvojicami vrcholov \(CD, EF\) je najvýhodnejšie. Súčet všetkých ohodnotení hrán v grafe je \(40\) a minimálna okružná cesta má hodnotu \(40+7=47\).

Riešenie: Ani tento graf nie je eulerovský, má až \(6\) vrcholov nepárneho stupňa :\(B, C, F, G, L, P\). Podobne ako v dvoch predchádzajúcich príkladoch pre nájdenie minimálnej okružnej cesty musíme niektoré hrany prejsť dvakrát. Dvakrát budeme musieť prejsť hrany troch dvojíc týchto vrcholov, pre ktoré je súčet ohodnotení hrán minimálnych ciest minimálny.
Zostrojíme teda všetkých \(15\) možných trojíc zostavených z dvojíc vrcholov nepárneho stupňa a priradíme im minimálne dĺžky určené napríklad Dijkstrovým algoritmom.

\(BC, FG, LP\)	\(BC, FL, GP\)	\(BC, FP, GL\)	\(BF, CG, LP\)	\(BF, CL, GP\)
\(5, 9, 9\)	\(5, 11, 4\)	\(5, 11, 13\)	\(15, 16, 9\)	\(15, 6, 4\)
\(BF, CP, GL\)	\(BG, CF, LP\)	\(BG, CL, FP\)	\(BG, CP, FL\)	\(BL, CF, GP\)
\(15, 12, 13\)	\(11, 11, 9\)	\(11, 6, 11\)	\(11, 12, 11\)	\(11, 11, 4\)
\(BL, CG, FP\)	\(BL, CP, FG\)	\(BP, CF, GL\)	\(BP, CG, FL\)	\(BP, CL, FG\)
\(11, 16, 11\)	\(11, 12, 9\)	\(7, 11, 13\)	\(7, 16, 11\)	\(7, 6, 9\)

Najmenší súčet dáva trojica \(BC, FL, GP\) a to \(20\). Súčet všetkých ohodnotení hrán v grafe je \(122\) a minimálna okružná cesta má hodnotu \(122+20=142\).

Riešenie: Graf \(G_1\) obsahuje kompletný graf \(K_4\) ako podgraf. Pre vrcholové farbenie kompletných grafov platí, že na regulárne zafarbenie grafu \(K_n\) je nutných \(n\) farieb. Na zafarbenie grafu \(G_1\) ich teda potrebujeme aspoň \(4\). Ako vidieť na nasledujúcom obrázku, \(4\) farby stačia na zafarbenie \(G_1\) a teda chromatické číslo \(\chi (G_1) = 4\). Graf \(G_2\) obsahuje len kružnice párnej dĺžky, pokúsime sa ho zafarbiť dvomi farbami. Ako je znázornené v nasledujúcom diagrame, \(2\) farby postačujú a \(\chi (G_2) = 2\). V grafe \(G_3\) sú kružnice nepárnej dĺžky, je teda jasné, že na zafarbenie potrebujeme aspoň \(3\) farby. Pokúsime sa to tromi farbami zafarbiť. Tak ako je to v nasledujúcom diagrame znázornené, \(3\) farby stačia a \(\chi (G_3) = 3\).

Riešenie: Chromatický index grafu \(\bar{\chi} (G)\) je minimálny počet farieb potrebných na regulárne hranové zafarbenie grafu \(G\). Pre chromatický index platí nasledujúca nerovnosť: \(\Delta(G)\leq \bar{\chi}(G)\leq \Delta(G)+1\), kde \(\Delta(G)\) je maximálny stupeň vrchola v grafe. Odtiaľ je zrejme, že chromatický index grafu \(G_1\) je \(4\) alebo \(5\), chromatický index grafu \(G_2\) je \(5\) alebo \(6\) a chromatický index grafu \(G_3\) je \(3\) alebo \(4\). Skúsime tieto grafy hranovo regulárne zafarbiť menším z možných čísel, ak sa to dá. Ako vidieť na predchádzajúcom diagrame, v grafoch \(G_1, G_2\) je potrebný počet farieb rovný najvyššiemu stupňu, no v grafe \(G_3\) potrebujeme jednu farbu navyše. A teda:
\(\bar{\chi} (G_1)=4\),
\(\bar{\chi} (G_2)=5\),
\(\bar{\chi} (G_3)=4\).