Matematické Fórum

Zdravím,
reším jeden problém zadání je: Dokažte, že K3,3 neni rovinny graf. (napověda: nakresleni jisteho podgrafu můžete vždy převest na n-uhelnik). Už vím že graf K3,3 není rovinný problém mi ale dělá ověření. Vím že pro graf který má alespoň 3 vrcholy platí vzorec |E| <= 3|V| - 6 když do vzorce dosadím 9 <= 3 * 6 - 6 tedy dostanu že 9 <= 12 (tento vzorec máme v přádnáškách)  Dále jsem našel vzorec |E| ≤ 3|V| −6 a s ≤ 2v −4 kde s je počet stěn, když dosadím do tohoto vzorce tak dostanu ze 9 <= 3*6 - 6 a 2<=2*6 - 4 tedy 9<= 12 a 2<=8 tedy zase obě nerovnice vyhovují. Což by neměli pokud není tento graf rovinný. Ještě jsem našel vzorec pro graf který neobsahuje trojúhelník |E| ≤ 2|V| − 4 a s ≤ |V| − 2 kdyz sem dosadím zjistim ze 9<= 2*6 - 4 a 2 <= 6 - 2 => 9<=8 a 2<=4 zde je videt ze první nerovnice neprošla tedy by měl být nerovinný. Bohužel se tím dostávám do sporu vuči tem prvním 2. vzorcům.
Najde se zde někdo kdo mi poradí jak dokázet (kromě nakreslení) že graf je nerovinný.
Předem děkuji za každou snahu.