Discrete Mathematical Structures by Pearson

Trees 11-21

The number of vertices n = 5

The number of edges e = 7

The number of branches of spanning tree S = 4 (dark line) = 5 - 1 = n - 1

The number of chords of spanning tree S = 3, that is, edges e

1

, e

4

, and e

3

∴ Rank of G = n - 1 = 5 - 1 = 4

Nullity of G = e - n + 1 = 7 - 5 + 1 = 3

Further Rank of G + Nullity of G = 4 + 3 = 7 = Number of edges in G

Example 2 A farmhouse consists of five walled plots of land as shown in Fig. 11.31(a) and these

are full of water. Find the number of walls that will have to be broken so that the water is drained

out completely.

2

3

4

5

1

Figure 11.31(a)

a

b

f

d

c

Figure 11.31(b)

Solution:

The number of vertices n = 8

The number ...