{"id":8582,"date":"2020-08-26T10:58:58","date_gmt":"2020-08-26T09:58:58","guid":{"rendered":"https:\/\/complex-systems-ai.com\/?page_id=8582"},"modified":"2022-11-27T20:58:04","modified_gmt":"2022-11-27T19:58:04","slug":"theoreme-des-quatre-couleurs","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/four-color-theorem\/","title":{"rendered":"Four Colors Theorem"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"8582\" class=\"elementor elementor-8582\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-625a941 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"625a941\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-fd08267\" data-id=\"fd08267\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-1b9468b elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"1b9468b\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Graph theory<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-4c35b03\" data-id=\"4c35b03\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-455a3ee elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"455a3ee\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/en\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Home page<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-88d4ed9\" data-id=\"88d4ed9\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-72eb328 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"72eb328\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/fr.wikipedia.org\/wiki\/Th%C3%A9or%C3%A8me_des_quatre_couleurs\" target=\"_blank\" rel=\"noopener\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Wiki<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-2d64e969 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"2d64e969\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-479a82e4\" data-id=\"479a82e4\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-760f3f65 elementor-widget elementor-widget-text-editor\" data-id=\"760f3f65\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p><\/p>\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_82_2 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contents<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewbox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewbox=\"0 0 24 24\" version=\"1.2\" baseprofile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/four-color-theorem\/#Theoreme-des-quatre-couleurs\" >Four color theorem<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/four-color-theorem\/#Histoire-du-theoreme-des-quatre-couleurs\" >History of the four color theorem<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Theoreme-des-quatre-couleurs\"><\/span>Four color theorem<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>The four color theorem states the possibility of coloring (we also say coloring in <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/\">graph theory<\/a>) with four colors only a geographical map without two neighboring countries having the same color.<\/p>\n<p><\/p>\n<figure><img fetchpriority=\"high\" decoding=\"async\" src=\"https:\/\/math93.com\/images\/images_doc\/4couleurs_france.gif\" alt=\"four color theorem\" width=\"450\" height=\"441\" title=\"\"><\/figure>\n<p><\/p>\n<p>To be more precise, the Four Colors Theorem states that by using only four different colors, it is possible to color any map cut into related regions (in one piece), so that two adjacent regions (or bordering), that is to say having a whole border (and not just a point) in common always receive two distinct colors.<br \/>Thus, each of the regions should be given a different color if the regions are two by two adjacent.<\/p>\n<p><\/p>\n<p>Moreover, there cannot exist five adjacent two by two connected regions (this is the easy part of Kuratowski&#039;s theorem).<\/p>\n<p><\/p>\n<p>This four-color theorem has practical application in the assignment by a mobile operator of GSM frequencies to the coverage areas of base stations in its network. Indeed, as in the situation of the four colors:<\/p>\n<p><\/p>\n<p>- a GSM network is modeled, like a geographical map, by contiguous hexagons: each hexagon (called \u201ccell\u201d, hence the notion of cellular network) corresponds to the radiation of a base station (approximately 30 km in diameter in rural area).<\/p>\n<p><\/p>\n<p>- two contiguous hexagons must in no case be assigned the same frequency band.<\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Histoire-du-theoreme-des-quatre-couleurs\"><\/span>History of the four color theorem<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p>The first four-color conjecture seems to have been made in 1852 by a South African mathematician and botanist, Francis Guthrie (1831 - 1899).<\/p>\n<p><\/p>\n<p>Francis Guthrie was a student at University College London, where he studied with the famous De Morgan.<br \/>He then turned to studies of botany, while his brother, Frederick Guthrie, became a mathematician and also followed De Morgan&#039;s courses.<br \/>Francis Guthrie notices that four colors are enough for him to color the (however complex) map of the cantons of England, without giving the same color to two adjacent cantons (having a common border).<br \/>He then asks his brother Frederick, if this property would not be true in general for any flat map; the latter communicated the conjecture to De Morgan, and in 1878 Cayley published it.<\/p>\n<p><\/p>\n<figure><img decoding=\"async\" title=\"The 4-color theorem\" src=\"https:\/\/math93.com\/images\/images_doc\/4couleurs.jpg\" alt=\"four color theorem\" width=\"210\" height=\"300\" \/><\/figure>\n<p><\/p>\n<p><\/p>\n<ul class=\"wp-block-list\">\n<li>As early as 1879, Kempe found a first &quot;proof&quot; of the conjecture, but eleven years later Heawood found a major flaw in it; however, he will manage to find a five-color theorem.<br \/>A second &quot;proof&quot; by Tait in 1880 will likewise be refuted by Petersen in 1891.<\/li>\n<li>In 1913, the American mathematician George David BIRKHOFF (1884 - 1944), demonstrated the conjecture for all maps with less than 26 regions to be colored.<br \/>This terminal is improved during the XX<sup>e<\/sup>\u00a0century.<\/li>\n<li>In 1969 Heesch found &quot;almost&quot; necessary and sufficient conditions for a configuration to be reducible, and a general method for finding an inevitable set of configurations.<\/li>\n<\/ul>\n<p><\/p>\n<p><strong>The first computer-generated proof.<\/strong><\/p>\n<p><\/p>\n<ul class=\"wp-block-list\">\n<li><strong>Finally, in 1976, the American mathematicians\u00a0<strong>Kenneth Appel<\/strong>\u00a0(died April 19, 2013 at age 80) and German mathematician Wolfgang Haken<\/strong>\u00a0carry out Heesch&#039;s program.<br \/>They show, using tens of thousands of figures, that any non-4-colorable map must contain one of the 1478 configurations, and, with 1200 hours of computation, that these configurations are reducible.\n<p>It&#039;s done\u00a0<strong>the first computerized proof of a mathematical theorem<\/strong>.<\/p>\n<\/li>\n<\/ul>\n<p><\/p>\n<ul class=\"wp-block-list\">\n<li>In 1995, Robertson, Sanders, Seymour and Thomas took advantage of the formidable acceleration of computers to find a much simpler realization of Heesch&#039;s program, with only 633 configurations; moreover they also automate the proof of inevitability.<\/li>\n<li>In September 2012, six years after the computer demonstration of the four color theorem, Georges Gonthier and his team succeeded in demonstrating Feit&#039;s theorem and <a href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/construction-of-thompson\/\">Thompson<\/a>. A theorem even more difficult to formalize.<\/li>\n<\/ul>\n<p><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>","protected":false},"excerpt":{"rendered":"<p>Graph theory Home page Wiki Four color theorem The four color theorem states the possibility of coloring (we also say coloring in \u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":2204,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-8582","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/8582","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/comments?post=8582"}],"version-history":[{"count":4,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/8582\/revisions"}],"predecessor-version":[{"id":17860,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/8582\/revisions\/17860"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/2204"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=8582"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}