Euler’s formula,planar graphs

In this post I will describe certain applications of Euler’s formula for planar graphs.

Euler’s formula states that $V-E+F=2$ for a planar graph. Thus $V-E+F$ acts a invariant for planar graph. Infact, more generally euler’s characteristic is a topological invariant of certain objects like simplical complexes. So a direct application euler’s formula shows that graphs $K_5$ and $K_{3,3}$ are non-planar. For example $K_5$ if there exist a planar topological realisation then we would have $V=5, E=10$ so that $F$ should be 7. Now one use a counting argument to show that it is not possible. Each face has atleast three boundary edges and each edge is the boundary of atmost two faces in a planar graph. Hence $2E\ge 3F$ . But we have $2E=20,3F=21$ . Hence $K_5$ has no planar realisation. Similarly for $K_{3,3}$ we get $F=5$ . But now each face has atleast four edges because $K_{3,3}$ being bipartite does not have a odd cycle. So we get $2E=18 \ge 4F=20$ , which is a contradiction. Now any graph containing these graphs is also non-planar. But interesting fact is that these obstructions are the only obstructions to planarity i.e., any non-planar graph has a subgraph which is homotopy equivalent to either $K_5$ or $K_{3,3}$ (Homotopy equivalence corresponds to the fact that they should not contain substructures of $K_5$ or $K_{3,3}$ that come up when we shrink an edge to a point.)

Now we move to another application of euler’s formula called the 5-neighbours theorem which says that any planar graph has a vertex with atmost five neighbours.

Proof: Add more number of edges to make all the faces triangular. We prove that the resulting graph has a vertex of atmost degree 5 so that the original graph also should have vertex of degree less than or equal to 5. By counting as above we have $2E=3F$ . Using this with $V-E+F=2$ we have $2E=6V$ , so that the average degree $2E/V= 6- \frac{12}{V}$ . Hence there should exist a vertex of degree $< 6$ . QED.

This result directly gives you the 6-colour theorem. Any planar graph can be coloured with 6 colours. (Infact 4 suffice. This is the famous 4-colour theorem.)

Proof. Assume the contrary and let $G$ be a graph with minimal number of vertices that cannot be coloured with 6 colours. Now let $v$ be vertex with degree less than 6 (which exists by above result). Remove the vertex $v$ from the graph and consider the resulting graph. This can be colored by 6 colors because of minimality of $latex G$. But we can now add the vertex $v$ to this graph and colour it with a sixth colour if it already had 5 neighbours. Thus we have a 6-colouring on G contradicting the assumption. Hence every planar graph has a 6-colouring.

Now we move onto another interesting application. Its the Picks theorem which gives the formula for the area of the polygon with vertices as integer points as $A=I+B/2-1$ where $I$ are number of integer lattice points in the interior of the polygon, $B$ is the number points on the boundary of the polygon.

Note that if the polygon was a triangle with no interior points we have $A=\frac{1}{2}$ . This comes from the pick’s formula and it also is due to the fact that such a triangle has half the area of a square which is one. So we triangulate our polygon such each triangle is a primitive one as above. Let the number of primitive triangles formed be $m$ . Now $3m$ counts the number of edges twice except for the boundary edges. So we have $3m=2E-\mbox{no. of boundary edges}$ . But the number of boundary edges is same as the number of boundary points. Hence we have $3m=2E-B$ . Also number of vertices $V=I+B$ . Eulers formula gives $V-E+F=2$ i.e, $I+B-(3m_B)/2+m=2$ Therefore we have $m=2I+B-2$ , area of the polygon $A$ =area of primitive polygon $\times$ number primitive triangles $\frac{1}{2} m= I+B/2 -1.$