Exercise 11.1

Q3)

Paths from b to f- there are 6 paths from b to f

1. B e f

2. B a c d e f

3. B a c d e g f

4. B e g f

5. B c d e f

6. B c d e g f

Q6)

1. d to e = 1

2. d to f = 1

3. d to c = 1

4. d to k = 2- goes through c

5. d to g = 2 -goes through c

6. d to h = 3- goes through f and g

7. d to j = 3- goes through c and g

8. d to l = 3-goes through c and k

9. d to m = 3-goes through c and k

10. d to i = 4- goes through c, g and h

Q8)

The smallest number of guards needed in the store will be 3.

The guards can wither stand at vertices c, d, and j or I, a, and g

Q10)

Connecting graph G where removing any edge of G results in a disconnected graph is a path

A C E G

| | | |

B D F

Exercise 11.2

Q1)

a) How many connected subgraphs ofGhave four vertices

and include a cycle? There are 3 connected subgraphs

1. {b,a}, {a,c}, {c.d} and {d,a}

2. {f,c}, {c,a}, {a,d} and {d,c}

3. {I,d}, {d,c}, {c,a} and {a,d}

b) Describe the subgraph G1 (of G) in part (b) of the figure

first, as an induced subgraph and second, in terms of

deleting a vertex of G.

G1 is the subgraph of G induced by the vertices a, b, d, f, g, h, I, and j. G1 also is obtained by deleting the vertex c from G, that is, G1=G-c

c) Describe the subgraphG2 (ofG) in part (c) of the figure

first, as an induced subgraph and second, in terms of the

deletion of vertices of G.

G2 is the subgraph of G induced by the vertices c, b, d, f, g, I, and j . G2 is obtained from G by deleting the vertices a and h from G, that is, G2=G-a-h

Exercise 11.3

Q20)

a) Find an Euler circuit for the graph in Fig. 11.44.

a b c g k j i h d e f

a d h i j k g c b e f is an Euler Circuit.

b) If the edge {d, e} is removed from this graph, find an Euler trail for the resulting subgraph.

a b c g k j f i h is an Euler Trail.

Q22)

For the graph in Fig. 11.37(b), what is the smallest number of bridges that must be removed so...