OCR MEI D1 2007 June — Question 1

Exam BoardOCR MEI
ModuleD1 (Decision Mathematics 1)
Year2007
SessionJune
TopicGraph Theory Fundamentals

1 Bus routes connect towns A and B and towns A and C .
Train lines connect towns B and D, towns C and D, and towns A and C.
John represents this information in a graph with four nodes, one for each town, in which an arc is drawn for each connection, giving five arcs in all.
  1. Draw John's graph.
  2. Is John's graph simple? Justify your answer. Jamil represents the information in a graph with five nodes. He uses one node for each of towns A, B and D. Because in town C the bus station and train station are some distance apart, he uses a node labelled C (bus) and a node labelled C (train). Again there are 5 arcs, each representing a connection.
  3. Draw Jamil's graph.
  4. Is Jamil's graph a tree? Justify your answer.