Počet vrcholů rovinného grafu
Úloha číslo: 3740
Má-li rovinný graf celkem \(12\) stěn, každá z nich je pětiúhelník a každý vrchol má stupeň \(3\), kolik má vrcholů?
Řešení
Dvěma způsoby určíme počet hran:
\(|E_G|=12{\cdot}5\cdot\frac12\), protože \(G\) má 12 stěn, každá stěna má 5 hran a každá hrana odděluje dvě stěny.
\(|E_G|=|V_G|\cdot3\cdot\frac12\), protože každý vrchol má stupeň 3 a každá hrana má dva konce.
Odtud \(|V_G|=\frac{12{\cdot} 5}3=20\).
Odpověď
Graf má \(20\) vrcholů, je to graf dvanáctistěnu.