Why an edge does not belong to three faces?

Question

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.

Answer 1

Everything you're saying and asking is very natural, and it is pretty pathetic that not more people ask these questions and acknowledge that this kind of graph theory can be very very unrigorous if not done correctly. In fact, I was turned off from graph theory initially because so many people thought all this planar graph stuff was automatically rigorous and obvious when it is most certainly not. With that said, and probably part of the reason so many people are brainwashed, it takes time to develop the topological prerequisites and is not fun for most; in particular, you can't expect to learn the answers to the questions you ask just by an answer here. I think the best "answer" to your question then is a reference. I think you should look at chapter $4$ of "Graph Theory" by "Reinhard Diestel" for a start.

Answer 2

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.

Answer 3

This is a question about definitions and exact prerequisites. It might look like you can state and use these theorems with just a bit of graph theory and ignoring the underlying topology and geometry but then you run into problems like this.

Euler's formula holds for graphs that are embedded on a surface. This is part of the theorem statement and without that prerequisite it just doesn't hold. A surface could be defined here as a $2$-dimensional manifold, which means every point has an open neighbourhood that is diffeomorphic to $\mathbb{R}^2$.

Now lets call the tetrahedron plus extra vertex and the faces you defined $T$, then we can ask:

Does there exist an embedding $\psi: T \rightarrow S$ to some surface $S$?

This is a perfectly reasonable question and the answer is no, but this can't be proved using graph theory but requires geometry/ topology to prove.

Pick a point $x$ on an edge where $3$ faces meet and let $U$ be a small neighbourhood of this point. Let $L$ be the part of the edge that $x$ lies on that is inside of $U$. Then $U \setminus L$ has $3$ connected components. Suppose there is a manifold chart $\varphi: U \rightarrow \mathbb{R}^2$. As $L$ is a line segment, $\mathbb{R}^2 \setminus \varphi(L)$ has at most $2$ connected components by the Jordan curve theorem. This is a contradiction.

Answer 4

There have been so many good answers to this questions. I'm just adding my understanding and hopefully it helps.

1 (Nice fact) Any graph can be embedded into $\mathbb{R}^3$.

A tetrahedron in $\mathbb{R}^3$ has three 'faces' adjacent to it, the two on the tetrahedron, and the 'infinite' face. Does that answer your question? This is due to the fact that we are in $\mathbb{R}^3$.

2. (Another nice fact) Any surface is locally homeomorphic to $\mathbb{R}^2$.

However, what we are interested in are embedding onto surfaces.

In an embedding, faces do not intersect. Now, laying an edge on a plane, there's clearly a left or a right to it. If there's a face to the left and to the right of the edge, you cannot add another without intersecting any of the two faces, since it is locally homeomorphic to $\mathbb{R}^2$.