On the sphere, faces, vertices, and edges obey the relationship: v-e+f = 2. (This assumes the graph is connected.) This can be proved by induction on the number of edges and vertices in the graph. The degenerate graph (one point) has one vertex, no edges, and one face. Given a larger graph, search for an endpoint. If one exists remove it and its associated edge, leaving v-e+f unchanged. If a vertex has degree two, remove it and connect the incident edges, leaving v-e+f unchanged. If an edge is part of a cycle, remove that edge and combine the two incident faces, leaving v-e+f unchanged. Since the edge was part of a cycle, the areas on either side were indeed separate faces. If there is no edge that is part of a cycle then we have a tree, with end points, and we can remove those.
The formula still holds even if multiple edges and loops are allowed.
If we ignore the "exterior", a planar graph obeys the relationship v-e+f = 1. When mapped to the sphere, the exterior becomes the face with the singularity. Bring this face back in and we have v-e+f = 2.
Unlike singularities, changing the genus affects Euler's formula. Add some "handles" to the sphere, and assume the graph uses all the handles. In other words, each face of the graph is simply connected. Deconstruct the graph as before. Most changes do not affect v-e+f. At some point a line is removed that has the same face on either side of it. This face wraps around one of the handles. Remove the edge and paint this face red. The red ring cannot shrink to a point; the face is no longer simply connected. With one edge removed, v-e+f has increased by 1. Continue to remove points and edges from this handle, and eventually another edge has the same face on either side. Remove the edge and paint this face red. These two red rings are essentially perpendicular. One runs around the inside of the handle and the other wraps around the cross-section of the handle. The same thing happens to all the other handles, leaving a shape (without the red rings) that is equivalent to a sphere with g singularities (holes). At this point v-e+f = 2. If there were g handles, a genus of g, the original graph satisfies v-e+f = 2-2g.
Euler's formula places restrictions on the average degree of a vertex. Let the average degree be d, hence dv = 2e. Let the average face have r edges, hence rf = 2e. Rewrite Euler's formula as follows.
2e/d - e + 2e/r = 2
We know that r is at least 3, so replace r with 3 and write the following.
2e/d - e + 2e/3 ≥ 2
2e/d - e/3 ≥ 2
Remember that dv = 2e and continue to simplify.
v - dv/6 ≥ 2
d ≤ (6v-12)/v
On the sphere, 4 vertices implies an average degree 3 (tetrahedron), 6 implies 4 (octahedron), 12 implies 5 (icosahedron), and the asymtotic limit is 6. If you try to draw 6 edges at each point, you wind up tiling the plane with equilateral triangles. That's fine for an infinite graph, but as soon as you make the graph finite, some vertex somewhere has a degree less than 6.