Famous Theorems of Mathematics/Four color theorem

From Wikibooks, open books for an open world
Jump to navigation Jump to search

Although technically the four color theorem has been proven, for some – professionals and amateurs alike – attempting to discover a more elegant solution to the Four Color Theorem is an engrossing pastime. In theory nothing more than a pencil, some paper, and some thought should be required.

Tips[edit | edit source]

  • It is easier to work with graphs than maps. Maps are equivalent to their duals, which are planar graphs. Each region corresponds to a vertex and borders between regions correspond to edges. Borders without length are disregarded.
  • On the other hand, working with cubic maps, we can switch prove a 3-coloring of the edges, which is equivalent to a 4-coloring of the areas.
  • It is assumed that it will be easier to prove the Four Color Theorem for fully-triangulated planar graphs. A planar graph which is not fully-triangulated (i.e. it is missing some edges) can easily be made fully-triangulated by adding some edges. Then, after a 4-coloring is found, those additional edges can be removed. However, if you are attempting to solve the Four Color Theorem as a route to solving P = NP, note that it is the finding of a 3-coloring of a [possibly non-fully-triangulated] graph – or proving that such a 3-coloring does not exist – that is hard.
  • The dual of a fully-triangulated planar graph is a cubic planar graph. Cubic means that every vertex has 3 edges. However, not every cubic planar graph has a Hamiltonian cycle – if it did, it would prove the Four Color Theorem. For examples of cubic planar graphs without a hamiltonian see: Tutte's counter-example with 46 vertices and 60 edges; Kozyrev and Grinberg's counter-example with 44 vertices; and Lederberg's or Barnette and Bosák's counter-example with 38 vertices.
  • We can prove that we need not discuss graphs with a connectivity lower than 4. According to Tutte, planar graphs with a connectivity of 4 or higher have a Hamiltonian cycle (of the nodes regarding the graph, or of the areas regarding the map). A Hamiltonian cycle provides us with a trivial way to impose a linear order on our nodes (or areas).

Mis-steps[edit | edit source]

Here are some of the common pitfalls for the beginner:

  • Not every graph can be generated by starting with a triangle and adding 1 vertex and 3 edges i.e. keeping the graph fully triangulated as each vertex is added. The smallest graph with minimum degree 4 has 6 vertices. The smallest graph with minimum degree 5 has 12 vertices.
  • To generate *every* graph, work it the other way around : in every graph you may eliminate a node by contracting two neighboring nodes in to a single node along their connecting edge. Inversely, we can create every graph by expanding a node into two neighboring ones.

Ideas[edit | edit source]

The Four Color Theorem is equivalent to finding a Bi-BiPartite solution. In other words it is sufficient to separate the vertexes into just 2 sets – if each set is itself BiPartite. This is actually a simplification because it is clear what makes a graph BiPartite: no odd cycles. If the graph can be decomposed into 2 subgraphs such that each subgraph has only even cycles or no cycles, a solution has been found.

The Four Color Theorem can be equivalent to finding a solution to an equation or a set of equations and may be easier to work with in matrix form.

The simplest equation is of the form (A-B)(A-C)... != 0 where A,B,C,... represent the colors of the vertexes. If 2 vertexes are adjacent, then their values are subtracted. It thus becomes a 'satisfiability problem' in that values for A,B,C... must be found that 'satisfy' the inequality. If two adjacent vertexes have the same color, then their difference is 0 and the entire equation yields 0. Inequalities are not easy to solve using matrix.

To prove an equation representing a 4-coloring or an equivalent assertion, we might have to find a (matrix) equation describing planarity, our main premise.

Minimum Counter Example to the Four Color Theorem[edit | edit source]

The Four Color Theorem (4CT) essentially says that "the vertices of a planar graph may be colored with no more than four different colors."

A graph is a set of points (called vertices) which are connected in pairs by rays called edges. In a complete graph, all pairs are connected by an edge. In a planar graph only those pairs whose edges do not cross or intersect are connected. A complete planar graph is one which has exactly edges. [ is the number of vertices] Vertices that are connected by an edge are called adjacent vertices Vertices that are not connected are called disjoint vertices.

The 4CT implies that adjacent vertices cannot have the same color; and that four colors are sufficient to meet this condition.

HYPOTHESIS: If the 4CT is true for all fully triangulated planar graphs (FTPG), then it is true for all planar graphs.

Therefore, it is necessary only to prove the 4CT for FTPG's!

The degree of a vertex is the number of vertices with which it shares an edge.

It is generally agreed that every vertex in a 5-chroma planar graph must have degree . [A 5-chroma planar graph is a graph that cannot be properly colored with less than five colors. In a "properly" colored graph, no two adjacent vertices will have the same color.]

If the 4CT is false, then there must be 5-chroma planar graphs. If such graphs exist, it should be possible to remove vertices and edges from such a graph until the smallest possible 5-chroma graph remains. This is a lot of work, so someone else has already done this for us. This "smallest possible" graph is called a "minimal counter-example to the Four Color Theorem"; more conveniently, MCE/4CT.

