August 2000
MA214 : DISCRETE MATHEMATICS

QUESTION 5

Total Marks: 15 Marks

• Question 1
• Question 2
• Question 3
• Question 4
• Cover Page

Click to access
SUGGESTED SOLUTIONS
for Question 5

((a) Let G be a graph. Prove that the sum of the degrees of the vertices of G is equal to twice the number of its edges. [2]

(b) Calculate the number of edges of each of the following graphs, if the graph
exists. For graphs that do not exist, explain their non-existence.
(i) G1: A 5-regular graph with 7 vertices. [1]
(ii) G2: The complete bipartite graph K_2,4. [1]
(iii) G3: The complete graph K₅ with 5 vertices. [1]

(c) For the graphs that do exist:
(i) Draw the graphs, labelling all vertices [4]
(ii) Write down their adjacency matrices and their distance matrices. [6]