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

180 GRAPH THEORY [CHAP. 8

8.5. Consider the graphGin Fig. 8-36(b). Find the subgraphs obtained when each vertex is deleted. DoesG

have any cut points?

When we delete a vertex fromG, we also have to delete all edges which contain the vertex. The six graphs obtained by

deleting each of the vertices ofGare shown in Fig. 8-39. All six graphs are connected; hence no vertex is a cut point.

Fig. 8-39

8.6. Show that the six graphs obtained in Problem 8.5 are distinct, that is, no two of them are isomorphic. Also

show that(B)and(C)are homeomorphic.

The degrees of the five vertices of any graph cannot be paired off with the degrees of any other graph, except for(B)

and(C). Hence none of the graphs is isomorphic except possibly(B)and(C).

However if we delete the vertex of degree 3 in(B)and(C), we obtain distinct subgraphs. Thus(B)and(C)are also

nonisomorphic; hence all six graphs are distinct. However,(B)and(C)are homeomorphic since they can be obtained

from isomorphic graphs by adding appropriate vertices.

TRAVERSABLE GRAPHS, EULER AND HAMILTONIAN CIRCUITS

8.7. Consider each graph in Fig. 8-40. Which of them are traversable, that is, have Euler paths?

Which are Eulerian, that is, have an Euler circuit? For those that do not, explain why.

Fig. 8-40

Gis traversable (has an Euler path) if only 0 or 2 vertices have odd degree, andGis Eulerian (has an Euler

circuit) if all vertices are of even degree (Theorem 8.3).

(a) Traversable, since there are two odd vertices. The traversable path must begin at one of the odd vertices and will

end at the other.

(b) Traversable, since all vertices are even. ThusGhas an Euler circuit.

(c) Since six vertices have odd degrees,Gis not traversable.