Stejné skóre

Najděte příklad dvou grafů \(G\) a \(H\) se stejným skóre takových, že:

Varianta
\(G\) je strom a \(H\) není strom.
Odpověď
Např. \((1{,}1,1{,}2,2{,}3)\), viz obrázky.
Varianta
\(G\) je souvislý, \(H\) není souvislý.
Odpověď
Např. \((1{,}1,1{,}2,2{,}3)\), viz obrázky.
Varianta
\(H\) je doplněk \(G\) neboli graf \(H=\overline{G}=\left(V_G,\binom{V_G}{2}\setminus E_G\right)\).
Odpověď
Např. pro grafy \(P_4\) nebo \(C_5\) plati \(G=\overline G\) a proto mají i stejná skóre.
Varianta
\(G\) je rovinný, \(H\) není rovinný.
Odpověď
Např. za \(H\) lze vzít graf \(K_{3{,}3}\), a za \(G\) graf 3-bokého hranolu (vznikne ze dvou \(C_3\) spojením odpovídajících si vrcholů hranami). Oba grafy jsou 3-regulární, \(G\) má jednoduché rovinné nakreslení, nerovinnost \(K_{3{,}3}\) je učebnicový příklad.