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

CHAP. 8] GRAPH THEORY 191

SupplementaryProblems

GRAPH TERMINOLOGY

8.34. Consider the graphGin Fig. 8-58. Find:

(a) degree of each vertex (and verify Theorem 8.1);

(b) all simple paths fromAtoL;

(c) all trails (distinct edges) fromBtoC;

(d) d(A,C), distance fromAtoC;

(e) diam(G), the diameter ofG.

Fig. 8-58

8.35. Consider the graph in Fig. 8-58. Find (if any): (a) all cycles; (b) all cut points; (c) all bridges.

8.36. Consider the graph in Fig. 8-58. Find the subgraphH=H(V′,E′)ofGwhereV′equals:

(a) {B, C, D, J, K} (b){A, C, J, L, M} (c){B, D, J, M} (d){C, K, L, M}

Which of them are isomorphic and which homeomorphic?

8.37. Suppose a graphGcontains two distinct paths from a vertexuto a vertexv. Show thatGhas a cycle.

8.38. SupposeGis a finite cycle-free graph with at least one edge. Show thatGhas at least two vertices of degree 1.

8.39. Show that a connected graphGwithnvertices must have at leastn−1 edges.

8.40. Find the number of connected graphs with four vertices. (Draw them.)

8.41. LetGbe a connected graph. Prove:

(a) IfGcontains a cycleCwhich contains an edgee, thenG−eis still connected.

(b) Ife={u, v}is an edge such thatG−eis disconnected, thenuandvbelong to different components ofG−e.

8.42. SupposeGhasVvertices andEedges. LetMandmdenote, respectively, the maximum and minimum of the degrees

of the vertices inG. Show thatm≤ 2 E/V≤M.

8.43. Consider the following two steps on a graphG:(1)Delete an edge. (2) Delete a vertex and all edges containing that

vertex. Show that every subgraphHof a finite graphGcan be obtained by a sequence consisting of these two steps.

TRAVERSABLE GRAPHS, EULER AND HAMILTONIAN CIRCUITS

8.44. Consider the graphsK 5 ,K 3 , 3 andK 2 , 3 in Fig. 8-59. Find an Euler (traversable) path or an Euler circuit of each graph,

if it exists. If it does not, why not?

8.45. Consider each graph in Fig. 8-59. Find a Hamiltonian path or a Hamiltonian circuit, if it exists. If it does not, why not?

8.46. Show thatKnhasH=(n− 1 )!/2 Hamiltonian circuits. In particular, find the number of Hamiltonian circuits for the

graphK 5 in Fig. 8-59(a).

8.47. SupposeGandG∗are homeomorphic graphs. Show thatGis traversable (Eulerian) if and only ifG∗is traversable

(Eulerian).