DOC PREVIEW
MIT 18 310C - Planarity and Coloring

This preview shows page 1-2-3-4 out of 11 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

15. Planarity and Coloring 15.1 Introduction We have been considering the notions of the colorability of a graph and its planarity (see notes 14). We have seen that a graph can be drawn in the plane if and only if it does not contain a subdivision of K5 or K3,3. We have also seen how to determine whether the coloring number of a graph is 2. We shall now examine the much harder problem of characterizing graphs of higher coloring number (at least 3-colorable). A natural question, which was raised back in the 19th century is: What is the largest coloring number among planar graphs? In other words, what is the largest number of colors you need to color any graph that can be drawn in the plane? A man named Kempe published a proof in 1879 that all planar maps are 4-colorable. However, this proof was incorrect and ten years later, someone noticed this and pointed it out. As a result, this became a well-known problem. Was Kempe right? Is the largest coloring number among planar graphs 4? Many mathematicians worked very hard on this problem and produced many partial results. Finally, about a hundred years after Kempe’s paper, a computer-aided proof was announced by Appel and Haaken. It uses few ideas beyond those employed by Kempe, but applies them to thousands of cases using a computer, and provides a proof of his claim. We will provide a proof that five colors are enough to color any planar graph, and then present Kempe’s flawed proof that four colors are enough. First, however, we must prove a few results that will be necessary in our later results. 15.2 Euler’s Formula Suppose we have a planar graph G, and we make a drawing of it as we discussed in notes 14. The drawing itself has properties that G, as a set of edges and vertices, does not possess. In particular, the edges of G divide the plane into separated regions called faces. For example, if we have a simple 3-cycle as our graph, then it has two faces, the “inside” and the “outside”. The following graph has 4 faces (3 inside and one outside).The boundary of a face is the set of edges that enclose it. If we define the parameters v, e, and f to be the number of vertices, edges, and faces of the drawing of G, there is a wonderful relation between these numbers that holds whenever G is a connected graph: v − e + f = 2 If G has more than one connected component, then we change the formula a little, with cc being the number of connected components of G: v − e + f = 1 + cc This relation is called Euler’s formula. We will now prove it. It is obvious that this relation holds for a single vertex with no edges, as well as for two vertices with one edge between them. We shall use an inductive proof by assuming that Euler’s relation holds for a graph, and showing that it still holds if we add a new vertex or a new edge. Suppose we have a planar drawing of a graph G and we add a new edge or a new vertex to G so that the new drawing of the resultant graph has no edge crossings and is thus still planar. There are only a small number of ways in which we could add a vertex or an edge. If we add a new vertex on an edge of G, then this splits that edge into two edges, so e and v both increase by 1, so the equality holds. If we add a vertex not on any edge, then it is an isolated point and so v and cc increase by 1, and still the equality holds. These are the only ways in which on can add a vertex, since it is either on an edge or not. Thus, Euler’s formula holds for the addition of a vertex. Suppose we add an edge between two vertices of G. If there is a path in G between the end of the new edge, then adding the edge creates a face and so e and f increase by 1. Since there was already a path connecting the vertices, cc remains unchanged. If there was no path connecting them, then f remains unchanged, but eincreases by 1 and cc decreases by 1 (since we have connected two previously unconnected components with this new edge). Since either a path connected the vertices of the new edge or it did not, so these are the only ways to add a new edge. Since both of them preserve Euler’s formula, we see that it holds for the addition of an edge. We see that Euler’s formula holds for the addition of a vertex or an edge to G, so we see by induction that Euler’s formula is true. □ 15.3 The Average Degree of a Planar Graph We now ask: what is the largest number of edges that a planar graph with v vertices can have? We can deduce the answer from Euler’s formula. Each face defined by a drawing of G in the plane is bounded by a cycle of G. If that cycle is not a triangle, we can add an edge between two opposite vertices and increase the number of edges. Let us look at graph (1) from above as an example: The above illustration only shows how to turn one face into all triangles. If we really want to maximize the number of edges in graph (1), then we can make 4 more triangles in the following way (note that triangles in this sense are faces with 3 edges; the edges do not have to be straight): We conclude then that a graph G on v vertices with the most edges will have triangles for all its faces.1 On such a graph, each face has three edges on its boundary. We will form “edge-face pairs” between a face and each of its edges. This means there are 3 edge-face pairs for each face, and thus 3f of them altogether. We can also see that each edge bounds two faces, so the number of edge-face pairs will also be 2e. We deduce then that f = 32e f, so that in this case we can write Euler’s formula asv − 3 + 2e /3 = 2 or 3v = e + 6 If we look at graph (2) above, we can see that this last equality holds in this case. We notice also that since each edge has two vertices, the number of edge-vertex pairs is 2e and is also equal to the sum of the degrees of all the vertices (recall that the degree of a vertex is the number of edges that contain it as an endpoint). This tells us that the sum of the degrees of the vertices of any planar graph G with v vertices and the maximum number of edges is 2e. Using the equation3v = e + 6 , we get that: [The sum of the degrees of the vertices of G] = 6v – …


View Full Document
Download Planarity and Coloring
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Planarity and Coloring and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Planarity and Coloring 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?