Discrete Mathematical Structures by Pearson

Topics in Graph Theory 10-7

Complete graphs are useful in modelling round-robin tournaments where every team plays

every other team exactly once. With n teams participating in the tournament, K

n

provides the

solution.

THEOREM 10.3 If G = (V, E) is a directed graph, then the sum of outdegree vertices is equal to

the sum of indegree vertices which equals to the number of edges.

This is

in v out

ve

i

ji

j

deg( )deg ()

==

∑∑

(the number of edges).

This is illustrated with the help of an example given in Fig. 10.7.

v

1

v

2

v

3

v

4

v

5

Figure 10.7

Vertex

v

1

v

2

v

3

v

4

v

5

Indegree

0 1 3 3 2

Outdegree

3 2 2 1 1

Sum of indegree vertices = 0 + 1 + 3 + 3 + 2 = 9

Sum of outdegree vertices ...