- #1
whiteman
- 9
- 0
Homework Statement
Nine students A, B,..., I serve as members on eight committees, as follows.
Committee 1: A, B, C, D
Committee 2: A, C, D, E
Committee 3: B, D, F, G
Committee 4: C, F, G, H
Committee 5: A, H
Committee 6: H, I
Committee 7: G, H
Committee 8: E, I
Each committee is to meet for a day. No two committees with a member in common can meet on the same day. Use a colouring of a suitable graph to find the least number of days in which the meetings can take place.
Homework Equations
None
The Attempt at a Solution
Let 1,2...,8 be vertices on a graph and let an edge be between two vertices if those committees share a student. If an edge exists between two vertices, then those vertices must be coloured differently
I've drawn out the graph properly, and is 4 (the number of colours used to colour the graph) the minimum no of days needed for the committees to meet? I know that 4 can be used by the Appel-Haken Theorem. i can't see a way to colour the graph with only 3 colours.
thanks for any help :)
Last edited: