OCR D1 2005 June — Question 2

Exam BoardOCR
ModuleD1 (Decision Mathematics 1)
Year2005
SessionJune
TopicCombinations & Selection

2 A simple graph is one which has no repeated arcs and no arc that joins a vertex to itself.
  1. Draw a simple graph that connects four vertices using five arcs.
  2. Explain why, in any graph, there must be an even number of odd vertices.
  3. By considering the orders of the vertices, show that there is only one possible simple graph that connects four vertices using five arcs.