# Every planar graph can be embedded on a sphere - formal proof?

The proof of the following theorem:

A graph can be embedded on the surface of a sphere without crossings if and only if it can be embedded in the plane without crossings.

is very short-

The plane is topologically a sphere with a missing point at the North pole.

Now, before I start: I do believe this theorem is true. My goal was to do some reflection on why I believe it's true. It's a good practice, we should always ourselves 'what makes me believe it?' and 'should I believe it?'. Similarly, we should ask: how much abstract thinking and intuition is allowed in mathematics? What if we reach wrong conclusions by using too much intuition to prove theorems - if so, where is the boundary? We take certain statements as axioms, use logical thinking and derive conclusions which we call theorems. And so on. This is the only proper way of doing mathematics.

Why should I consider this as a convincing argument? Topology is just a purely mathematical construct. Here, we have a real-world problem and want to solve it using the formal methods of mathematics. I don't trust simplified proofs based on intuition - what if I'm being fooled into thinking this is true for every planar graph? Even if the smartest person in the world "believed it", there may still exist a counterexample.

A proof is valid if it shows that, in this example, there doesn't exist a planar graph that cannot be drawn on a sphere.

Can we make it a bit more precise and formal? I believe the first step is to state the define the theorem in formal terms.

1. How to define edges drawn on a sphere, their intersections?
2. What allows us to model this problem in topological terms?
3. Why homeomorphism is believed to guarantee that if there are no intersections in topological space of the plane, then there aren't in topological space of the sphere without a point? Should we believe it?

What I'm concerned about is the transition from natural description of the problem to topological, formal one. We solve the problem in the domain of topology and assume that the problem stated in topological terms is equivalent to the original problem. In other words, we are assuming that topological formulation of the problem is equivalent to the original problem - this assumption is based on intuition!. If not, what axioms or theorems (which is what maths is made of) tell us we can do that - e.g. make a topological space out of a graph, solve the problem in topology domain, and come back to our graph-theory domain?

• What part of this strikes you as a 'real world problem'? Literally every meaning-carrying word in your initial theorem - 'graph', 'embedded', 'surface', 'sphere', 'crossing', and 'plane' - has a formal definition and meaning. If you're concerned about the transition away from the 'natural description' of the problem, that process has started and arguably completed well before this post even starts. – Steven Stadnicki Feb 25 '15 at 5:55
• (Also, one-character edits without content to bump your question back to the top of the site are generally frowned upon.) – Steven Stadnicki Feb 25 '15 at 5:58
• If I didn't do that, everyone has only a few minutes to notice my question. Nobody cares what's on page 2, 10, 100. Anyway, would you be so kind and comment the discussion between me and Mike Miller below? My major concern is why it's believed that topological graph theory correcly models the problem. – user216094 Feb 25 '15 at 20:38
• Look at it from the philosophical point of view. Now, is it a complete nonsense? If yes, why? – user216094 Mar 7 '15 at 22:46

Hint: Look up stereographic projection (e.g. wikipedia), and check to see that this carries non-overlapping edges in the plane to non-overlapping edges on the sphere, and vice versa, and also carries the shared endpoints of edges in the plane to shared endpoints of edges on the sphere and vice versa.

One can make a topological space out of a graph; then "drawing a graph on a surface without crossings" is the same thing as a topological embedding $G \to \Sigma$, where $\Sigma$ is the surface. Everything else relies on this - and this is the answer to your first two questions - so you should convince yourself of this.

Then if you have an embedding $G \to \Bbb R^2$, you can embed compose with the embedding $\Bbb R^2 \hookrightarrow S^2$ to get an embedding $G \to S^2$; and if $G \to S^2$ is an embedding, there has to be some point it misses (if your graph is finite, this is because injective maps from compact spaces to Hausdorff spaces are homeomorphisms onto their image; if the image was all of $S^2$, your graph would be homeomorphic to $S^2$, which it's not.), so compose with the stereographic projection $S^2 \setminus \{p\} \to \Bbb R^2$ to get an embedding $G \hookrightarrow \Bbb R^2$.

So $G$ embeds into $\Bbb R^2$ if and only if it embeds into $S^2$.

• What I'm concerned about is the transition from natural description of the problem to topological, formal one. We solve the problem in the domain of topology and assume that the problem stated in topological terms is equivalent to the original problem. In other words, we are assuming that topological formulation of the problem is equivalent to the original problem - this assumption is based on intuition!!!. If not, what axioms or theorems (which is what maths is made of) tell you we can do that - e.g. make a topological space out of a graph, solve the problem in topology domain, and come back? – user216094 Feb 24 '15 at 15:39
• @user216094 The original problem is not a mathematical statement - it is meaningless to talk about drawing a graph on a surface without crossings without defining what that means. So part of the problem becomes to actually appropriately define the problem - the first paragraph says "convince yourself" instead of "prove". If you can successfully define what the problem should mean, you should be able to translate it topologically. (That you can make a topological space out of a graph is a construction, not a theorem.) – user98602 Feb 24 '15 at 15:58
• So we don't know if our problem can be modelled accurately in topology, because it has been stated in informal terms. Then, intuition is telling us what it should mean in mathematical terms. We only assume it's correct. What if I found a counterexample convincing you it's not a correct formalization of the problem? You cannot guarantee I can't do that. – user216094 Feb 24 '15 at 18:06
• I cannot convince myself of this mathematical statement's validity, because I don't know if I should. Suppose I gave you a slightly modified, wrong, model of the problem, but the fact that it's wrong would be hard to discover (you would be 100% sure it's a wrong model once I'd showed you its flaw). But at first, you would be convinced the mathematical model is perfectly correct... – user216094 Feb 24 '15 at 18:48

Place your hand out flat on the table. Now imagine a new 'thing' that is connected to all of your fingertips (including your thumb). When you contract that 'thing' down to a single point, it pulls your fingertips together. Now what effect does this have on the shape of your whole hand? And what would happen to a graph drawn on the back of your hand (including along the back of your fingers) when you did so?

Now imagine you had infinitely many fingertips on fingers with zero length - so your fingertips are simply the points at the edge of your hand. And imagine what would happen to your hand if you tried the same trick as with your real hand.

This is the same thing done with the embeddings. First you define the graph embedding on the plane. Then you take a point at infinity, which is connected to all infinite points, and collapse it to induce curvature in the surface. Then smooth out the curvature and voila, the sphere! To reverse the process, you simply remove the point at infinity (the 'north pole' point you mentioned) and expand all its connected points to give the boundary. Then reduce the curvature until you have the flat surface back, and voila, the plane!