One way of proving the 4CT to be true is to prove that every graph thought to be an MCE/4CT is really not!

An MCE/4CT is by definition is a 5-chroma simple loopless planar graph and by choice, a FTPG. If any vertex is removed from a true MCE/4CT, then a 4-colorable graph will always result.

A proposed MCE/4CT is not a true MCE/4CT if it can be shown that there is a least one smaller graph; i.e., one with fewer vertices, that is also 5-chroma.

This is a difficult task, but it is not complex. Complex in the sense that there are many configurations to analyze. It is necessary to analyze only one configuration. This is the subgraph of the MCE/4CT which consists of a vertex of degree = 5 and its 5 neighboring vertices. Every MCE/4CT has at least one such vertex. Figure 1 below is a typical subgraph of a fully triangulated planar graph (FTPG)

             1-----2
             |\   /|
             | \ / |
             5--0--3
              \ | /
               \|/
                4
            Figure 1
              

where the central vertex v_0 has degree = 5. Every vertex with degree = 5 in a FTPG will have exactly the same local graph.

For convenience let graph G be a proposed MCE/4CT. Then Chi(G) = 5; i.e., G is 5-chroma. If v_0 is removed as in Figure 2,

             1-----2
             |     |
             |     |
             5     3
              \   /
               \ /
                4
            Figure 2

then Chi(G-v) must always be <5! [(G-v) is the subgraph of G that remains after vertex v_0 has been removed.]

HYPOTHESIS: There is only one vertex coloring pattern for Figure 2 that will allow Chi(G-v) to equal 4 and at the same time insure that Chi(G) is always greater than 4 when v_0 is restored. The pattern is C1-C2-C3-C4-C3. Figure 2 must have a 4-coloring. This is necessary if (G-v) is 4-colorable and G is not 4-colorable. A 3-coloring of Figure 2 would not require G to be 5-chroma.

Figure 3, shows a typical 4-coloring of the vertices of the graph in Figure 2.

             R     G
             1-----2
             |     |
             |     |
           B 5     3 B
              \   /
               \ /
                4
                Y
            Figure 3

Usually, Figure 3 can be 3-colored But in this case,the configuration of (G-v) is such that a normal 3-coloring is not possible!

None of the configurations of(G-v) are known. It is possible that they are also "unknowable"? Yet is essential that we acknowledge that they may exist!

Here's a new approach!

Because G is a FTPG, its dual is a cubic planar graph (CPG); i.e., C_g. If G is not 4-C, then C_g cannot be bridgeless!

Now consider graph (G-v). It is not fully triangulated. But it can be fully triangulated by the addition of two edges. A typical triangulation is shown in Figure 4.

             1-------2
             |\     /|
             | \   / |
             |  \ /  | 
             5---4---3                
           
            Figure 4.

Now graph (G-v) is fully triangulated and its dual is a cubic planar graph; i.e., graph C_v.

The a priori presumption is that C_v is bridgeless, and that C_G is not bridgeless!.

If you want to disprove the existence of a minimal counter example, you may also concentrate on the "minimal" part. If counter examples exist, there has to be a minimal one. Now if we can prove that every supposed minimal counter example can be used to construct a smaller counter example, we disprove the existence of counter examples at all.

Four Color Theorem for Maximal Planar Graphs [MPG][edit | edit source]

The 4CT for MPGs is a sub theorem for the 4CT for all planar graphs. It simply states that all MPG's are 4-colorable.

The advantage of MPGs is that certain statements can be made about their structure; i.e., the way that they are drawn on the page.

One convenient way to draw a MPG is to start with a single vertex (V). V is drawn surrounded by 5 or more adjacent vertices. These neighbors of V form a closed ring called a "cycle" graph. This ring is in turn surrounded by a second cycle formed by some or all of the neighbors of the vertices in the first ring. A third closed ring encloses the second ring, etc. This continues until all vertices have been used. The final ring will have only three vertices.

Only if the graph is maximal, will it be certain that all of the rings are closed.

The concentric ring configuration is a concept that is not easy to prove!

The main problem with this ring configuration is not that rings may not be closed, but that rings may be short-circuited, in which case there's not a single "next" ring, but multiple next *rings*. If there is no single outermost ring, contraction to a single node doesn't work and there's no necessity for a single final color.

HYPOTHESIS: The colors of each ring are determined by the colors of the next external ring.

HYPOTHESIS. It requires 4 colors in one ring to force 4 colors on the next internal ring.

For any ring in a MPG there must be four coloring of MPG in which the external ring is 3-colorable. Otherwise the MPG can be used to construct counterexample to 4CT. Just join the nodes of the external ring to another new node.

If these hypotheses are true, then the 4CT for MPGs is true.

Rationale: The outermost ring can have only three colors. Therefore, none of the rings can have more than three colors!