I'm reading Richard J. Trudeau's book "Introduction to Graph Theory", it discussed genus, so there is not only a flat plan (i.e. $S_0$), but also surfaces "with handles" such as $S_1$ (donut), $S_2$ (eyeglasses, without the glass), $S_3$ (pretzel) etc… But wherever it is, for example, on a $S_3$ pretzel, an edge can only belong to 2 faces.
But why?
Take a tetrahedron $ABCD$ with 4 vertices, 6 edges and 4 faces, can I add the centre of the tetrahedron $E$, and add edges connecting it to the original 4 vertices, ie, $AE$, $BE$, $CE$ and $DE$, then say that edge $AE$ belongs to 3 faces, namely $ABE$, $ACE$, and $ADE$?
This is a bit weird, e.g. now we have 5 vertices, 10 edges, and 10 faces, Eurler's formula $$V+F-E=2-2g$$
won't hold unless $$g=-1.5$$
. But what prevent us announcing this is a valid graph?
If in geometry I asked, "why from a point outside of a line, only 1 parallel line can be drawn?" The answer could be :"Parallel postulate, this is one of some basic assumptions in geometry, that we didn't specifically mention, but actually required."
So here in Graph theory I have a similar doubt, is there some postulation / assumption/ maxiom in Graph theory (or topology) that I don't know, but actually ensures 1 edge could only belongs to 2 faces?
For example, is it because that face $ABE$ and $ACE$ can glue up together, and at every point its local region could be mapped to a circle in $R^2$, but adding one more face $ADE$ will break this?
Or is this a limitation to $R^3$ where we talk about $S_n$ and faces?
Please enlighten me.
Best Answer
Planar graphs are a mix of graph theory and topology. The fact that an edge in a plane graph divides exactly two regions of the plane is the topological part of it.
If you're not interested into getting into the topological details, you are in good company in graph theory! The single important detail is the Jordan curve theorem, which says that every cycle in a graph in the plane divides the plane into an "inside" and "outside" region that can only be crossed by crossing the cycle itself. JCT is what gives us the authority to say that removing an edge merges the faces "on either side of the edge" into a single face, and leads to all of the nice formulas about planar graphs.