Coloring general graphs is, as I said in my last post, quite difficult. But if you can restrict the structure of the graph, you can change the problem in a way that makes it *much* easier. The classic example of this is *planar graphs*.
\n![\"map.jpg\"](\"https:\/\/i0.wp.com\/scientopia.org\/img-archive\/goodmath\/img_168.jpg?resize=214%2C210\")
\nA planar graph is a graph which can be drawn on a plane with no edges crossing. Every planar graph is also the structural equivalent to a map, where the vertices corresponding to two countries on a map are adjacent if and only if the countries share a border in the map. (A border here has non-zero length, so two countries that only meet in a corner don’t share a border.) You can see an example of a map with its corresponding planar graph overlayed to the right.<\/p>\n
\nIn the late 19th century, it was proven that any planar graph could be colored with only five colors. (Actually, it was an *attempt* to prove that any planar graph could be colored with only four colors, but the proof contained an error; after correcting it, it could only show that you could color a planar graph with no more than 5 colors.) Not only that, but exploiting the properties of a planar graph, you can 5-color a planar graph in *linear* time.
\nPeople were pretty much sure that it was true that every planar graph could be
\nfour-colored, but every attempt to prove it failed. The work that led to the eventual
\nproof was based on the idea of looking at the failed proofs, examining the cases that
\nthey missed, and figuring what a counterexample of the 4-color theorem would look like. For example, there’s a result along the way called the *snark theorem*, which defines an interesting kind of graph which could potentially be a basis for a counterexample.
\n(Calling this kind of graph a snark, and the theorem the snark theorem is a relatively recent thing; but it’s now pretty widely used.)
\n![\"snark20.jpg\"](\"https:\/\/i0.wp.com\/scientopia.org\/img-archive\/goodmath\/img_169.jpg?resize=183%2C186\")
\nA snark is a graph with the following properties:
\n1. It’s connected: there is a path from any node in the graph to any other
\nnode in the graph.
\n2. It’s *bridgeless*: there is no single edge that will split the graph
\ninto two disconnected subgraphs if it’s removed.
\n3. It’s *cubic*: every node has three edges.
\n4. It has chromatic number 4: it can’t be colored in less than 4 colors.
\nThe snark theorem says that the four-color theorem is *equivalent* to the
\nstatement that no snark is planar.
\nThe work to find a counterexample never managed to find one. Finally, in 1976, Andrew Appel at UIUC came up with a proof of the 4-color theorem: it seemed to work, but it was
\n(and in fact still is) rather controversial. The idea of it was to define the properties of any graph that could form a counterexample. This produced a collection of close to 2000 graphs in the original version, which were called *unavoidable* graphs, because any minimal counterexample to the 4-color theorem needed to include at least one of them as a counterexample. (They later managed to reduce that set to 1476 unavoidable graphs.) The
\ncollection of unavoidable graphs was generated by a computer program, and then the resulting set of graphs was 4-colored. So they exhaustively showed that every possible
\ncounterexample to the 4-color theorem was 4-colorable. (You can see a more modern version
\nof the proof based on a set of 633 unavoidable configurations [here][thomas].)
\n[thomas]: http:\/\/www.math.gatech.edu\/~thomas\/FC\/fourcolor.html
\nThe big reason for the controversy was that THE proof was over 500 pages long, and
\nrelied on an extremely complicated algorithm to produce the unavoidable graphs. No one could really hold the entire thing in their head, and no one could
\nmanually reproduce the results. This meant that accepting the correctness of the proof came down to accepting the correctness of the program that generated it – and in fact, not just the correctness of the program, but the correctness of the compiler and the hardware than ran it. And that was, and still is, not at all a popular idea.
\nIt’s also considered by many purists to be *ugly*. The common quote about it (and I haven’t been able to find a definitive source for who first said it) is: “A good proof is like a poem; this beast is more like a telephone book.”
\nBut the fact remains that it seems to be true. It’s been reproduced by multiple people
\nusing multiple independently written programs; the number of cases has been pared down
\nconsiderably; and pretty much everyone agrees that it’s true, even if the proof is not
\nexactly loved.
\nPeople have also written 4-coloring algorithms, which are reasonably efficient. Given a planar graph, you can 4-color it in quadratic time. Quadratic isn’t great, but it’s a far cry better than exponential.<\/p>\n","protected":false},"excerpt":{"rendered":"
Coloring general graphs is, as I said in my last post, quite difficult. But if you can restrict the structure of the graph, you can change the problem in a way that makes it *much* easier. The classic example of this is *planar graphs*. A planar graph is a graph which can be drawn on […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[25],"tags":[],"class_list":["post-458","post","type-post","status-publish","format-standard","hentry","category-graph-theory"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-7o","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/458","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=458"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/458\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=458"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=458"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=458"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}