aljabrak

Jul 30, 2022

Euler's Characteristic Formula

Many theorems in mathematics are important enough that they have been proved repeatedly in surprisingly many different ways. Like Fermat’s last theorem, Basel problem, Fundamental theorem of arithmetic, etc.

Euler’s characteristic formula is one of the important results of Graph Theory. Not to confuse it with

Euler was a busy man. And as used in graph theory, the term graph does not refer to graphs of functions.

Graph theory, more than any other branch of mathematics, feeds on problems. It is no coincidence that Paul Erdos, the greatest problem-poser the world has ever seen, devoted much of his time to graph theory.

"Another roof, another proof." Paul Erdos.

The basic concepts of graph theory are extraordinarily simple and can be used to express problems from many different subjects. It is used in Computer Science, Chemistry, Biology, etc. Facebook uses graphs to store enormous information about users and friendships.

What is Graph?

A graph is an ordered pair of disjoint sets $$(V, E)$$, where every element of set $$V$$ is called vertex and every element of set $$E$$ is called edge. An edge $${x, y}$$ is said to join the vertices $$x$$ and $$y$$ and is denoted by $$xy$$. Thus $$xy$$ and $$yx$$ mean exactly the same edge; the vertices $$x$$ and $$y$$ are the end-vertices of this edge.

If the edges of the graph don't intersect with each other then it is a Planar Graph. Putting it a little more rigorously, it is possible to represent it by a drawing in the plane in which the vertices correspond to distinct points and the edges to the simple Jordan curves connecting the points of its end vertices. In this drawing, every two curves are either disjoint or meet only at a common endpoint. The above representation of a graph is said to be a plane graph.

Leonhard Euler was originally working with a convex polyhedron. When he realized the importance of the edges of a polyhedron. He wrote about it twice in 1750, and in 1752 published the result, with a faulty proof by induction for triangulated polyhedra based on removing a vertex and re-triangulating the hole formed by its removal.

If we draw the graph of a convex polyhedron in the plane, then the edges and, vertices of the polyhedron clearly correspond to the lines and, dots of the planar graph. If we omit the vertices and edges of a planar graph remainder falls into connected components called faces or regions. The boundary of the face is the set of edges in its closure.

Projection of dodecahedron onto a plane.

This leads us to an important contribution of Leonhard Euler to Graph Theory, namely Euler's Characteristic Formula or Euler's polyhedron theorem.

Planar graphs of cube, octahedron and dodecahedron respectively.

Euler's Characteristic Formula.

If a connected planar graph G has V vertices, E edges, and F faces, then:

$$V - E + F = 2.$$

Euler's characteristic formula says that the number of dots (vertices) minus the number of lines (edges) plus the number of regions (faces), including the outer region always equals two. The Euler characteristic can be defined for connected planar graphs by the same formula as for polyhedral surfaces, where F is the number of faces in the graph, including the exterior face.

Here are Twenty-one proofs of Euler's formula by The Geometry Junkyard.