Graph theory terminologyEdexcel International A Level Maths: Subtopic test

1. 1
   A graph $G$ has vertices $A, B, C, D, E$ and edges $AB$, $AC$, $BC$, $CD$ and $DE$.

   (a)

   What is the degree of vertex $C$?

   [1 mark]

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

   (b)

   Which of the following is a cycle in $G$?

   [1 mark]

   • A$A\to B\to C\to A$
   • B$C\to D\to E$
   • C$A\to B\to C\to D\to E$
   • D$A\to C\to D\to C\to A$

   (c)

   State, with a reason, whether $G$ is a tree.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   $K$ is the complete graph with 6 vertices.

   (a)

   How many edges does $K$ have?

   [1 mark]

   • A$12$
   • B$30$
   • C$15$
   • D$36$

   (b)

   What is the degree of each vertex of $K$?

   [1 mark]

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

   (c)

   A spanning tree of $K$ is formed by deleting edges. State the number of edges in the spanning tree and the number of edges deleted.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   A graph $H$ has vertices $P, Q, R, S, T, U$ and edges $PQ$, $QR$, $RS$, $ST$, $TU$, $UP$ and $QT$.

   (a)

   (i) Write down a cycle in $H$ that contains exactly four vertices.
   (ii) Write down a walk in $H$ of five edges that is not a path.

   [3 marks]

   (b)

   (i) State the number of edges in a spanning tree of $H$, and hence the number of edges that must be removed from $H$ to form one.
   (ii) List the edges of one spanning tree of $H$.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   A network of 8 computers is modelled by a connected graph $G$. Each vertex represents a computer and each edge represents a cable. No computer is joined to itself and each pair of computers is joined by at most one cable.

   (a)

   The network has 10 cables.
   (i) Find the sum of the degrees of the vertices and the mean degree.
   (ii) Explain why $G$ cannot have exactly three vertices of odd degree.
   (iii) Show that $G$ contains a cycle, and find the number of cables that must be removed to leave a spanning tree.

   [6 marks]

   (b)

   (i) Find the number of cables in the complete graph on the 8 computers, and the degree of each vertex.
   (ii) A technician claims that if every vertex of $G$ has degree 3 then $G$ is a tree. Show that the claim is false.
   (iii) Explain why a tree with 8 vertices must have at least one vertex of degree 1.

   [6 marks]

   Total for question 4: 12 marks

End of questions