Some probabilistic restatements of the Four Color Conjecture (Q4474281)

The cut graph \(H_G\) of \(G\), a triangulation of the plane, is a graph consisting of vertex-disjoint triangles, one corresponding to each face of \(G\) (and thus each edge of \(G\) corresponds to two edges in \(H_G\)). A proper edge-coloring with colors 0, 1, 2 of \(H_G\) is called even (odd) if, for an even (odd) number of faces of \(G\), the colors \(0,1,2\) in the corresponding triangle of \(H_G\) appear in the ``clockwise order''. A labeling of the edges of \(G\) can be obtained from the coloring of \(H_G\) by labeling each edge \(e\) with the modulo 3 sum of the colors on the two copies of \(e\) in \(H_G\). For two randomly chosen edge-colorings of \(H_G\), let \(A_G\) be the event that they have the same parity, and \(B_G\) be the event that they produce the same labeling on \(G\). The main result of this paper is that the four color theorem is equivalent to the statement that for every triangulation \(G\), the events \(A_G\) and \(B_G\) are (positively) correlated. The main result follows from a direct expression of this correlation in terms of the number of 4-colorings of \(G\). The clever derivation of this expression is accomplished by the use of a generating function \(M\) that encodes all possible 3-colorings of the edges of \(H_G\), as well as their parity. Multiplying two suitable forms of \(M\) another generating function is obtained whose constant term is, on the one hand, the correlation, and on the other hand, the desired expression. The connection between edge- and vertex-colorings of \(G\) is via Tait colorings.