Graph Theory Lessons

Answers to Lesson 21

Problems 1 to 6:

Graph	Edges	Vertices	Regions
C_n	`n`	`n`	`2`
`W_n`	`2n - 2`	`n`	`n`
Tetrahedron	`6`	`4`	4
Cube	`12`	`8`	`6`
Octahedron	`12`	`6`	`8`
Icosahedron	`30`	`12`	`20`
Dodecahedron	`30`	`20`	`12`
`S_n`	`n - 1`	`n`	`1`
`Sq_m,n`	`2mn - n - m`	`mn`	`mn - m - n + 2`
`Tri_n`	`3n(n - 1)/2`	`n(n + 1)/2`	`(n - 1)²+1`

You found the number of edges in Sq_m,n in lesson 19. The number of regions is
(m - 1)(n - 1)=mn - n - m + 1. If you count the outside region you get mn - n - m + 2.

The number of vertices in Tri_n is

1 + 2 + 3 + ... + n = n(n+1)/2. The number of regions in Tri_n is the sum of the first n - 1 odd numbers, i.e. 1 + 3 + 5 + ... + (2n- 3)=(n - 1)². Add on the outside region to get (n-1)²+1. By counting the number of vertices of degree 2, 4, and 6 in Tri_n you can get the sum of the degrees and hence the number of edges.

The relationship between e, v, and r is e = v + r - 2.

Another planar depiction of Prism(K₃).

e-mail: C. Mawata