the outer, infinitely large region), then As an illustration, in the butterfly graph given above, , and . In general, if the property holds for all planar graphs of faces, any change to the graph that creates an additional face while keeping the graph planar would keep an invariant. Since the property holds for all graphs with , 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 and by one, leaving constant. Repeat until the remaining graph is a tree; trees have and , yielding , 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 : 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. Average degree Connected planar graphs with more than one edge obey the inequality , because each face has at least three face-edge incidences and each edge contributes exactly two incidences. It follows via algebraic transformations of this inequality with Euler's formula that for finite planar graphs the average degree is strictly less than 6. Graphs with higher average degree cannot be planar. Coin graphs We say that two circles drawn in a plane kiss (or osculate) whenever they intersect in exactly one point. A "coin graph" is a graph formed by a set of circles, no two of which have overlapping interiors, by making a vertex for each circle and an edge for each pair of circles