AQA A-Level Further Maths
Euler's formula for planar graphs
Total 27 marks
Name
Class
Date
- 1A connected planar graph has vertices and edges.(a)How many faces does have, including the outer face?[1 mark]
- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: C(b)A new vertex is added to 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]- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: A(c)Every face of , 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
A1: edges per face
Accept: follow-through from their number of faces in (a)
Do not accept:Total for question 1: 4 marks
- 2A connected simple planar graph has vertices, and every face, including the outer face, is bounded by exactly edges.(a)Which equation connects the number of edges and the number of faces ?[1 mark]
- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: D(b)How many edges does the graph have?[1 mark]- A
- B
- C
- D
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: , or
A1: faces in total, so bounded facesTotal for question 2: 4 marks
- 3A connected planar graph has vertices, and its edges divide the plane into faces, including the outer face.(a)Find the number of edges.[3 marks]
Show the mark scheme
Mark scheme
B1: Euler's formula
M1:
A1:(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 vertices
M1: edges
M1:
A1:
Accept: follow-through from their number of edges in (a)Total for question 3: 7 marks
- 4A road network on a flat island has junctions joined by roads that do not cross. The network is connected, exactly roads meet at every junction, and the unbounded outer region counts as a region.(a)(i) Find the number of roads.[6 marks]
(ii) Find the number of regions.
(iii) Every region is bounded by either roads or roads. Find how many regions there are of each type.Show the mark scheme
Mark scheme
M1: (i) sum of the degrees is , which is twice the number of roads
A1: (i) roads
M1: (ii)
A1: (ii) regions
M1: (iii) and (each road borders two regions, so the edge-sides total )
A1: (iii) regions bounded by roads and regions bounded by roads(b)A second proposal has junctions and 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:
A1:
B1: the numbers of roads around the regions total , as each road borders two regions
B1: with no loops or multiple roads each region is bounded by at least roads, so the total is at least
M1: compares with
R1: is a contradiction, so such a network cannot existTotal for question 4: 12 marks
End of questions