Rovinnost úplných bipartitních
Úloha číslo: 4112
Ukažte, že graf \(K_{m,n}\) je rovinný právě když \(\min\{m,n\}\le2\).
Řešení
Pokud \(\min\{m,n\}\ge 3\), potom graf obsahuje \(K_{3{,}3}\) jako podgraf a není rovinný podle Kuratowského věty.
Graf \(K_{2,n}\) lze rovinně nakreslit, viz obrázek. Grafy \(K_{1,n}\) a \(K_{0,n}\) jsou jeho podgrafy, tedy jsou také rovinné.
