Color identical pairs and the 4-color theorem

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?

Explanation:

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.

• 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? Mar 11 '14 at 20:37
• 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. Mar 11 '14 at 22:09
• @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? Mar 12 '14 at 12:04
• Well, that is what I think, but one is hesitant and cautious about claiming anything with regard to the four color theorem. Mar 12 '14 at 12:18
• 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. 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.