Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 8] GRAPH THEORY 193

8.52. Then-cycle, denoted byCn, is the graph which consists of only a single cycle of lengthn. Figure 8-60(c)shows the

6-cycleC 6. (a) Find the number of vertices and edges inCn. (b) Find the diameter ofCn.

8.53. Describe those connected graphs which are both bipartite and regular.

TREES

8.54. Draw all trees with five or fewer vertices.

8.55. Find the number of trees with seven vertices.

8.56. Find the number of spanning trees in Fig. 8-61(a).

8.57. Find the weight of a minimum spanning tree in Fig. 8-61(b)

Fig. 8-61

8.58. Show that any tree is a bipartite graph.

8.59. Which complete bipartite graphsKm,nare trees.

PLANAR GRAPHS, MAPS, COLORINGS

8.60. Draw a planar representation of each graphGin Fig. 8-62, if possible; otherwise show that it has a subgraph homeo-

morphic toK 5 orK 3 , 3.

Fig. 8-62

8.61. Show that the 3-cubeQ 3 (Fig. 8-60(b)) is planar.

8.62. For the map in Fig. 8-63, find the degree of each region and verify that the sum of the degrees of the regions is equal

to twice the number of edges.

8.63. Count the numberVof vertices, the numberEof edges, and the numberRof regions of each of the maps in Fig. 8-64,

and verify Euler’s formula.