Year 10 Networks Worksheets & Practice

Worked examples

Year 10 networks: worked examples

Three examples, from a standard question to a worded problem. Have a go at each one before you open the solution.

1. Example 1 · Vertices, edges and degree

   A network has five vertices: A, B, C, D and E. The edges are: A, B, A, C, B, C, B, D, and D, E. State the number of vertices, the number of edges, and the degree of each vertex.

   Show worked solution

   Key idea: The degree of a vertex is the number of edges connected to it. The sum of all degrees equals twice the number of edges.

   1. Count the vertices: A, B, C, D, E gives 5 vertices.
   2. Count the edges: A, B, A, C, B, C, B, D, D, E gives 5 edges.
   3. Find the degree of each vertex by counting how many edges meet it:

   • A appears in A, B and A, C: $\deg(A) = 2$
   • B appears in A, B, B, C and B, D: $\deg(B) = 3$
   • C appears in A, C and B, C: $\deg(C) = 2$
   • D appears in B, D and D, E: $\deg(D) = 2$
   • E appears in D, E: $\deg(E) = 1$

   4. Check: sum of degrees $= 2 + 3 + 2 + 2 + 1 = 10 = 2 \times 5$ ✓

   Answer: 5 vertices, 5 edges; $\deg(A)=2,\; \deg(B)=3,\; \deg(C)=2,\; \deg(D)=2,\; \deg(E)=1$.

2. Example 2 · Eulerian paths and connectedness

   A network has six vertices: P, Q, R, S, T and U. The edges are: P, Q, P, R, Q, R, Q, S, R, T, S, T, S, U and T, U. (a) State the degree of each vertex and determine whether the network is connected. (b) Determine whether an Eulerian path exists. If it does, state a valid starting and finishing vertex.

   Show worked solution

   Key idea: An Eulerian path (which travels every edge exactly once) exists if and only if the network is connected and has exactly 0 or 2 vertices of odd degree. With 0 odd-degree vertices, the path is a circuit (starts and ends at the same vertex); with exactly 2, it starts at one odd-degree vertex and ends at the other.

   1. Find the degree of each vertex:
      $\begin{aligned} \deg(P) &= 2 (\text{P, Q, P, R})\\ \deg(Q) &= 3 (\text{P, Q, Q, R, Q, S})\\ \deg(R) &= 3 (\text{P, R, Q, R, R, T})\\ \deg(S) &= 3 (\text{Q, S, S, T, S, U})\\ \deg(T) &= 3 (\text{R, T, S, T, T, U})\\ \deg(U) &= 2 (\text{S, U, T, U}) \end{aligned}$
   2. Check connectivity: every vertex can be reached from every other vertex by tracing the edges, so the network is connected.
   3. Identify odd-degree vertices: Q, R, S and T each have degree 3, that is 4 odd-degree vertices.
   4. Because there are more than 2 odd-degree vertices, no Eulerian path exists.

   Answer: The network is connected. The odd-degree vertices are Q, R, S and T (four in total), so no Eulerian path exists.

3. Example 3 · Shortest path in a weighted network

   A parks ranger needs to travel between five rest stops in a national park. The rest stops are labelled A, B, C, D and E. The walking trail distances in kilometres between them are: A, B: 3 km, A, C: 7 km, B, C: 2 km, B, D: 5 km, C, E: 4 km and D, E: 6 km. The ranger starts at A and must reach E. Find the shortest total distance the ranger can walk, and state the route.

   Show worked solution

   Key idea: In a weighted network, the shortest path is found by comparing the total weights of all possible routes between the two vertices.

   1. List all routes from A to E and calculate their total distances:
      $\begin{aligned} \text{A} \to \text{B} \to \text{C} \to \text{E} &= 3 + 2 + 4 = 9 \text{ km}\\ \text{A} \to \text{B} \to \text{D} \to \text{E} &= 3 + 5 + 6 = 14 \text{ km}\\ \text{A} \to \text{C} \to \text{E} &= 7 + 4 = 11 \text{ km} \end{aligned}$
   2. Compare: $9 < 11 < 14$, so the shortest route is A $\to$ B $\to$ C $\to$ E.
   3. Check: $3 + 2 + 4 = 9$ km ✓

   Answer: The shortest route is A $\to$ B $\to$ C $\to$ E, with a total distance of 9 km.

Common mistakes

Where students usually lose marks

Try one yourself

Your turn

Got a different networks question wrong? Upload it to Tuterly and get the worked solution and a fresh one to practise, free.