Matematické Fórum

Každý bipartitní graf Km,n s m>2, n>2 obsahuje K3,3, který není rovinný, proto ani Km,n není rovinný pro min{m,n}>2. Bibartittní graf s min{m,n}=2 nakreslit do roviny lze:
                   x
o o o o o o o o o o o o o o o
                  x
Přitom jedna skupina vrcholů je značena symboly o, druhá symboly x a každé o s x je spojeno ranou (v textové podobě neumím nakreslit ;) ), je ale zřejmé, že se žádné dvě hrany nekříží.

Pro min{m,n}=1 je situace ještě jednodušší:
                    x
o o o o o o o o o o o o o o o

Tím je zadané tvrzení dokázáno.