# A conjecture on 4-coloring maximal planar graphs

The question/task is to prove/disprove the conjecture below.

Let $$G$$ be a maximal planar graph with a 4-coloring $$f$$. Let $$(a,b,c,d)$$ be a cycle in $$G$$. Let $$S$$ be the collection of all $$a,c$$-paths in $$G$$ and all $$b,d$$-paths in $$G$$.
Conjecture: At least two members of $$S$$ are bicolored.
(i.e., there exist distinct paths $$Q_1,Q_2\in S$$ and colors $$i,j,k,l\in\{1,2,3,4\}$$ such that $$f(u)\in\{i,j\}$$ for every vertex $$u$$ on $$Q_1$$ and $$f(v)\in\{k,l\}$$ for every vertex $$v$$ on $$Q_2$$).

Definitions:-
$$G$$ is a maximal planar graph if it can be drawn on a plane such that no edges cross and boundary of every face is a triangle. A 4-colouring $$f$$ of $$G$$ is a function $$f:V(G)\to\{1,2,3,4\}$$ such that $$f$$ map endpoints of each edge to different 'colors' (i.e. $$f(u)\neq f(v)$$ for every edge $$uv$$ of $$G$$).

Notes:-
It is easy to see that the conjecture is true if the cycle $$(a,b,c.d)$$ is tricolored (or bicolored). The following is the crux of the conjecture.

Let $$G$$ be a planar graph with a 4-coloring $$f$$. Let $$(a,b,c,b)$$ be a cycle in $$G$$ such that boundary of each face inside the cycle is a triangle. Suppose that the cycle $$(a,b,c,d)$$ receives all four colors.
Conjecture 2: Then, there is a bicolored $$a,c$$-path or a bicolored $$b,d$$-path inside the cycle.
If Conjecture 2 is true, then the main conjecture above is true (apply Conjecture 2 to outside region of the cycle $$(a,b,c,d)$$ ).

Theorem A.1. Let $$G$$ be an a-graph with boundary cycle $$uxvy$$ for the exterior 4-face and let $$G$$ have a 4-coloring $$c$$. Suppose, without loss of generality, that $$c(x)=1$$, $$c(y)=1$$ or 2, $$c(u)=3$$, and $$c(v)=3$$ or 4. Then there is either a 1–2 path between $$x$$ and $$y$$ or a 3–4 path between $$u$$ and $$v$$.