离散数学及其应用英文版第五版

36. They are not isomorphic .Because the graph in the right hand side has a vertex of degree 4,but the graph in the left hand side has no vertex of degree 4.It follows that they are not isomorphic.

SECTION 8．6

2．The shortest path between a and z is a , b , e , d , z , with length 7

SECTION 8.7

12.

Because there are 8 vertices, each of degree three, the sum of the degrees of the vertices is 24. Then we can conclude that there are 12 edges in the graph by the handshaking theorem.

And since it is a connected planar graph , we know that the number of the regions is 12-8+2 = 6 by EULER’S FORMULA.

25.(图我不画出来了)

The subgraph H of this graph obtained by deleting the edges {a,e},{b,f},{c,e},{d,f},{e,g},{f,g}. H is homeomorphic to K5,with vertices a, b, c, d, g, since it can be obtained by a sequence of elementary subdivisions , adding the vertices e, f .

SECTION 8.8

14.

from the map we can find it containing W5,so we know that we can not use three colors to color the map. And by THE FOUR COLOR THEOREM , we know that the chromic number of planar graph is no greater than four. So we know the least number of colors needed to color the map is 4.

18.(图我不画了)

The answer is three.