Discrete Mathematical Structures by Pearson

10-10 Discrete Mathematical Structures

The number of edges is half the sum of all degree of vertices, that is, 2. Hence a possible

graph is

v

4

v

3

v

2

v

1

which is a disconnected graph.

(3) In the given sequence (1, 1, 1, 1, 1, 1), the sum of degrees of all vertices is even, that is,

6 and also number of odd vertices is even, that is, 6. Hence, a graph is possible. For the

graph, the number of edges will be half the sum of degrees of all vertices, that is, 3. Hence,

a possible graph is a disconnected graph.

v

2

v

1

v

4

v

3

v

5

v

6

THEOREM 10.4 The maximum number of edges in a simple graph of n vertices is n(n - 1)/2.

Proof: Let G = (V, E) be a simple graph with ...