Discrete Mathematical Structures by Pearson

10-6 Discrete Mathematical Structures

Example 1 Consider the graph (Fig. 10.6) with four vertices a, b, c, and d.

b

a

d

c

Figure 10.6

d(a) = 4, d(b) = 4, d(c) = 2, d(d) = 4

The sum of degrees all vertices is

= 4 + 4 + 2 + 4 = 14

Since the sum is even, there might be a graph with 14/2 = 7 edges.

Fig. 10.6 demonstrates such a graph.

Even and Odd Vertex: A vertex is said to be an even vertex if its degree is even. In case its

degree is odd, the vertex is called an odd vertex.

THEOREM 10.2 The number of vertices of odd degree in a graph is always even.

Proof: Considering even and odd vertices separately for a graph, we have

dv dv dv

i

i

n

jk

()

=+

=

∑∑ ∑

1

()

()

even