Edexcel International A Level Maths
Graph theory terminology
Total 27 marks
Name
Class
Date
- 1A graph has vertices and edges , , , and .(a)What is the degree of vertex ?[1 mark]
- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: B(b)Which of the following is a cycle in ?[1 mark]- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: A(c)State, with a reason, whether is a tree.[2 marks]Show the mark scheme
Mark scheme
B1: it is not a tree
B1: it contains a cycle (), or it has 5 edges but a tree on 5 vertices has only 4Total for question 1: 4 marks
- 2is the complete graph with 6 vertices.(a)How many edges does have?[1 mark]
- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: C(b)What is the degree of each vertex of ?[1 mark]- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: D(c)A spanning tree of is formed by deleting edges. State the number of edges in the spanning tree and the number of edges deleted.[2 marks]Show the mark scheme
Mark scheme
B1: edges in the spanning tree (6 vertices, so )
B1: edges deleted
Accept: follow-through from their number of edges inTotal for question 2: 4 marks
- 3A graph has vertices and edges , , , , , and .(a)(i) Write down a cycle in that contains exactly four vertices.[3 marks]
(ii) Write down a walk in of five edges that is not a path.Show the mark scheme
Mark scheme
B1: (i) or
M1: (ii) a walk of five edges, each an edge of , with consecutive edges sharing a vertex
A1: (ii) a vertex repeated, so it is not a path, e.g.
Accept: any valid walk that repeats a vertex or edge(b)(i) State the number of edges in a spanning tree of , and hence the number of edges that must be removed from to form one.[4 marks]
(ii) List the edges of one spanning tree of .Show the mark scheme
Mark scheme
B1: (i) edges in a spanning tree
B1: (i) edges removed
M1: (ii) five edges of that include all six vertices
A1: (ii) connected with no cycle, e.g.
Accept: any valid spanning tree ofTotal for question 3: 7 marks
- 4A network of 8 computers is modelled by a connected graph . 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.[6 marks]
(i) Find the sum of the degrees of the vertices and the mean degree.
(ii) Explain why cannot have exactly three vertices of odd degree.
(iii) Show that contains a cycle, and find the number of cables that must be removed to leave a spanning tree.Show the mark scheme
Mark scheme
B1: (i) sum of degrees
B1: (i) mean degree
B1: (ii) the sum of the degrees is twice the number of edges, so it is even
B1: (ii) with exactly three odd degrees the sum would be odd, which is impossible
M1: (iii) a tree on 8 vertices has 7 edges, and has edges
A1: (iii) so contains a cycle, and cables are removed(b)(i) Find the number of cables in the complete graph on the 8 computers, and the degree of each vertex.[6 marks]
(ii) A technician claims that if every vertex of has degree 3 then 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.Show the mark scheme
Mark scheme
B1: (i) cables
B1: (i) degree
M1: (ii) sum of degrees , so edges
A1: (ii) a tree on 8 vertices has 7 edges, so is not a tree
M1: (iii) a tree has 7 edges, so the degrees sum to
A1: (iii) if every degree were at least 2 the sum would be at least , so some vertex has degree 1 (degree 0 is impossible as the tree is connected)Total for question 4: 12 marks
End of questions