Network in Graph Theory · Form 4
Network in Graph Theory: Practice Questions
Original SPM-style practice questions for Network in Graph Theory, each with full worked solutions, Paper 1 multiple-choice and Paper 2 structured.
Original practice questions for Network in Graph Theory, in the style of Mathematics Paper 1 (Objective) and Mathematics Paper 2 (Subjective). Each answer is worked so you can check your method, not just the result.
Multiple-choice (Paper 1 style)
Question 1
A graph has 8 edges. What is the sum of the degrees of all its vertices?
- A. 8
- B. 16
- C. 32
- D. 64
Question 2
A graph has vertices with degrees 3, 3, 2, 2 and 2. How many edges does the graph have?
- A. 5
- B. 6
- C. 7
- D. 12
Question 3
In any graph, the number of vertices with an odd degree must be even. Which of the following cannot be the number of odd-degree vertices in a graph?
- A. 0
- B. 2
- C. 3
- D. 4
Question 4
A directed network has 10 arcs (directed edges). What is the sum of the in-degrees of all its vertices?
- A. 5
- B. 10
- C. 20
- D. 100
Question 5
A loop at a vertex contributes how much to the degree of that vertex?
- A. 0
- B. 1
- C. 2
- D. 3
Question 6
A weighted network connects towns P, Q, R and S with these road lengths: P–Q = 5 km, P–R = 3 km, R–Q = 1 km, Q–S = 4 km, R–S = 6 km. What is the length of the shortest route from P to S?
- A. 7 km
- B. 8 km
- C. 9 km
- D. 12 km
Question 7
In a complete graph with 5 vertices, every vertex is joined to every other vertex by exactly one edge. How many edges does it have?
- A. 5
- B. 10
- C. 20
- D. 25
Question 8
A tree is a connected graph with no cycles. A tree with 7 vertices has how many edges?
- A. 5
- B. 6
- C. 7
- D. 8
Question 9
What is the name given to a vertex with degree 0 in a graph?
- A. A loop
- B. An isolated vertex
- C. A complete vertex
- D. A weighted vertex
Question 10
Which term describes a graph in which each edge is assigned a numerical value such as distance, time or cost?
- A. A simple graph
- B. A weighted graph
- C. A directed graph
- D. A complete graph
Structured (Paper 2 style)
Question 1 (5 marks)
A network graph G has six vertices A, B, C, D, E and F with degrees A = 4, B = 3, C = 3, D = 2, E = 2 and F = 2. (a) Find the sum of the degrees of all the vertices.
(b) Hence, find the number of edges of G. (c) State, with a reason, whether such a graph can be drawn.
- (a) Sum of degrees = 4 + 3 + 3 + 2 + 2 + 2 = 16.
- (b) Number of edges = sum of degrees ÷ 2 = 16 ÷ 2 = 8.
- (c) Only two vertices (B and C) have an odd degree; since the number of odd-degree vertices (2) is even, the graph can be drawn.
Question 2 (4 marks)
A weighted network shows the roads between five towns P, Q, R, S and T, with distances in km: P–Q = 8, P–R = 5, Q–R = 3, Q–S = 6, R–T = 7, S–T = 4. (a) List all possible routes from P to T and their total lengths.
(b) Hence, determine the shortest route from P to T and state its length.
- Route P–R–T: 5 + 7 = 12 km.
- Route P–Q–R–T: 8 + 3 + 7 = 18 km.
- Route P–Q–S–T: 8 + 6 + 4 = 18 km.
- Route P–R–Q–S–T: 5 + 3 + 6 + 4 = 18 km.
- Comparing all routes, the smallest total length is 12 km.
Question 3 (6 marks)
A directed network models the one-way streets between four junctions A, B, C and D. The arcs are A→B, A→C, B→C, C→D, D→A and D→B.
(a) Write down the out-degree of each junction. (b) Write down the in-degree of each junction.
(c) Show that the sum of the out-degrees equals the sum of the in-degrees, and state what this total represents.
- (a) Out-degrees: A → B and A → C give A = 2; B → C gives B = 1; C → D gives C = 1; D → A and D → B give D = 2.
- (b) In-degrees: D → A gives A = 1; A → B and D → B give B = 2; A → C and B → C give C = 2; C → D gives D = 1.
- (c) Sum of out-degrees = 2 + 1 + 1 + 2 = 6; sum of in-degrees = 1 + 2 + 2 + 1 = 6; both equal the number of arcs, which is 6.
Question 4 (5 marks)
In a chess tournament, 7 players each play exactly one game against every other player. This is modelled by a graph in which the vertices are players and each edge is a game played.
(a) State the degree of each vertex and give a reason. (b) Find the sum of the degrees of all the vertices.
(c) Hence, find the total number of games played.
- (a) Each player plays against the other 6 players, so every vertex has degree 6.
- (b) Sum of degrees = 7 × 6 = 42.
- (c) Number of edges = sum of degrees ÷ 2 = 42 ÷ 2 = 21, so 21 games are played. (Check: n(n−1)/2 = 7 × 6 ÷ 2 = 21.)
Source:SPM: Format Pentaksiran mulai 2021, Matematik (1449)
Frequently asked questions
How do Paper 1 and Paper 2 questions differ in this network in graph theory set?
Paper 1 questions are multiple-choice, testing quick reading of vertices, edges, and degree from a small network diagram, plus recognising directed versus undirected or weighted versus unweighted networks. Paper 2 questions ask you to draw a network from given information, identify subgraphs or trees, and total the weights along a route with full working shown.
Why should I attempt each network question before checking the worked solution?
Reading a network diagram correctly, counting degree, following edge directions, adding every weight along a route, takes practice under time pressure. Attempting the question yourself first shows whether you can build and read that network independently, rather than just following logic that already looks obvious in a finished diagram.
What common mistakes do students make with network in graph theory questions?
Students often miscount a vertex's degree when edges are drawn too close together, ignore the direction of a directed edge, or forget to add every weight along a route. This practice set is built to surface those slips before the real exam.