d ≤ (6v-12+12g) / v
For large v, the average degree approaches 6, no matter the value of g. We can always find a vertex with 6 edges or fewer. However, intermediate values of v and g may support a larger average connectivity.
On the torus, when g = 1, the average degree is always 6 or less. If x has degree 6, we can assign it the 7th color, hence all graphs on the torus are 7-colorable. This is the 7 color theorem.
Planets aren't usually shaped like doughnuts, and it's hard to picture a map of countries that requires 7 colors, but one exists, and we'll try to describe it below.
Place vertex A in the center of the middle square, place B C and D in the squares running down the left column, and place E F and G in the squares running down the right column. Thus we have the following table of locations, where each vertex is in the center of one of the nine squares.
A middle square B upper left C middle left D lower left E upper right F middle right G lower right
Directly connect A to the other 6 vertices, with no "wrap-arounds". Thus A has degree 6, and we are done with A.
Connect B to C to D to B, going straight down the left column. Of course the connection from D to B wraps around the torus; leaving the board at the bottom and reappearing at the top. In the same fashion, connect E to F to G to E, going straight down the right column. If we can draw a K3,3 from BCD to EFG, without crossing any preexisting lines, we're done.
Directly connect B to E and D to G, with horizontal lines. Then connect B to G using a wrap-around line with slope ½.
Six connections to go. These all leave the right side of the board and reappear on the left.
Connect F to C B and D, using lines with slopes 0 1 and 2 respectively.
Connect E to D and C, using lines with slopes 1 and 2 respectively.
Finally connect G to C, with a line of slope 1. That completes (pun) K7 on the torus.
As an immediate corollary, K3,3, another non-planar graph, can be drawn on the torus. Similarly for K3,4, a subgraph of K7.
It's not immediately obvious, but you can draw K4,4 without too much difficulty. Arrange the vertices in two columns of 4 and sew the sides of the containing rectangle together, as we did before. Draw four direct connections, joining each vertex to its neighbor at the same level. Then draw four "inside" connections with slope 1, joining the vertices on the left to the (next up) vertices on the right. That's 8 out of 16 connections.
Start at the right column and draw wrap-around lines with an upward slope. These leave the right edge, reenter at the left, and connect with the vertices one unit up. Four more upward sloping wrap-around lines connect the vertices with their counterparts 2 units up.
I don't know about higher bipartite graphs on the torus.
d ≤ (6v-12+12g) / v
Graphs don't get very interesting until v goes beyond 6. Get rid of the -12; that can only make the average degree higher. Thus d is bounded below 6+2g. Some vertex has degree 5+2g or less. Every graph embedded in a surface of genus g is thus 5+2g colorable. The sphere is 5-colorable and the torus is 7-colorable etc.
We showed that K7 can be drawn on the torus, hence every map (in the torus) is 7-colorable, and there exists a map that requires 7 colors. In fact, there exists a map requiring 5+2g colors for all values of g beyond 0. In other words, the formula 5+2g is precise. (We won't prove this here.)
On the sphere (or plane), 4 colors are sufficient. This is the four color theorem, and it is very difficult to prove. In fact the proof involves a computer program that examines thousands of cases. If you can think of a simpler proof, you've earned your Ph.D!