Let $T$ be a spanning tree in a connected plane graph $G$. Let $G^*$ be the dual graph corresponding to an embedding of $G$ in the plane, and let $T^*$ be the subgraph of $G^*$ consisting of the edges of $G^*$ that correspond to the edges of $G$ not in $T$. We want to prove $T^*$ is a spanning tree of $G^*$.
First note that $T$ has $|V(G)|-1$ edges, so $T^*$ has $|E(G)|-(|V(G)|-1)$ edges. By Euler's formula, there are exactly $2 - |V(G)| + |E(G)|$ faces in the embedding of $G$, so $|V(G^*)| = 2 - |V(G)| + |E(G)|$, and we have that $|E(T^*)| = |V(G^*)|-1$. It remains to show that $T^*$ is acyclic, since an acyclic subgraph of a graph with 1 fewer edge than the number of vertices in the graph is a spanning tree.
Now suppose $T^*$ has a cycle $C$. Note that $C$ separates the embedding of $G^*$ into two connected pieces, each of which contains at least one face of the embedding. But then the faces of $G^*$ correspond to vertices of $G$, and the edges of $C$ must correspond to an edge cut of $G$. But $T$ does not contain any of the edges in that edge cut, so $T$ cannot be a spanning tree, a contradiction.
Thus $T^*$ is acylic and $|E(T^*)| = |V(G^*)|-1$, and $T^*$ is a spanning tree in $G^*$.
You might want to look into matroid theory. These notions are quite a bit easier to understand in that light. A spanning tree of a graph is a basis in the cycle matroid $M$ for the graph. The complement of basis is a basis in the dual matroid. In other words, the complement of a spanning tree in a planar graph is a spanning tree in the dual graph.
The graph $K_{1,n}$ is planar for all $n$ since it's just a star graph.
The graph $K_{2,n}$ is planar for all $n$. To see this, draw $n$ vertices in a straight line in the plane, and draw two more vertices, one on each side of the line, and connect these two vertices to each vertex on the line.
Every other case deals with $K_{n,m}$ where $n,m\geq 3$. But then this graph must have $K_{3,3}$ as a minor so it is nonplanar by Wagner's theorem. Or it's nonplanar by Kuratowski's theorem if you'd rather say "subgraph" instead of "minor".
Best Answer
So $G$ is planar and eulerian. We must prove $G'$ is bipartite. Asume $G'$ is not bipartite. Now I want you to forget about the fact that $G'$ is the dual of $G$. Just think of $G'$ as a normal graph in which the vertices of $G'$ are drawn as vertices and not as the faces of $G$.
Since $G'$ is not bipartite it has an odd cycle, one of the faces inside that odd cycle must therefore have an odd number of edges. That face is a vertex of odd degree in $G''$,so $G''$ is not eulerian. Now,$G\cong G''$ so $G$ is not eulerian, a contradiction. The contradiction comes from assuming $G'$ is not bipartite.
A key step is the fact $G\cong G''$.