Riešenie: Most v grafe je definovaný "hrana daného grafu, ktorá nepatrí žiadnej kružnici". Z toho vyplýva, že most je takou hranou, ktorej odstránením dostaneme podgraf obsahujúci viac komponentov, ako pôvodný graf. Daný graf je súvislý, teda odstránením mosta, by sme mali dostať nesúvislý podgraf. Tomu vyhovujú dve hrany, ktoré sú mostami: \(\{a,b\}\) a \(\{f,j\}\).

Riešenie: Artikuláciou v grafe rozumieme "vrchol daného grafu, ktoreho odstránením dostaneme podgraf obsahujúci viac komponentov, ako pôvodný graf". Daný graf je súvislý, teda odstránením artikulácie, by sme mali dostať nesúvislý podgraf. Artikuláciami v uvedenom grafe sú vrcholy: \(a,b,c,f\).

Riešenie: Riešením môžu byť rôzne grafy, každý si môže zvoliť rôzny. Tu uvedieme len nejaké príklady:

1. Nasledujúci graf obsahuje jednu artikuláciu, žiaden most.
   
2. Vrcholy incidujúce s mostom sú zároveň artikuláciami, výnimkou je visiaci vrchol. Preto jediným možným súvislým grafom obsahujúcim most a nie artikulácie je cesta na dvoch vrcholoch.
3. Tento graf obsahuje dva mosty a dve artikulácie.
   

Riešenie: Pravidelný súvislý graf 3. stupňa znamená, že všetky vrcholy budú mať stupeň 3 a má ich byť 16. Bez mosta to môže byť napríklad uvedený graf \(G_1\), s jedným mostom napríklad graf \(G_2\). Odporúčame však čitateľovi zostrojiť si nejaký vlastný graf s danými vlastnosťami.

Riešenie: V grafe \(G_1\) neplatí žiadna z nám známych postačujúcich podmienok pre hamiltonovskosť. To však neznamená, že graf nemôže byť hamiltonovský. Pokúsime sa tomto grafe regulárne zafarbiť všetky vrcholy čo najmenším počtom farieb. Daný graf sa nám podarilo zafarbiť dvoma farbami. Počet vrcholov označených 1 je 6, počet vrcholov označených 2 je 5. Keďže susedné vrcholy majú vždy iné číslo, ak by existovala hamiltonovská kružnica, museli by sa v nej dvojky a jednotky striedať. No pretože jednotiek a dvoják nie je rovnaký počet, takáto kružnica nemôže existovať a graf nie je hamiltonovský. Jednou z možných postačujúcich podmienok na hamiltonovskosť grafov je, aby všetky vrcholy v grafe s n vrcholmi mali stupeň aspoň \(n/2\). Graf \(G_2\) túto podmienku spĺňa. Má 8 vrcholov a každý vrchol má stupeň 4. Teda graf je hamiltonovský a existuje v ňom napríklad takáto hamiltonovská (obsahujúca všetky vrcholy) kružnica: Platí tiež veta, že ak v súvislom grafe vieme odstrániť \(m\) vrcholov tak, že vznikne aspoň \(m+1\) komponentov, tak graf nie je hamiltonovský. V grafe \(G_3\) vieme odstrániť dva vrcholy tak, že nám vzniknú tri komponenty, preto tento graf nie je hamiltonovský.

Riešenie: Zostrojíme rozhodovací strom z vrcholu \(F\) (keďže je výhodné začať z vrcholu s najnižším stupňom). Postupovať budeme tak, že z vrcholu naznačíme hrany do všetkých susedných vrcholov, ak už v ceste nie sú uvedené. Potom z každého ďalšieho naznačíme každého jeho suseda,... Ako je vidieť v strome, existujú tu len dve hamiltonovské kružnice:

• \(k_1\): \(FABCDEF\)
• \(k_2\): \(FADCBEF\)

Dĺžku kružnice \(k_1\) vypočítame ako súčet ohodnotení jej hrán, teda \(18+6+2+10+12+2=50\). Podobne dĺžka kružnice \(k_2\) je \(18+4+10+2+8+2=44\). Cestou pre obchodného cestujúceho je teda kružnica \(k_2\) (keďže je kratšia) a jej dĺžka je \(44\).

Riešenie: Vieme, že graf je súvislý a planárny, teda pre počet hrán \(|H|\), počet vrcholov \(|V|\) a počet oblastí \(r\) platí vzťah: \(|V|-|H|+2=r\). Ďalej vieme, že odstránením 5 hrán dostaneme kostru, teda je to minimálny počet hrán, ktoré musíme odstrániť, aby sme zrušili všetky kružnice v grafe, čo znamená, že 5 je vlastne cyklomatické číslo grafu \(\mu =5\). Z vlastností planárnych grafov tiež vieme, že platí \(r=\mu +1\), teda \(r = 5 + 1 = 6\). Dosadením dostaneme: \(|H|-11+2=6\) a teda počet hrán daného grafu \(|H|=15\).

Riešenie: Overiť, resp. dokázať planárnosť grafu znamená nájsť nejaký jeho diagram bez pretínajúcich sa hrán. Ako možno vidieť na nasledujúcom obrázku, tento graf je planárny, pretože jeho diagram sa dá prekresliť tak, aby sa hrany nepretínali.

Riešenie: Keď sa pozrieme na diagram grafu, vidíme, že obsahuje len jeden priesečník hrán, no odstrániť ho nejde. Tento graf nie je planárny a dokážeme to použitím Kuratowského vety, ktorá hovorí o tom, že graf je planárny práve vtedy, ak neobsahuje podgraf homeomorfný s \(K_5\) ani s \(K_{3,3}\). Vieme z grafu vybrať podgraf, ktorý je homeomorfný s \(K_5\). Nahradením hrán \({a,e}\) a \({a,b}\) hranou \({e,b}\) a postupne nahradením hrán \({b,c}; {c,d}; {d,h}\) hranou \({b,h}\) dostaneme graf izomorfný s \(K_5\), teda z grafu sa dá vybrať podgraf homeomorfný s \(K_5\), čo znamená, že graf nie je planárny.

Riešenie: Podobne ako v predchádzajúcom príklade sa pokúsime z grafu vybrať podgraf homeomorfný s \(K_{3,3}\) alebo \(K_5\). Podgraf \(G´\) na nasledujúcom obrázku je podgrafom pôvodného grafu. Odstránením vrcholov stupňa \(2\) a ich nahradením hranami dostaneme graf \(K_{3,3}\). To je dôkazom toho, že daný graf nie je planárny.