Discrete Mathematical Structures by Pearson

Appendix A-21

4.

K

3

K

4

K

4

K

5

5. (i) In a regular graph all vertices are of equal degree.

Regular graphs of degree 2 (with three and four vertices) are

3-regular 3-regular

3-regular

2-regular 2-regular 2-regular

(ii) Yes, K

n

is a regular graph of degree n − 1.

6. (i) The isolated vertices are v

5

and v

6

and pendant vertices are v

3

and v

9

.

(ii) (a) There are

5

C

2

= 10 ways of choosing two vertices from the set V of graph G and

hence the number of edges are 10.

(b) In a multigraph, multiple edges are permitted, and hence the graph G can have any

number of edges. No maximum number of edges exists.

(iii) No. In a simple graph of n vertices, the maximum number ...