198 GRAPH THEORY [CHAP. 8
8.55. 10
8.56. 15
8.57. 1 + 1 + 1 + 1 + 1 + 2 + 2 + 3 =12.
8.59. m=1.
8.60. Only (a) is nonplanar, andK 3 , 3 is a subgraph.
8.61. Figure 8-70(a)is a planar representation ofQ3.
8.62. The outside region has degree 8, and the other two regions have degree 5.
8.63. (a) 5, 8, 5; (b) 12, 17, 7; (c) 3, 6, 5; (d) 7, 12, 7.
8.64. (a) 3; (b) 3; (c) 2; (d)3.
8.65. See Fig. 8-72.
Fig. 8-728.66. (a)n=3; (b)n=4.
8.67. (a)
⎡
⎢
⎢
⎣0101
1011
0101
1110⎤
⎥
⎥⎦; (b)⎡
⎢
⎢⎣0120
1011
2100
0100⎤
⎥
⎥⎦; (c)⎡
⎢
⎢⎣1110
1002
1000
0200⎤
⎥
⎥⎦8.68.See Fig. 8-73.
8.69.LetMandNbe the two disjoint sets of vertices determining the bipartite graphG. Order the vertioes inMfirst and
then those inN.
8.70. (a) B,F,A,D,E,C.
(b) G=[A:B;B:A, C, D, E;C:F;D:B;E:B;F:C].