AQA D1 2014 June — Question 8

Exam BoardAQA
ModuleD1 (Decision Mathematics 1)
Year2014
SessionJune
TopicGraph Theory Fundamentals

8 In this question you may use the fact that any simple graph must have an even number of vertices of odd degree.
  1. A simple graph has five vertices and their degrees are $$x , x + 1 , x + 1 , x + 2 \text { and } x + 3$$
    1. Show that \(x\) must be odd.
    2. Find the value of \(x\) and draw a graph with vertices having the given degrees.
  2. A simple graph has 10 vertices.
    1. State the minimum possible degree and maximum possible degree of a vertex.
    2. Show that the degrees of the vertices cannot all be different.