Covers Lessons 1–6: network terminology, paths and cycles, Eulerian trails and circuits, Hamiltonian routes, and trees.
Multiple Choice
10 questions drawn from Lessons 1–6
Short Answer
1. A network has vertices A, B, C, D, E with edges AB, BC, CD, DE, EA, AC, CE. (a) Find the degree of each vertex. (b) Does it have an Eulerian circuit? (c) Does it have an Eulerian trail? (d) Find a Hamiltonian cycle. 3 MARKS
2. (a) How many edges in K₆? (b) How many edges in a tree with 9 vertices? (c) A connected network has 8 vertices and 11 edges. How many edges must be removed to form a spanning tree? 2 MARKS
3. (a) Explain the difference between an Eulerian trail and a Hamiltonian path. (b) A network has degrees 2, 2, 2, 3, 3, 4. Can you draw it without lifting your pen? If yes, where do you start and finish? (c) A tree has 7 vertices. What is the maximum possible degree of any vertex? Draw an example. 3 MARKS
Q1 (3 marks): (a) All degrees correct [0.5]. (b) No [0.5]. (c) Yes [0.5]. (d) Valid cycle [1.5].
Q2 (2 marks): (a) 15 [0.5]. (b) 8 [0.5]. (c) 4 [1].
Q3 (3 marks): (a) Clear distinction [1]. (b) Yes, start/finish at odd vertices [1]. (c) 6, diagram [1].
Tick when you have finished all questions and checked your answers.