Editing Planar graph (section)

=== Euler's formula ===
<!--Linked to from [[Crossing number inequality#Proof]]-->
{{main|Euler characteristic#Plane graphs}}
'''Euler's formula''' states that if a finite, [[Connectivity (graph theory)|connected]], planar graph is drawn in the plane without any edge intersections, and {{mvar|v}} is the number of vertices, {{mvar|e}} is the number of edges and {{mvar|f}} is the number of faces (regions bounded by edges, including the outer, infinitely large region), then

:<math>v-e+f=2.</math>

As an illustration, in the [[butterfly graph]] given above, {{math|1=''v'' = 5}}, {{math|1=''e'' = 6}} and {{math|1=''f'' = 3}}. 
In general, if the property holds for all planar graphs of {{mvar|f}} faces, any change to the graph that creates an additional face while keeping the graph planar would keep {{math|''v'' − ''e'' + ''f''}} an invariant. Since the property holds for all graphs with {{math|1=''f'' = 2}}, by [[mathematical induction]] it holds for all cases. Euler's formula can also be proved as follows: if the graph isn't a [[tree (graph theory)|tree]], then remove an edge which completes a [[cycle (graph theory)|cycle]]. This lowers both {{mvar|e}} and {{mvar|f}} by one, leaving {{math|''v'' − ''e'' + ''f''}} constant. Repeat until the remaining graph is a tree; trees have {{math|1=''v'' = ''e'' + 1}} and {{math|1=''f'' = 1}}, yielding {{math|1=''v'' − ''e'' + ''f'' = 2}}, i. e., the [[Euler characteristic]] is 2.

In a finite, [[Connectivity (graph theory)|connected]], ''[[simple graph|simple]]'', planar graph, any face (except possibly the outer one) is bounded by at least three edges and every edge touches at most two faces, so {{math|1=3''f'' ≤ 2''e''}}; using Euler's formula, one can then show that these graphs are ''sparse'' in the sense that if {{math|''v'' ≥ 3}}:

:<math>e\leq 3v-6.</math>

[[File:Dodecahedron schlegel.svg|thumb|A [[Schlegel diagram]] of a regular [[dodecahedron]], forming a planar graph from a convex polyhedron.]]

Euler's formula is also valid for [[convex polyhedron|convex polyhedra]]. This is no coincidence: every convex polyhedron can be turned into a connected, simple, planar graph by using the [[Schlegel diagram]] of the polyhedron, a [[perspective projection]] of the polyhedron onto a plane with the center of perspective chosen near the center of one of the polyhedron's faces. Not every planar graph corresponds to a convex polyhedron in this way: the trees do not, for example. [[Steinitz's theorem]] says that the [[polyhedral graph]]s formed from convex polyhedra are precisely the finite [[Connectivity (graph theory)|3-connected]] simple planar graphs. More generally, Euler's formula applies to any polyhedron whose faces are [[simple polygon]]s that form a surface [[homeomorphism|topologically equivalent]] to a sphere, regardless of its convexity.