December 1998
MA214: DISCRETE MATHEMATICS

QUESTION 5

Total Marks: 20 Marks

 Click here to access other questions

Click to access
SUGGESTED SOLUTIONS
for Question 5

 
(a) (i) Give the conditions for a graph to be bipartite. [1]
(ii) The graph below is not bipartite.

 

It can be made bipartite by removing one edge. Copy the graph, removing the appropriate edge to make it bipartite.

 [1]
(iii) Give the vertices in each of the subsets X and Y of the bipartition.

 

 [2]
(b) Write down the adjacency matrices and draw the graphs given below:
(i) a complete graph with five vertices [4]
(ii) a K1,5   (complete bipartite). [4]
(iii) a 2-regular graph with 4 vertices.

 

 [3]
(c) Consider the set A = {a,b,c} and the relations on A represented by the directed graphs F,G and H below.

 

 
Which of the graphs are [1]
(i) reflexive? [1]
(ii) irreflexive? [1]
(iii) symmetric? [1]
(iv) antisymmetric? [1]
(v) transitive? [1]