The algorithm is: pick an edge $x y_1$. Inductively find a $\Delta+1$ colouring $\phi$ of $G \setminus \{ x \to y_1 \}$.
For every vertex, there is a colour which is not used at that vertex, because the degree of the vertex is $\leq \Delta$ but we have $\Delta+1$ colours to choose from.
Let $c$ be a colour missing from vertex $x$, and $c_1$ missing from $y_1$.
Then if $c_1$ is missing at $x$, we are done: colour the edge $x y_1$ with colour $c_1$.
Otherwise, $c_1$ is not missing at $x$, so there is some $y_2$ in the neighbourhood $\Gamma$ of $x$ with $\phi(x \to y_2) = c_1$.
Repeat: given $y_1, \dots, y_k \in \Gamma(x)$ distinct, and distinct colours $c_1, \dots, c_k$ such that $c_i$ is missing at $y_i$ for all $i$, and $\phi(x y_i) = c_{i-1}$, do the following: if $c_k$ is missing at $x$, stop and recolour $x y_i$ with colour $c_i$. Otherwise, let $y_{k+1} \in \Gamma(x)$ be such that $\phi(x y_{k+1}) = c_k$, and let $c_{k+1}$ be a colour missing at $y_{k+1}$.
This process builds a list of distinct $y_i$ and $c_i$, so eventually it must terminate: it can only terminate if we find $c_{k+1}$ which has already appeared as an earlier $c_i$.
Wlog $c_1 = c_{k+1}$, because we can recolour $x y_j$ with colour $c_j$ for $1 \leq j \leq i-1$ and un-colour $x y_i$ itself.
Consider the subgraph of $G$ which is coloured only in colours $c_1, c$ (recalling that $c$ is the colour missing at $x$).
The maximum degree of this subgraph is $2$, so its components are paths and cycles; but $x, y_1, y_{k+1}$ all have degree $1$ in this subgraph and so must not lie in the same component.
If $x, y_1$ are disconnected in the subgraph, swap $c, c_1$ on the $c, c_1$-component of $y_1$, and let $\phi(x, y_1) = c$.
Otherwise, $x, y_{k+1}$ are disconnected in the subgraph, so swap $c$ and $c_1$ on the $c, c_1$-component of $y_{k+1}$, and recolour $x y_{k+1}$ by $c$, $x y_i$ by $c_i$ for each $i \in [1, k]$.
This type of coloring is called a vertex-edge-face coloring in this paper, where the same conjecture is made: that for any planar graph $G$ with maximum degree $\Delta$,
$$
\chi^{vef}(G) \le \Delta + 4,
$$
where $\chi^{vef}$ is the vertex-edge-face chromatic number. (Actually, the paper's Conjecture 1 goes further and makes this conjecture for list coloring.) Furthermore, the paper proves this when $\Delta \ge 12$.
There are a couple of ways to prove the weaker result that $\chi^{vef}(G) \le \Delta + 7$: either
- By combining Theorem 1 of this paper (due to Borodin) that $\chi^{vf}(G) \le 6$ for planar graphs, with Vizing's theorem that $\chi^e(G) \le \Delta+1$ for all graphs, or
- By combining Theorem 2 of this paper (due to Waller) that $\chi^{ef}(G) \le \Delta+3$ for planar graphs, with the four-color theorem that $\chi^v(G) \le 4$ for planar graphs.
Best Answer
A possible strategy is the following (I did not work on details, e.g. might work for even/odd $n$ only, and the expressions may not be accurate, but the general idea is hopefully clear) -
Starting from a graph with no edge, we add colored edges in iterations, such that in iteration $i$ each node has degree $2i$ (or $i$ for even $n$?). Let $p_i$ be the probability of success until the end of iteration $i$, and $q_i$ the probability of failing before the end of iteration $i$. Then considering we add $n$ new edges in iteration $i$, we have:
$$ p_{i-1} \cdot \left(1-\frac{4i}{m}\right)^n \le p_i \le p_{i-1} \cdot \left(1-\frac{2i}{m}\right)^n$$
which makes it easy to estimate the desired probability $p_{n/2}$. Also, the failure probability can be estimated combining the above with the following:
$$q_i = q_{i-1} + (1-q_{i-1})\cdot (1-p_{i})$$
Though I'm not sure if this is a sufficiently delicate solution!