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é.

    bipartitní graf
Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha na dokazování, ověřování
En translation
	Zaslat komentář k úloze