Five colour theorem in graph theory pdf

We prove that if a graph embeds on a surface with all edges suitably short, then the vertices of the graph can be five colored. Unless stated otherwise, we assume that all graphs are simple. Through a considerable amount of graph theory, the four color theorem was reduced to a nite, but large number 8900 of special cases. In general, this concept of coloring comes up all the time in graph theory. The formal proof proposed can also be regarded as an. The motivation is that a graph embedded with short edges is locally a planar graph and hence should not require many more than four colors. Avertexcoloring of agraphisanassignmentofcolorstotheverticesofthegraph. I was wondering if proof by induction or contradiction is better, but i decided for proof by induction, as this is easier to translate in actual code then. Eulers formula and the five color theorem contents 1. Four color theorem simple english wikipedia, the free. A graph on vertex can easily be coloured with just colour, while a graph with vertices can easily be coloured with just colours for a good colouring recall that we restrict ourselves to simple graphs. Tait, in 1880, showed that the four color theorem is equivalent to the statement that a certain type of graph called a snark in modern terminology must be nonplanar.

I plan to show them the proof for the six five coloring theorems and also give a brief discussion of the famous four color theorem. The lines may be directed arcs or undirected edges, each linking a pair of vertices. Marcus, in that it combines the features of a textbook with those of a problem workbook. Ygsuch that no edge in this graph has both endpoints colored the same color. In this post, i am writing on the proof of famous theorem known as five color theorem. In the example above, the chromatic number was 5, but this is not a counterexample to the four color theorem, since the graph representing the radio stations is not planar. There are at most 4 colors that have been used on the neighbors of v. A graph is a pair of sets g v,e where v is a set of vertices and e is a collection of edges whose endpoints are in v. Well, besides the obvious application to cartography, graph coloring algorithms and theory can be applied to a number of situations.

Graph theory, four color theorem, coloring problems. Let g be the smallest planar graph in terms of number of vertices that cannot be colored with five colors. The four color problem remained unsolved for more than a century. Our goal today is to prove that any planar graph can be coloured with 5 colours. Most standard texts on graph theory such as diestel, 2000,lovasz, 1993,west, 1996 have chapters on graph coloring. The subject of graph theory had its beginnings in recreational math problems see number game, but it has grown into a significant area of mathematical research, with applications in chemistry, operations research, social sciences, and computer science. Appel and haken published an article in scienti c american in 1977 which showed that the answer to the problem is yes. I might be giving a talk to high school students soon. Kempes proof for the four color theorem follows below. Using a similar method to that for the formal proof of the five color theorem, a formal proof is proposed in this paper of the four color theorem, namely, every planar graph is fourcolorable. We will prove this five color theorem, but first we need some other results. Graph theory presents a natural, readerfriendly way to learn some of the essential ideas of graph theory starting from first principles. That is, for all connected planar simple graphs on vertices. What are the reallife applications of four color theorem.

Thinking about graph coloring problems as colorable vertices and edges at a high level allows us to apply graph co. Cs 408 planar graphs abhiram ranade a graph is planar if it can be drawn in the plane without edges cross. Heawoods theorem on 5colorability of planar graphs. One of the earliest results in graph theory is eulers formula. Planar graphs graph theory fall 2011 rutgers university swastik kopparty a graph is called planar if it can be drawn in the plane r2 with vertex v drawn as a point fv 2r2, and edge u. Then we prove several theorems, including eulers formula and the five color theorem. In 1890, in addition to exposing the flaw in kempes proof, heawood proved the five color theorem and generalized the four color conjecture to surfaces of arbitrary genus. The five color theorem is a result from graph theory that given a plane separated into regions, such as a political map of the counties of a state, the regions may be colored using no more than five colors in such a way that no two adjacent regions receive the same color. To color a given graph, their first step is to scour the graph for a structure. The crossreferences in the text and in the margins are active links. One early example of this technique is kainens proof 7 of the 5 color theorem. It is not in anyway comprehensive overview of graph theory, and it doesnt pretend to be. A bad idea, we think, directed people to a rough road.

