Converse of Euler's theorem (Graph theory)

Question

Euler's theorem states that If $G$ is a connected, planar graph whose edges do not intersect other than at vertices, and $v$ is the number of vertices, $e$ is the number of edges and $f$ is the number of faces, then

$$v-e+f=2$$

But my question is whether the converse holds.I mean to say,If G is a connected graph with the symbols having usual meaning and $v-e+f=2$ then does it imply $G$ is planar? I have tried to find counterexamples but have not yet obtained one.

Answer 1

Notably, $G$ may also be drawn on any topological sphere and the formula will hold good. Classic examples include the regular convex or "Platonic" polyhedra, in fact all convex polyhedra. For some insights into this understanding, see Branko Grünbaum; "Graphs of polyhedra; polyhedra as graphs", Discrete Mathematics, Volume 307, Issue 3-5, February 2007. pp. 445–463.

The inverse does not apply for other surface topologies - which is, indeed, the origin of topology. For a fuller introduction to Euler's insight and its subsequent generalizations, I would recommend David S. Richeson; Euler's Gem: The Polyhedron Formula and the Birth of Topology, Princeton University Press, 2008.

Nevertheless any sufficiently small part of a smooth two-dimensional surface (2-manifold) may be regarded as planar, which is usually described as being locally Euclidean. In general the inverse applies to (i.e. $G$ may be drawn on) any such local area of a 2-manifold.

Answer 2

The definition of faces (and thus the ability to count them) is based on a specific planar embedding. So asking how many faces an arbitrary graph has is sort of like asking if an arbitrary real number is prime.

The definition of faces is slightly roundabout. A rigorous definition might say that a plane graph has a certain number of faces based on its specific topology. From there, you would need to note that every planar embedding of a planar graph has the same number of faces, so only in that context does it make sense to take about the number of faces in a planar graph.

To give an example (which also helps to reinforce that not all graphs are not intrinsically points on paper connected by lines), let us consider a simple graph where the vertices are all of the four letter English words and two words are connected if they share exactly three letters in the same position. (For instance, CRAB would be adjacent to DRAB, CRIB, and CRAM, along with other words.) How many faces does that graph have? The question doesn't really make sense, especially considering that the graph is almost certainly not planar (although it would be an interesting exercise to prove that in this case).