If one could prove that for every 4-chromatic planar graph $X$ every color identical pair in $X$ is separated by a cycle, would that be a proof of the 4-color theorem?


A pair of vertices $\{u, v\}$ in a $k$-chromatic graph $G$ is a color identical pair iff the color of $u$ equals the color of $v$ in every $k$-coloring of $G$, and the supergraph of $G$ where $u$ and $v$ are adjacent, $(V(G), E(G) \cup \{uv\})$, then requires $k + 1$ colors.

For every $k$-critical graph $X$ and for every edge $xy$ in $X$, there is a $(k - 1)$-chromatic graph $Y = (V(X), E(X) \setminus \{xy\})$ where $\{x, y\}$ is a color identical pair (because, if there were a $(k - 1)$-coloring of $Y$ where $x$ and $y$ had different colors, that would also have been a $(k - 1)$-coloring of $X$).

E.g. removing an edge from $K_{5}$ gives a 4-chromatic graph of two tetrahedrons whose intersection is a triangle, and the two vertices that are not in the intersection are a color identical pair. On the plane these vertices are separated by the triangle.

  • 1
    $\begingroup$ I fail to see how a statement starting by "for every 4-chromatic planar graph" could imply the 4-color theorem: how would you apply it to a graph not known to be 4-colorable? $\endgroup$ Mar 11 '14 at 20:37
  • 2
    $\begingroup$ The point is (meant to be) in the explanation: Every 5-critical graph has a set of 4-chromatic subgraphs that each has a color identical pair {x, y}, and if in each subgraph x and y are separated by a cycle there is no planar 5-critical graph. $\endgroup$ Mar 11 '14 at 22:09
  • $\begingroup$ @AsbjørnBrændeland, is that not the answer to your question? In fact, does it not show that your claim is equivalent to the four colour theorem? $\endgroup$
    – Ben Barber
    Mar 12 '14 at 12:04
  • $\begingroup$ Well, that is what I think, but one is hesitant and cautious about claiming anything with regard to the four color theorem. $\endgroup$ Mar 12 '14 at 12:18
  • $\begingroup$ My only concern is what exactly "separated by a cycle" means. If it turns out to be equivalent to not being able to add an edge between the vertices without wrecking planarity then the equivalence is clear. So you just have to make sure that your definition of separating by cycles captures this notion correctly. $\endgroup$
    – Ben Barber
    Mar 12 '14 at 13:23

The claim appears to be equivalent to the four colour theorem. In the following I'll assume that "$x$ and $y$ can be separated by a cycle" is equivalent to "adding the edge between $x$ and $y$ produces a non-planar graph". (Perhaps this is what your question is actually about: formally showing that a reasonable definition of separating by a cycle captures the intended idea.)

So suppose that $G$ is a planar graph with chromatic number at least 5. Without loss of generality, $G$ is 5-critical. Choose an edge $e=xy$ of $G$ and consider $G-e$. This is 4-chromatic, and in every 4-colouring $x$ and $y$ must receive the same colour (else we have a 4-colouring of $G$). So by the claim, $x$ and $y$ can be separated by a cycle, contradicting the planarity of $G$.

In the other direction, suppose there is a 4-chromatic planar graph $G$ with colour identical vertices $x$ and $y$ such that $x$ and $y$ cannot be separated by a cycle. Then $G + xy$ is a 5-chromatic planar graph.

On being hesitant about claiming anything about the four colour theorem: you're reasonably safe making statements of the form "Claim X is equivalent to the four colour theorem". You only need to start to worry if you think you also have a simple proof of Claim X.

  • $\begingroup$ Well, I guess I should be worried then. I have actually submitted a text to arXiv about this, but I guess mathoverflow is not the proper place to advertice it. $\endgroup$ Mar 12 '14 at 13:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.