Introduction the five color theorem is a result from graph theory that given a plane. Proofs of the five colour theorem and the heawood colouring theorem are included, as well as demonstrations of eulers. Introduction to graph theory dover books on mathematics. Four, five, and six color theorems nature of mathematics. So g can be colored with five colors, a contradiction. To prove that every planar graph can be colored with at most ve colors, we. In fact, this proof is extremely elaborate and only recently discovered and is known as the 4colour map theorem. Four color theorem wikimili, the best wikipedia reader. The five color theorem is a result from graph theory that given a plane separated into regions, such as a political map of the counties of a state, the regions may. The four color theorem 28 march 2012 4 color theorem 28 march 2012.

Then, we will prove eulers formula and apply it to prove the five color theorem. Contents introduction preliminaries for map coloring. News about this project harvard department of mathematics. Eulers formula and the five color theorem min jae song abstract. The format is similar to the companion text, combinatorics. Take any connected planar graph on nitely many vertices. If g is a planar graph, then by eulers theorem, g has a 5. I feel that, by retitling the book introduction to graph theory, dover has done this particular book a bit of a disservice. Today we are going to investigate the issue of coloring maps and how many colors are required. But the strong perfect graph theorem provides a surprisingly simple recipe for perfection. April 18, 2017 april 18, 2017 namita tiwari discreate maths discreate math.

The five color theorem is implied by the stronger four color theorem, but is considerably easier to prove. Conversely any planar graph can be formed from a map in this way. Four, five, and six color theorems in 1852, francis guthrie pictured above, a british mathematician and botanist was looking at maps of the counties in england and discovered that he could always color these maps such that no adjacent country is the same color with at most four colors. There is a way to assign each of its vertices one of the four colors fr. Students will gain practice in graph theory problems and writing algorithms. Though heawood solved the five color theorem using the principle of.

We assume that there exists a minimal graph that is not four colorable, thus every smaller graph can be four colored, for coloring graphs we will use the colors. In 1879, alfred kempe gave a proof that was widely known, but was incorrect, though it was not until 1890 that this was noticed by percy heawood, who modified the proof to show that five colors suffice to color any planar graph. Graph theory, branch of mathematics concerned with networks of points connected by lines. The 6 color theorem nowitiseasytoprovethe6 colortheorem. In graphtheoretic terminology, the fourcolor theorem states that the vertices of every planar graph can be colored with at most four colors so that no two adjacent vertices receive the same color, or for short. Recent research in physics shows that this proof directly implies the grand unification of the standard model with quantum gravity in its physical interpretation and conversely the existence of the standard model of particle physics shows that nature applies this proof of the four colour theorem at the most fundamental level. Pdf a generalization of the 5color theorem researchgate. Amongst other fields, graph theory as applied to mapping has proved to be useful in planning wireless communication networks. In 1969 heinrich heesch published a method for solving the problem using computers. The four colour theorem mactutor math history archives linked essay describing work on the theorem from its posing in 1852 through its solution in 1976, with two other web sites and 9 references booksarticles. In this paper, we introduce graph theory, and discuss the four color theorem. Let v be a vertex in g that has the maximum degree. The three and five color theorem proved here states that the vertices of g can be colored with five colors, and using at most three colors on the boundary of.

The topic mixes chromatic graph theory, integral geometry and is motivated by results known in differential geometry like the farymilnor theorem of 1950 which writes total curvature of a knot as an index expectation and is elementary. They will learn the four color theorem and how it relates to map. Article pdf available in proceedings of the american mathematical. This is usually done by constructing the dualgraphof the map, and then appealing to the compactness theorem of propositional. As berge correctly guessed 54 years ago, a graph is perfect when it does not contain any arrangements of five or more nodes called odd holes or odd antiholes. A coloring is proper if adjacent vertices have different colors. Why is the four color theorem so much harder to prove than the six five color theorems.