The MCE can be made temporarily 4-colorable by removing a vertex of degree 5
from G. Then (G-v) can be triangulated by adding two edges.
But as shown in Figures 1 & 2; one or more of the vertex neighbors of v may not
have degree > = 5.
| \ / | | \ / |
---A--B--C--- ---A--B--C---
|\ | /| | / \ |
| \ / | |/ \|
| v | ---E-----D---
| / \ | | |
|/ \|
--- E-----D---
| |
Figure 1 Figure 2
In Figure 2, vertices A & C have degree < 5 and may be arbitrarily removed
without effecting the colorability of the graph.
Let H be the triangulation of (G-v). If we posit that H may be the MCE, then
H can not have any 4 degree vertices.