Activity Sheet 1

Reporter
:
Speaker
:

Section 1.1

  1. Consider the courses that each of the students in this class is taking. Assume that all these courses will have a final exam. We want to figure out how many different time slots we would need to use. Two courses cannot go in the same time slot if they are in the same department, or if a student is taking both of them.
    1. Draw a graph whose vertices are to be the different courses, and where we draw an edge between two graphs if they cannot go in the same time slot because of the two reasons above.
    2. Using the graph, determine what the smallest number of time slots we would need is, and justify your answer.
    3. Can we abstract away the key elements in this problem, so we can apply them to other settings? Can you express this problem purely in terms of graphs?

Section 1.2

  1. Describe at least three different proper subgraphs of the graph in question 1. At least one of these should be an induced subgraph, and at least one should not.
  2. Is the graph we constructed in question 1 connected? Did it necessarily have to be connected? Explain.
  3. What is the diameter of the graph in question 1?