Graf planarny: Różnice pomiędzy wersjami

Zgodnie z [[Charakterystyka Eulera|wzorem Eulera]], jeżeli <math>|V| \geq 3</math> oraz G jest grafem [[graf spójny|spójnym]] i planarnym, to <math>|V|+|S|-|E|=2</math>, gdzie ''V'' – zbiór wierzchołków, ''E'' – zbiór krawędzi, ''S'' – zbiór ścian dowolnego rysunku płaskiego grafu ''G''.

 

* Jeżeli G jest planarny i posiada <math>k</math> składowych spójnych, to <math>|V|+|S|-|E|=k+1</math>.

* Jeżeli G jest planarny i <math>|E|\geq3</math>, to <math>|E|\leq3\cdot|V|-6</math>.

 

Zgodnie z [[twierdzenie o czterech barwach|twierdzeniem o czterech barwach]], graf planarny daje się zawsze [[kolorowanie grafu|pokolorować]] przy użyciu co najwyżej czterech kolorów.

 

[[Kategoria:Teoria grafów]]