Why can't a 4-regular graph be both planar AND bipartite. I thought I was smarter than a man who held a doctorate in graph theory. I attempted to prove that it is possible for a $4$ regular graph $(k4 4)$ to be both bipartite and planar. I used a formula $m \leq 3n-6$ where $m$ is the amount of edges and $n$ is the amount of vertices. I was corrected by email. 
Can someone help me, why can't a $4$-regular graph be both bipartite and planar?
 A: The relation $m \le 3n - 6$ holds for all connected non-trivial planar graphs. However if you know how to prove it, you can deduce more strong relation for non-trivial planar bipartite graph: $m \le 2n - 4$. If immediately implies that such graph can't be $4$-regular.
A: First of all, the formula $m \le 3n-6$ can't possibly be used to prove a claim like yours. It's a property that all planar graphs must satisfy, so if you proved that a $4$-regular bipartite graph didn't satisfy it, you would know that no $4$-regular bipartite graph can be planar. But not all graphs that satisfy $m \le 3n-6$ are planar: a counterexample is the Petersen graph (image below, thanks to Wikipedia).

So even if all $4$-regular bipartite graphs satisfy this inequality, it's still possible that none of them are planar for some different reason.
In fact, such a reason does exist. In any planar embedding of a $4$-regular bipartite graph with $m$ edges, $n$, vertices, and $f$ faces, each face must have at least $4$ sides (since a bipartite graphs contains no triangles). We have:

*

*$n - m + f = 2$: by Euler's formula.

*$4n = 2m$: counting the edges out of each vertex, we count each edge twice.

*$4f \le 2m$: counting the at-least-four edges around each face, we count each edge twice.

So we have
$$4(2-n+m) \le 2m \implies 4n - 2m \ge 8 \implies 0 \ge 8$$ which is a contradiction.
A: I am no expert in graph theory, but I imagine you can assume without loss of generality that such a graph is connected, and show that there must be a subdivision of $K_{3,3}$ in a 4-regular bipartite graph. I don't have the background to prove this myself, but this seems like a sensible approach.
A: A planar graph represents the net of a polyhedron. A bipartite graph has only even cycles, so the smallest number of edges on any face would be $4$. A $4$-regular graph would have four faces meeting at each vertex. This can only be used as a tiling of the infinite plane, not of a sphere/finite planar graph.
So if you allow an infinite 4-regular graph, the tiling of squares as a chessboard, you could arguably be correct, but not for any finite graph.
