April 2000
MA214 : DISCRETE MATHEMATICS

QUESTION 3

Total Marks: 15 Marks

• Question 1
• Question 2
• Question 4
• Question 5
• Cover Page

Click to access
SUGGESTED SOLUTIONS
for Question 3

(a) denotes the complete graph on n vertices,and denotes a cycle having n vertices.
[2 marks ]
[2 marks ]

(b)How many edges do the following graphs have?
(i) [2 marks ]
(ii) [2 marks ]

(c)Consider the directed multigraph shown below.

(i)List the vertices.
(ii)List the edges.
(iii)Find the in –degree and out –degree of each vertex.
[4 marks ]

(d)Consider the two graphs below.One graph is bipartite,the other is not bipartite. State,giving reasons,which graph is bipartite.For this bipartite graph find two sets of vertices A and B so that vertices within the same set are nonadjacent.[3 marks ]