Let $G=(V, E)$ be a connected graph such that $r=m−n+2$, where $r$ is the number of regions, $m$ is the number of edges and $n$ is the number of vertices.
Does there exist a graph embedding of a nonplanar graph that satisfies $r=m-n+2$?
We define a region of a graph embedding as an area enclosed by edges and the infinite region.
Does such a graph embedding exist, and if not how can we prove that for all graph embeddings satisfying Euler's formula, the graph must be planar.
Best Answer
When dealing with plane embeddings, there are often a ton of technical details that you need to be careful of. To make matters simpler, let me only consider straight line embeddings of graphs. I will allow edges to intersect, but only at interior points and not vertices (apart from edges that share a vertex, of course), and at any point other then a vertex at most two edges intersect. In this setting it seems relatively clear what a region is: you delete the image of the vertices and edges from $\mathbb{R}^2$ and look at the connected components.
I claim that in this setting, an embedding satisfies Euler's formula if and only if it is without crossings; that is, if it is an honest planar embedding of the graph. Indeed, if the embedding has crossings, then start putting new vertices at each crossing, so that the new vertex subdivides the two crossing edges. With each new vertex, the number of vertices increases by one, the number of edges increases by two, and the number of regions does not change. Keep doing this, and you will get the planar embedding of a graph with $n+c$ vertices and $m+2c$ edges, where $c$ is the number of crossings in the initial embedding. Euler's formula now tells you that the number of regions is $m-n + 2 + c$. Since the number of regions did not change, this is also true for the original embedding.
Since for a non-planar graph every embedding will have crossings, this shows that none of the embeddings satisfies Euler's formula.