grafy planarność Kamil: Jeżeli G jest planarny i |V|≥3 to |E|≤3*|V|−6 Powyższe zdanie jest z twierdzenia Kuratowskiego. Czyli jeśli powyższa nierówność jest niespełniona to graf na pewno nie jest planarny, a jeśli jest spełniona to nie można rozstrzygnąć? Czy źle myślę?

Adamm: jeśli jest niespełniona i |V|≥3

Kamil: Czyli załóżmy takie zadanie Czy graf pełny z 6 wierzchiłkami jest planarny? |V|=6

	6*5
|E|=		=15
	2

15≤18−6 15≤12 sprzeczność Czyli ten graf nie jest planarny

Adamm: tak