page_title: Planar graph
section_title: Euler's formula
hierarchical_section_title: Planar graph / Other planarity criteria / Euler's formula
caption_attribution_description: English: Dodecahedron Schlegel diagram
context_page_description: In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.
  Every graph that can be drawn on a plane can be drawn on the sphere as well, and vice versa, by means of stereographic projection.
  Plane graphs can be encoded by combinatorial maps.
  The equivalence class of topologically equivalent drawings on the sphere is called a planar map. Although a plane graph has an external or unbounded face, none of the faces of a planar map have a particular status.
  Planar graphs generalize to graphs drawable on a surface of a given genus. In this terminology, planar graphs have graph genus 0, since the plane are surfaces of genus 0.
context_section_description: Euler's formula states that if a finite, connected, planar graph is drawn in the plane without any edge intersections, and v is the number of vertices, e is the number of edges and  f is the number of faces (regions bounded by edges, including the outer, infinitely large region), then
  As an illustration, in the butterfly graph given above, v = 5, e = 6 and f = 3.  
  In general, if the property holds for all planar graphs of f faces, any change to the graph that creates an additional face while keeping the graph planar would keep v − e + f an invariant. Since the property holds for all graphs with 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, then remove an edge which completes a cycle. This lowers both e and f by one, leaving v − e + f constant. Repeat until the remaining graph is a tree; trees have v =  e + 1 and f = 1, yielding v − e + f = 2, i. e., the Euler characteristic is 2.
  In a finite, connected, 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; using Euler's formula, one can then show that these graphs are sparse in the sense that if v ≥ 3:
  Euler's formula is also valid for 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 graphs formed from convex polyhedra are precisely the finite 3-connected simple planar graphs. More generally, Euler's formula applies to any polyhedron whose faces are simple polygons that form a surface topologically equivalent to a sphere, regardless of its convexity.
caption: A Schlegel diagram of a regular dodecahedron, forming a planar graph from a convex polyhedron.
exif: {}