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

178 GRAPH THEORY [CHAP. 8

SolvedProblems

GRAPH TERMINOLOGY

8.1. Consider the graphGin Fig. 8-36(a).

(a) DescribeGformally, that is, find the setV (G)of vertices ofGand the setE(G)of edges ofG.

(b) Find the degree of each vertex and verify Theorem 8.1 for this graph.

(a) There are five vertices soV (G)={A, B, C, D, E}. There are seven pairs{x, y}of vertices where the vertexxis

connected with the vertexy, hence

E(G)=[{A, B},{A, C},{A, D},{B, C},{B, E},{C, D},{C, E}]

(b) The degree of a vertex is equal to the number of edges to which it belongs; e.g., deg(A)=3 sinceAbelongs to

the three edges{A, B},{A, C},{A, D}. Similarly,

deg(B)= 3 ,deg(C)= 4 ,deg(D)= 2 ,deg(E)= 2

The sum of the degrees is 3+ 3 + 4 + 2 + 2 =14 which does equal twice the number of edges.

Fig. 8-36

8.2. Consider the graphGin Fig. 8-36(b). Find:

(a) all simple paths fromAtoF;(d) diam(G), the diameter ofG;

(b) all trails fromAtoF;(e) all cycles which include vertexA;

(c) d(A,F), the distance fromAtoF;(f) all cycles inG.

(a) A simple path fromAtoFis a path such that no vertex, and hence no edge, is repeated. There are seven such paths,

four beginning with the edges{A, B}and three beginning with the ege{A, D}:

(A,B,C,F), (A,B,C,E,F), (A,B,E,F), (A,B,E,C,F),

(A,D,E,F), (A,D,E,B,C,F), (A,D,E,C,F).

(b) A trail fromAtoFis a path such that no edge is repeated. There are nine such trails, the seven simple paths from

(a)together with

(A,D,E,B,C,E,F) and (A,D,E,C,B,E,F).

(c) There is a path, e.g.,(A,B,C,F), fromAtoFof length 3 and no shorter path fromAtoF; henced(A,F)=3.

(d) The distance between any two vertices is not greater than 3, and the distance fromAtoFis 3; hence diam(G)=3.

(e) A cycle is a closed path in which no vertex is repeated (except the first and last). There are three cycles which

include vertexA:

(A,B,E,D,A), (A,B,C,E,D,A), (A,B,C,F,E,D,A).

(f) There are six cycles inG; the three in(e)and

(B,C,E,B), (C,F,E,C), (B,C,F,E,B).