Special graphsAQA A-Level Further Maths: Subtopic test

1. 1
   A simple graph $G$ has 7 vertices and 8 edges.

   (a)

   How many edges does the complement of $G$ have?

   [1 mark]

   • A$8$
   • B$21$
   • C$13$
   • D$14$

   (b)

   A vertex $v$ of $G$ has degree 2. What is the degree of $v$ in the complement of $G$?

   [1 mark]

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

   (c)

   Explain why $G$ cannot be a tree.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   A graph has vertices $P$, $Q$, $R$, $S$, $T$. Its adjacency matrix, with rows and columns in the order $P,Q,R,S,T$, is $\begin{pmatrix} 0&0&0&1&1 \\ 0&0&0&1&0 \\ 0&0&0&0&1 \\ 1&1&0&0&0 \\ 1&0&1&0&0 \end{pmatrix}$.

   (a)

   How many edges does the graph have?

   [1 mark]

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

   (b)

   Which statement about the graph is correct?

   [1 mark]

   • AIt is a complete bipartite graph
   • BIt is a tree
   • CIt contains a cycle
   • DIt is a complete graph

   (c)

   Show that the graph is bipartite, stating the two sets of vertices.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   $G$ is a simple connected graph with 6 vertices. The degrees of its vertices are 4, 4, 3, 2, 2, 1.

   (a)

   Show that $G$ has 8 edges and explain why $G$ is not a tree.

   [3 marks]

   (b)

   Let $G'$ be the complement of $G$. Find the degrees of the vertices of $G'$, show that $G'$ has 7 edges, and state with a reason whether $G'$ is a tree.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   The complete bipartite graph $K_{3,3}$ has vertex sets $\{A,B,C\}$ and $\{X,Y,Z\}$, with every vertex in one set joined to every vertex in the other set. The graph $G$ is formed from $K_{3,3}$ by deleting the three edges $AX$, $BY$ and $CZ$.

   (a)

   (i) Show that $G$ has 6 edges.
   (ii) Write down the adjacency matrix of $G$, with the vertices in the order $A,B,C,X,Y,Z$.
   (iii) Write down the degree of every vertex of $G$.

   [6 marks]

   (b)

   Let $G'$ be the complement of $G$.
   (i) Find the number of edges of $G'$.
   (ii) Write down the degree of each vertex of $G'$.
   (iii) Prove that $G'$ is not bipartite.

   [6 marks]

   Total for question 4: 12 marks

End of questions