let the planar connected graph G be embedded in the plane sh

let the planar connected graph G be embedded in the plane, show that G has a region with 5 or less sides.

Solution

A graph is planar if it can be drawn in the plane without edges crossing.

More formally, a graph is planar if it has an embedding in the plane, in which each vertex is mapped to a distinct point P(v), and edge (u, v) to simple curves connecting P(u), P(v), such that curves intersect only at their endpoints. Examples of planar graphs: Pn, Trees, Cycles, X-tree, K4. Examples of non-planar graphs: Qn for n¿3, K5, K3,3, the complete bipartite graph which each partition having 3 vertices. An important notion for planar graphs is that of a Face: which is simply a region of the plane bounded by edges of the graph. The outer infinite region is also considered a face. Planar graphs are important for several reasons. First, they are very closely linked to the early history of graph theory. Second, in the mechanical analysis of two dimensional structures, the structures get partitioned and these partitions can be represented using planar graphs. Planar graphs are also interesting because they are a large class of graphs having small separators. After studying some basic notions, we will study the colouring and separation of planar graphs. 1 Euler’s Formula One of the earliest results in Graph Theory is Euler’s formula. Theorem 1 (Euler’s Formula) 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, then v + f = e + 2 Proof: Let us generalize it to allow multiple connected components c. In that case the formula becomes v + f = e + c + 1. The proof is by induction over e. If e = 0, we have v = c, f = 1, and the theorem holds. Suppose we remove an edge: (1) either the number of faces reduces by 1, or (2) number of components increases by 1. In each case, if the formula is 1 true for the new graph, it is true for the old one. Planar graphs are sparse. Corollary 1 In a finite, connected, simple, planar graph, e 3v6 if v 3. If the graph is also bipartite, then e 2v 4. Proof: If the graph is simple, then every face has at least 3 edges. Now 3f would count every edge 2 times, so we have 3f 2e. But e + 2 = v + f v + 2e/3. So 3e + 6 3v + 2e. So e 3v 6. In a bipartite graph every face must have at least 4 sides. Thus 4f 2e, and the result follows similarly.

We prove by induction on the number of vertices. The base case is with v = 3 and clearly holds. Let G be any graph with v 3. We know that e 3v 6. Thus the average degree 2e/v (6v 12)/v < 6. Thus G must have a vertex u with degree at most 5. By induction we know that G {u} can be coloured using 5 colours. If u has degree only 4, or if u has neighbours of only 4 colours, we can colour it using the remaining colour. So u must have 5 neighbours p, q, r, s, t, each having a different colour, say with colours 1,2,3,4,5. Suppose we change the colour of r to 1.

If r already has neighbours of colour 1, we change their colour to 3.

If they have neighbours with colour 3, we change them to 1 and so on.

In this process if the colour of p does not change, then we colour u with 3.

So assume that the colour of 1 does change.

But then we know that there is a cycle C containing v (uncoloured) and other vertices of colours 1,3, with q of colour 2 inside it.

Now suppose we change the colour of q to 4. We know that this change will not reach s, because s is outside C while q is inside. Thus we now colour u using colour 2.