Euler's formula for planar graphsAQA A-Level Further Maths: Subtopic test

1. 1
   A connected planar graph $G$ has $8$ vertices and $12$ edges.

   (a)

   How many faces does $G$ have, including the outer face?

   [1 mark]

   • A$4$
   • B$5$
   • C$6$
   • D$8$

   (b)

   A new vertex is added to $G$ 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$6$
   • B$7$
   • C$5$
   • D$9$

   (c)

   Every face of $G$, including the outer face, is bounded by the same number of edges. Find this number.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   A connected simple planar graph has $7$ vertices, and every face, including the outer face, is bounded by exactly $3$ edges.

   (a)

   Which equation connects the number of edges $e$ and the number of faces $f$?

   [1 mark]

   • A$3f=e$
   • B$f=3e$
   • C$2f=3e$
   • D$3f=2e$

   (b)

   How many edges does the graph have?

   [1 mark]

   • A$10$
   • B$15$
   • C$17$
   • D$21$

   (c)

   Find the number of faces, and state how many of them are bounded faces, not counting the outer face.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   A connected planar graph has $9$ vertices, and its edges divide the plane into $8$ faces, including the outer face.

   (a)

   Find the number of edges.

   [3 marks]

   (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]

   Total for question 3: 7 marks

4. 4
   A road network on a flat island has $12$ junctions joined by roads that do not cross. The network is connected, exactly $3$ 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 $4$ roads or $6$ roads. Find how many regions there are of each type.

   [6 marks]

   (b)

   A second proposal has $12$ junctions and $31$ 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]

   Total for question 4: 12 marks

End of questions