December 1998
MA214: DISCRETE MATHEMATICS

QUESTION 5

Total Marks: 20 Marks

 Click here to access other questions

SUGGESTED SOLUTIONS
Solutions and allocated marks are indicated in green.
Return to Question 5

 
(a) (i) Give the conditions for a graph to be bipartite. [1]
A graph is bipartite  if its vertices can be separated into two sets such that all vertices within the same set are non-adjacent.

 
(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]
Edge fi should be removed.

 
(iii) Give the vertices in each of the subsets X and Y of the bipartition. [2]
X = {a,d,e,f,i},   Y = {b,c,g,h]
X and Y may be interchanged. Subtract one mark for each error or omission up to a maximum of two.

 
(b) Write down the adjacency matrices and draw the graphs given below:
(i) a complete graph with five vertices [4]
 

2 marks for matrix - one subtracted for each error or omission up to a maximum of two.
2 marks for graph.

 
(ii) a K1,5   (complete bipartite). [4]
 

2 marks for matrix - one subtracted for each error or omission up to a maximum of two.
2 marks for graph.

 
(iii) a 2-regular graph with 4 vertices. [3]
 

2 marks for matrix - one subtracted for each error or omission up to a maximum of two.
1 mark for graph.

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

 

 
For each part, the mark is awarded if candidates identify all the graphs satisfying the conditions and no other graphs. No half marks!
Which of the graphs are [1]
(i) reflexive? [1]
G,H

 
(ii) irreflexive? [1]
None of the graphs.

 
(iii) symmetric? [1]
G

 
(iv) antisymmetric? [1]
H

 
(v) transitive? [1]
F