Graf planarny: Różnice pomiędzy wersjami

'''Graf planarny''' – [[graf (matematyka)|graf]], który można narysować na płaszczyźnie (i każdej powierzchni [[genus]]u 0) tak, by krzywe obrazujące krawędzie grafu nie przecinały się ze sobą. Odwzorowanie grafu planarnego na płaszczyznę o tej własności nazywane jest jego rysunkiem płaskim. Graf planarny o zbiorze wierzchołków i krawędzi zdefiniowanym poprzez rysunek płaski nazywany jest [[graf płaski|grafem płaskim]]<ref>{{Cytuj książkę | nazwisko = Diestel | imię = Reinhard | tytuł = Graph Theory | url=http://diestel-graph-theory.com/index.html | miejsce = Nowy Jork | rok = 2000 | strony = 67, 80| isbn= 0-387-95014-1}}</ref>.

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

* 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>|V|\geq3geqslant3,</math>, to <math>|E|\leq3leqslant3\cdot|V|-6.</math>.