Graph Theory Lessons

Lesson 21: Planar Graphs

We have already talked about planar graphs in previous exercises (graphs that can be drawn so that no edges cross). Get the graph of the tetrahedron (use the plane version) and get its line graph (figure 34). Save it as graph 1 (we shall use it again later).

Fig. 34, Line graph of a tetrahedron.

It does not look planar but if we move the vertices around using the editor we can get the plane depiction in as in figure 35

Fig. 35, Plane depiction of the line graph of a tetrahedron.

Notice that the graph breaks up the plane into 8 regions (the outside counts as a region). You can get the program to count regions of plane graphs for you by clicking Properties, then Planar Graphs and then Count Regions. We have many examples of planar graphs. Get the circuit graph C₅ and count the regions, edges and vertices. You should get 2 regions, 5 edges and 5 vertices. In general C_n has 2 regions, n edges and n vertices.

How many edges, vertices and regions does the wheel W_n have?

Find the number of edges, vertices and regions for each of the platonic graphs (use the planar depictions).

Find the number of edges, vertices and regions in the star S_n. (The program cannot handle this one so you will have to figure it out for yourself!)

Find the number of edges, vertices and regions for the rectangular grid sq_m,n.

Find the number of edges, vertices and regions for the triangular grid Tri_n.

Summarize your answers to the questions above in a table:

Graph	Edges	Vertices	Regions
C_n	n	n	2
W_n	.	.	.
tetrahedron	.	.	.
cube	.	.	.
octahedron	.	.	.
icosahedron	.	.	.
dodecahedron	.	.	.
S_n	.	.	.
Sq_m,n	.	.	.
Tri_n	.	.	.

If a plane graph has e edges, v vertices and r regions, what do you think the relationship is between e and v+r?

Many times a planar graph has more than one plane depiction. Get the complete graph K₃ and then Prism(K₃). (See figure 25). One planar depiction of this graph is given below. Draw another planar depiction of Prism(K₃). [Hint: try to put four vertices on the outside boundary.]

Fig. 36, A Plane depiction of the prism of K₃

The Four Color Theorem: The chromatic number of a planar graph is no greater than four. This was posed as a conjecture in the 1850s and although many attempts were made to prove it was only finally proved in 1976 by K. Appel and W. Haken. The proof involves a careful analysis of 2000 different cases and was done using more than 1000 hours of computer time.

Answers

e-mail: C. Mawata