Graphs to find minimum days for meetings

[whiteman]

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.

EDIT: just realized that 2 and 5 should be connected on the graph but it doesn't make any difference to the colouring.

thanks for any help :)

 

[Outlined]

Well, you have a clique (all nodes are connected to each other): \{1, 2, 3, 4\} so you need at least 4 colors, with 3 colors you can not even color your clique.