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

CHAP. 8] GRAPH THEORY 197

8.45. (a)ABCDEA; (b)ABCDEF A; (c) none, sinceBorDmust be visited twice in any closed path including all vertices.

8.46. ( 5 − 1 )!/ 2 =12.

8.47. Hint: Adding a vertex by dividing an edge does not change the degree of the original vertices and simply adds a vertex
of even degree.

8.48. (a) The two 3-regular graphs in Fig. 8-70 are not isomorphic: (b) has a 5-cycle, but (a) does not. (b) There are none.
The sum of the degrees of anr-regular graph withsvertices equalsrs, andrsmust be even.

Fig. 8-70

8.49. (a) diam(K 1 )=0; all others have diameter 1; (b)m=C(n, 2 )=n(n− 1 )/2; (c)n−1; (d) (i)n=2 andnodd;
(ii) alln.

8.50. (a) diam(K 1 , 1 )=1; all others have diameter 2; (b)E=mn; (c)K 1 , 1 ,K 1 , 2 , and allKm,nwheremandnare even;
(d) none are isomorphic; onlyK 1 , 1 andK 1 , 2 are homeomorphic.

8.51. (a)n; (b)n 2 n−^1 ; (c)n; (d)n=1, even; (e) consider the 4×16 matrix:

M=

⎡

⎢

⎢⎣

0110011001100110

0011110000111100

0000111111110000

0000000011111111

⎤

⎥

⎥⎦

which shows howQ 4 (the columns ofM) is obtained fromQ 3. That is, the upper left 3×8 submatrix ofMisQ 3 ,

the upper right 3×8 submatrix ofMisQ 3 written in reverse, and the last row consists of eight 0s followed by

eight 1s.

8.52. (a)nandn; (b)n/2 whennis even,(n+ 1 )/2 whennis odd.

8.53. Km,mis bipartite andm-regular. Also, beginning withKm,m, deletemdisjoint edges to obtain a bipartite graph which is
(m− 1 )-regular, delete anothermdisjoint edges to obtain a bipartite graph which is(m− 2 )-regular, and so on. These
graphs may be disconnected, but their connected components have the desired properties.

8.54. There are eight such trees, as shown in Fig. 8-71. The graph with one vertex and no edges is called thetrivial tree.

Fig. 8-71