Networks and graphsIB MYP Maths Extended: Subtopic test

1. 1
   A network has four vertices $A$, $B$, $C$ and $D$. The edges are $AB$, $AC$, $AD$ and $BC$. Each edge joins two different vertices, and no two vertices are joined by more than one edge.

   (a)

   What is the degree of vertex $A$?

   [1 mark]

   • A1
   • B2
   • C3
   • D4

   (b)

   What is the sum of the degrees of all four vertices?

   [1 mark]

   • A4
   • B8
   • C6
   • D16

   (c)

   Write down the adjacency matrix of the network, with the vertices in the order $A$, $B$, $C$, $D$.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   Five towns $P$, $Q$, $R$, $S$ and $T$ are joined by roads. The road lengths in km are $PQ=4$, $PR=7$, $QR=2$, $QS=6$, $RS=3$, $RT=9$ and $ST=5$. There are no other roads, and a route may not visit the same town twice.

   (a)

   What is the degree of town $R$?

   [1 mark]

   • A2
   • B3
   • C5
   • D4

   (b)

   How many different routes are there from $P$ to $T$?

   [1 mark]

   • A7
   • B5
   • C6
   • D8

   (c)

   Find the shortest route from $P$ to $T$ and state its length.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   A complete network $K_n$ has $n$ vertices, with every pair of vertices joined by exactly one edge. $K_3$ has 3 edges, $K_4$ has 6 edges and $K_5$ has 10 edges. An Euler circuit is a route that starts and ends at the same vertex and uses every edge exactly once. A connected network has an Euler circuit if and only if every vertex has even degree.

   (a)

   Describe the pattern in the number of edges of $K_n$ and write a general rule for the number of edges in terms of $n$. Check your rule using $K_5$ and predict the number of edges of $K_6$.

   [3 marks]

   (b)

   For which values of $n$ does $K_n$ have an Euler circuit? Justify your answer and state the result for $K_5$ and $K_6$.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   A ferry company links four islands $A$, $B$, $C$ and $D$ with the direct routes $AB$, $AC$, $BC$ and $CD$. Every route can be used in either direction, and a tourist is planning a holiday using these ferries.

   (a)

   (i) Write down the adjacency matrix $\mathbf M$ for the network, with the islands in the order $A$, $B$, $C$, $D$.
   (ii) Find $\mathbf M^2$.
   (iii) Use $\mathbf M^2$ to find the number of journeys that start at $C$ and finish at $C$ using exactly two ferries, and list these journeys.

   [6 marks]

   (b)

   The tourist would like (i) to use every ferry route exactly once and (ii) to visit every island exactly once. Evaluate whether each plan is possible, and whether the tourist can finish at the island where they started.

   [6 marks]

   Total for question 4: 12 marks

End of questions