Euler's formula for planar graphs

Euler's formula for planar graphs Test

Spec DA3 · AQA A-Level Further Maths: Subtopic test

Studying this course? Keep your progress in one place.

Two ways to do this test

Question by question

One question at a time. Each answer is marked the moment you hand it in, so you learn as you go. Drago helps if you get stuck. All 10 questions, or just 5.

Exam mode

The whole paper in one go, timed like the real exam. Nothing is marked until you hand it in, then you get every mark explained.

10 questions, 27 marks

AQA A-Level Further Maths

Euler's formula for planar graphs

Total 27 marks

Name

Class

Date

  1. 1
    A connected planar graph GG has 88 vertices and 1212 edges.
    (a)
    How many faces does GG have, including the outer face?
    [1 mark]
    • A44
    • B55
    • C66
    • D88
    Show the mark scheme

    Mark scheme

    Answer: C
    (b)
    A new vertex is added to GG and joined to it by a single new edge, so that the graph is still planar. How many faces does the new graph have?
    [1 mark]
    • A66
    • B77
    • C55
    • D99
    Show the mark scheme

    Mark scheme

    Answer: A
    (c)
    Every face of GG, including the outer face, is bounded by the same number of edges. Find this number.
    [2 marks]
    Show the mark scheme

    Mark scheme

    M1: each edge borders two faces, so the total number of edge-sides around the faces is 2×12=242\times12=24
    A1:
    246=4\frac{24}{6}=4 edges per face
    Accept: follow-through from their number of faces in (a)

    Do not accept:
    126=2\frac{12}{6}=2

    Total for question 1: 4 marks

  2. 2
    A connected simple planar graph has 77 vertices, and every face, including the outer face, is bounded by exactly 33 edges.
    (a)
    Which equation connects the number of edges ee and the number of faces ff?
    [1 mark]
    • A3f=e3f=e
    • Bf=3ef=3e
    • C2f=3e2f=3e
    • D3f=2e3f=2e
    Show the mark scheme

    Mark scheme

    Answer: D
    (b)
    How many edges does the graph have?
    [1 mark]
    • A1010
    • B1515
    • C1717
    • D2121
    Show the mark scheme

    Mark scheme

    Answer: B
    (c)
    Find the number of faces, and state how many of them are bounded faces, not counting the outer face.
    [2 marks]
    Show the mark scheme

    Mark scheme

    M1: 7−15+f=27-15+f=2, or f=2×153f=\frac{2\times15}{3}
    A1:
    1010 faces in total, so 99 bounded faces

    Total for question 2: 4 marks

  3. 3
    A connected planar graph has 99 vertices, and its edges divide the plane into 88 faces, including the outer face.
    (a)
    Find the number of edges.
    [3 marks]
    Show the mark scheme

    Mark scheme

    B1: Euler's formula v−e+f=2v-e+f=2
    M1:
    9−e+8=29-e+8=2
    A1:
    e=15e=15
    (b)
    Two new vertices are added, each joined to the graph by a single new edge. One further edge is then drawn between two existing vertices without crossing any other edge. Find the number of faces of the new graph.
    [4 marks]
    Show the mark scheme

    Mark scheme

    M1: new graph has 9+2=119+2=11 vertices
    M1:
    15+2+1=1815+2+1=18 edges
    M1:
    11−18+f=211-18+f=2
    A1:
    f=9f=9
    Accept: follow-through from their number of edges in (a)

    Total for question 3: 7 marks

  4. 4
    A road network on a flat island has 1212 junctions joined by roads that do not cross. The network is connected, exactly 33 roads meet at every junction, and the unbounded outer region counts as a region.
    (a)
    (i) Find the number of roads.
    (ii) Find the number of regions.

    (iii) Every region is bounded by either
    44 roads or 66 roads. Find how many regions there are of each type.
    [6 marks]
    Show the mark scheme

    Mark scheme

    M1: (i) sum of the degrees is 12×3=3612\times3=36, which is twice the number of roads
    A1: (i)
    1818 roads
    M1: (ii)
    12−18+f=212-18+f=2
    A1: (ii)
    88 regions
    M1: (iii)
    x+y=8x+y=8 and 4x+6y=364x+6y=36 (each road borders two regions, so the edge-sides total 2×182\times18)
    A1: (iii)
    66 regions bounded by 44 roads and 22 regions bounded by 66 roads
    (b)
    A second proposal has 1212 junctions and 3131 roads. It is connected and planar, and has no loops and no pairs of roads joining the same two junctions. Show that this network cannot be built.
    [6 marks]
    Show the mark scheme

    Mark scheme

    M1: 12−31+f=212-31+f=2
    A1:
    f=21f=21
    B1: the numbers of roads around the regions total
    2×31=622\times31=62, as each road borders two regions
    B1: with no loops or multiple roads each region is bounded by at least
    33 roads, so the total is at least 3×21=633\times21=63
    M1: compares
    6363 with 6262
    R1:
    63>6263>62 is a contradiction, so such a network cannot exist

    Total for question 4: 12 marks

End of questions

Subtopic tests