I turned in my proof and the teacher said it is correct, so here it is again:
Assume the contrary, let there exist such a graph $G$. Since $G$ is planar, we can build a graph $G^*$ dual to $G$. Any two faces in $G$ share an edge $\implies$ any two faces in $G$ are adjacent $\implies$ any two vertices in $G^*$ are also adjacent (by the property of dual graphs). Since $G$ has 5 faces, $G^*$ has 5 vertices. So, $G^*$ is a complete graph on five vertices which might contain loops and parallel edges. Obviously, $K_5$ is a subgraph of $G^*$. Therefore, by Kuratowski's theorem, $G^*$ cannot be planar, which contradicts the property of dual graphs (a graph dual to a planar graph is also planar).
Q.E.D.
I'll solve the problem in three steps:
(1) First I'll show that any connected graph $G$ with an even number, $2m$, of edges is the edge-disjoint union of $m$ trails of length 2.
(2) If $G$ is a graph with even number of edges and $2n$ vertices of odd degree, and the edges is an edge-disjoint union of trails, it is possible to successively concatenate trails until we are left with $n$ trails all starting and ending in odd degree vertices plus any number of circular trails.
(3) We can merge the circular trails with the $n$ linear trails so as to end up with only $n$ trails.
The reason $n\ge1$ is required is that for $n=0$, i.e. all vertices have even degree, step (3) will end with a single circular trail (an Euler path) with no linear trail to merge it to.
1: Splitting $G$ into 2-trails
Proof goes by induction (or descent): i.e. I reduce the graph to one or more graphs with a smaller number of edges.
Pick a vertex, $x$ of degree 2 or higher: one must exist, or $G$ would have two vertices and one edge only. Decompose $G$ into components $G_1,\ldots,G_k$ which correspond to the connected components after removing $x$ from $G$, but with the vertec $x$ and edges between $x$ and vertices of each $G_i$ included in $G_i$: i.e. two vertices are in the same component if the can be connected by a path not passing through $x$. Each edge of $G$ is then in exactly one of the $G_i$.
If there is only one component, we can pick any two edges at $x$, say $xy$ and $xz$ for vertices $y$ and $z$, form the 2-trail $yxz$ and subsequently remove these two from the graph. If this leaves $x$ with degree zero, we also remove $x$. The remaining graph is still connected and with even number of edges.
If all components have even number of edges, each of these have a smaller number of edges and so follow from the induction hypothesis.
If there are components with an odd number of edges, there must be an even number of these. Take any two of these, pick one edge $xy$ to one of them and one edge $xz$ to the other, form the 2-trail $yxz$ as before, then remove these two edges (and $x$ if left with degree 0). The two selected components may (or may not) get disconnected from the rest of the graph after removing these edges, but each connected component of $G$ after removing $yxz$ will have even number of edges and so be handled by the induction hypothesis.
This procedure (by induction or used iteratively) will reduce $G$ to a disjoint union of trails of length 2.
2: Join 2-paths into maximal paths
If at a vertex $x$ there are two trails that start/end there, join these two trails together. Do this iteratively until no more such cases exist. The only place trails can start/end will be at vertices of odd degree; conversely, at each vertex of odd degree, there must be exactly one trail starting/ending. Hence, we are left with $n$ trails starting/ending in the $2n$ vertices of odd degree, plus any number of circular trails.
Since we start with 2-trails, and the joining of two even length trails remain even, all trails (linear and circular) are of even length.
3: Merge circular trails with linear trails
Take any circular trail, $\omega$, from the set. There must be a vertex $x$ in $\omega$ through which another trail from the set passes which we denote $\gamma$: if not, $\omega$ must contain an entire connected component of $G$. Merge $\gamma$ and $\omega$ together at $x$ into a new trail, also of even length since both $\omega$ and $\gamma$ were. If $\gamma$ is linear, the merged trail is linear; if $\gamma$ is circular, the merged trail is circular. But in either case, the number of circular trails in the set is reduced by 1.
We repeate this step until there are no circular trails left. This requires $n>0$, otherwise we will be left with a single circular Euler path spanning the entire graph which we cannot get rid of.
Q.E.D.
Best Answer
Your question is about two decision problems. Let me start with stating these two problems explicitly. One is the usual 3-colorability:
3-colorability
Instance: A graph G=(V,E).
Question: Is G 3-colorable?
and the other is the following problem. Because there is no standard name for the second problem, I just call it Problem X for the purpose of this answer.
Problem X
Instance: A graph G=(V,E).
Question: Is there an edge e∈E such that G−e is 3-colorable?
Suppose that we have the ability to solve Problem X and that we want to know whether a given graph G=(V,E) is 3-colorable or not. Let G′=G+K4 be the vertex-disjoint union of G and the complete graph on four vertices, and query the answer to Problem X on G′. It is not hard to prove that the answer to Problem X on G′ is yes if and only if G is 3-colorable; the proof is left as an exercise.
In complexity theory, what you are asking for is called a reduction from 3-colorability to Problem X.