COMPUTER SCIENCE - GRAPGH THEORY AND APPLICATION

3. Let n be a non-negative integer. Suppose that in a school, there are 3 classes, A, B and 0 each with 'n, students, and that any given student belongs to exactly one class. Moreover, suppose that every student knows exactly 'n, + 1 students from the other two classes they are not in. Dene a graph G = C(V, E) where the vertices represent students and an edge joins two vertices whenever these vertices represent students from different classes who know each other. For a class X E {A,B, C} and any student 3; not in class X, i.e. y i X, dene N X (y) to be the students in X that y knows. For example if b E B, then NA(b) = {a E A : ab 6 E(G)}, i.e. NAG) is the set of students in class A who know 6. (a) Now x a c E 0. Suppose that |N3(c)| = m for some m. Write down the possible values of m and hence give an expression for |NA(c)| in terms of n, and m. (2 marks) (b) Show that there must be three students, each from different classes who all know each other. (8 marks)