Though the stack method is much simpler, this is the how the graph is constructed :
Each distinct room is indicated by a distinct color.
1.Create a node for job A.
2.Job B which starts after A (and before A ends) should be given a different room. So we create a node for B and to ensure that A and B do not belong to the same room we give different color to these nodes. If we connect A and B then we can ensure that the chromatic no. of the graph (till now) will give us the no. of different rooms.
3. Job C has arrived while A and B are still in execution. This means a 3rd room has to be given to C. How can we ensure that using colors? If we connect A and B both to C then the chromatic no. becomes 3 which again indicates the no. of different rooms needed till now.
4. A ends. D starts. So we can give the room left by A to D. Then we don't connect A and D in the graph so that they can get the same color. BUT we have to connect D with B and C because their color (rooms) can't be given to D.
5. C ends. E starts. Currently D and B are still in execution occupying 2 different rooms. So E can't get their colors. Connect D and B to E.
6. F starts. B,D,E are still there. So connect F with B,D,E.
7. B ends. D ends. E and F are still there. G starts. Connect G to E and F.
8. E ends. F ends. G is still there. H starts. Connect H to G.