Discrete Mathematics 1: GraphsAQA A-Level Further Maths: Topic test

1. 1
   A simple connected graph $G$ has vertices $L,\ M,\ N,\ R,\ S,\ T$ and eight edges: $LM$, $MN$, $NR$, $RS$, $ST$, $TL$, $LR$ and $MS$.

   (a)

   What is the sum of the degrees of the vertices of $G$?

   [1 mark]

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

   (b)

   Which statement about $G$ is correct?

   [1 mark]

   • A$G$ is Eulerian, because it is connected
   • B$G$ is semi-Eulerian, because it has an even number of odd vertices
   • C$G$ is neither Eulerian nor semi-Eulerian, because four of its vertices have odd degree
   • D$G$ is Eulerian, because every vertex has degree at least $2$

   (c)

   Show that $G$ is Hamiltonian.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   A connected planar graph $G$ has $11$ edges and divides the plane into $7$ faces, including the outer face.

   (a)

   How many vertices does $G$ have?

   [1 mark]

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

   (b)

   $G$ is also simple. What is the greatest number of edges that a simple connected planar graph with this number of vertices can have?

   [1 mark]

   • A$12$
   • B$15$
   • C$18$
   • D$9$

   (c)

   A different simple connected graph $H$ has $7$ vertices and $16$ edges. Show that $H$ is not planar.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   The graph $C$ is the cycle graph with vertices $1,\ 2,\ 3,\ 4,\ 5$ and edges $12$, $23$, $34$, $45$ and $51$.

   (a)

   Find the number of edges in the complement of $C$ and list them.

   [3 marks]

   (b)

   Explain why $C$ is not bipartite, and state which single edge could be deleted to leave a bipartite tree, naming the two vertex sets.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   Graph $H$ has vertices $A,\ B,\ C,\ D,\ E,\ X$ and eleven edges: $AX$, $XB$, $AC$, $AD$, $AE$, $BC$, $BD$, $BE$, $CD$, $CE$ and $DE$. Graph $J$ has vertices $1,\ 2,\ 3,\ 4,\ 5,\ 6$ and eleven edges: $13$, $14$, $15$, $23$, $24$, $25$, $34$, $35$, $45$, $61$ and $62$.

   (a)

   Show that the test $e\le3v-6$ does not decide whether $H$ is planar, then use Kuratowski's theorem to prove that $H$ is not planar.

   [6 marks]

   (b)

   Show that $H$ and $J$ are isomorphic, and deduce whether $J$ is planar.

   [6 marks]

   Total for question 4: 12 marks

5. 5
   Graph $T$ has vertices $s,\ t,\ u,\ v,\ w,\ x$ and seven edges: $st$, $tu$, $us$, $uv$, $vw$, $wx$ and $xv$.

   (a)

   Which statement about $T$ is correct?

   [1 mark]

   • A$T$ is semi-Eulerian but not Eulerian
   • B$T$ is Eulerian
   • C$T$ is Hamiltonian
   • D$T$ is neither Eulerian nor semi-Eulerian

   (b)

   Which sequence of vertices is a cycle in $T$?

   [1 mark]

   • A$s,\ t,\ u$
   • B$u,\ v,\ w,\ x,\ v,\ u$
   • C$s,\ t,\ u,\ v,\ s$
   • D$v,\ w,\ x,\ v$

   (c)

   Write down an Euler trail in $T$.

   [2 marks]

   Total for question 5: 4 marks

6. 6
   A connected planar graph $G$ has $10$ vertices and $15$ edges.

   (a)

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

   [1 mark]

   • A$6$
   • B$7$
   • C$27$
   • D$3$

   (b)

   Suppose also that $G$ is simple and bipartite. What is the greatest number of edges that a simple connected planar bipartite graph with $10$ vertices can have?

   [1 mark]

   • A$24$
   • B$20$
   • C$16$
   • D$14$

   (c)

   Show that it is impossible for every face of $G$, including the outer face, to be bounded by exactly $3$ edges.

   [2 marks]

   Total for question 6: 4 marks

7. 7
   The complete bipartite graph $K_{3,4}$ has $7$ vertices in two sets, one of $3$ vertices and one of $4$. Every vertex in one set is joined to every vertex in the other set, and there are no other edges.

   (a)

   State the number of edges and the degree of each vertex of $K_{3,4}$, and explain whether the graph is Eulerian or semi-Eulerian.

   [3 marks]

   (b)

   Every face of a planar drawing of $K_{3,4}$ would be bounded by at least $4$ edges. Use Euler's formula to show that $K_{3,4}$ is not planar.

   [4 marks]

   Total for question 7: 7 marks

8. 8
   Graph $G$ has vertices $1,\ 2,\ 3,\ 4,\ 5,\ 6$ and seven edges: $12$, $23$, $34$, $45$, $56$, $61$ and $14$. Graph $H$ has vertices $a,\ b,\ c,\ d,\ e,\ f$ and seven edges: $ab$, $bc$, $cd$, $de$, $ef$, $fa$ and $ac$. In a planar drawing of $G$ the edges do not cross.

   (a)

   Show that $G$ and $H$ have the same degree sequence but are not isomorphic.

   [6 marks]

   (b)

   Show that $G$ is bipartite. Use Euler's formula to find the number of faces in the planar drawing of $G$, and find the number of edges in the complement of $G$ and its degree sequence.

   [6 marks]

   Total for question 8: 12 marks

End of questions