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

Question

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?

Answer 1

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.

Answer 2

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$.

Answer 3

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!