Vertices, edges, degree, paths, cycles, trees, connected and complete graphs, adjacency and distance matrices, Eulerian and semi-Eulerian graphs, Hamiltonian cycles, the handshaking lemma, isomorphic graphs.
12 original questions, 60 marks. Type your answers below for an instant mark and a score (algebra in any equivalent form, e.g. 2sqrt(3) or 2√3), or print the worksheet, mark it with the answers sheet, and use the solutions to see every step written out by hand.
Show that your answers agree with the handshaking lemma, and explain why the lemma is true.
3 marks
Show answer
a) A 2, B 3, C 3, D 2, E 4, F 2b) 16 = 2 × 8; each edge adds 2 to the total degree
2
For the graph shown, write down
a path from P to S that passes through exactly two other vertices,
a cycle that passes through exactly four vertices,
a Hamiltonian cycle.
3 marks
Show answer
a) e.g. P U T S or P Q R Sb) e.g. Q R T U Qc) e.g. P Q R S T U P
3
Kn denotes the complete graph on n vertices.
Show that Kn has 12n(n − 1) edges.
Find the number of edges in K7
A simple graph has 7 vertices and 15 edges. Find how many edges must be added to make it K7
4 marks
Show answer
a) n(n - 1) ends ÷ 2b) 21c) 6
4
The diagram shows a graph with five vertices. There are two edges joining A and B.
Write down the adjacency matrix for the graph.
Explain how the degree of each vertex can be found from the matrix, and state the degree of B.
Explain why the graph is not a simple graph.
4 marks
Show answer
a) 0 2 1 0 0; 2 0 1 1 0; 1 1 0 1 0; 0 1 1 0 1; 0 0 0 1 0b) row sum; deg(B) = 4c) it has a multiple edge (A to B twice)
5
The table shows the lengths, in km, of the roads directly joining five villages A, B, C, D and E. A dash means there is no direct road.
A
B
C
D
E
A
−
12
9
−
15
B
12
−
7
10
−
C
9
7
−
8
11
D
−
10
8
−
6
E
15
−
11
6
−
Using the vertices in the diagram, draw the network, labelling each edge with its length.
Find the total length of the roads.
Write down the degree of each vertex.
4 marks
Show answer
a) AB 12, AC 9, AE 15, BC 7, BD 10, CD 8, CE 11, DE 6b) 78 kmc) A 3, B 3, C 4, D 3, E 3
6
The diagram shows three graphs.
For each graph, state whether it is Eulerian, semi-Eulerian or neither. You must justify your answers.
For the semi-Eulerian graph, state where a route that uses every edge exactly once must start and finish, and write down such a route.
5 marks
Show answer
a) Graph 1 neither, Graph 2 semi-Eulerian, Graph 3 Eulerianb) A to B, e.g. A E B A D C B
7
This question is about the degrees of vertices.
Explain why there is no graph whose vertices have degrees 1, 2, 2, 3, 3, 4 and 4
A tree T has seven vertices. The degrees of the vertices are
1 1 1 1 x 2x − 3 x − 1
State the number of edges in T.
Find the value of x.
State, with a reason, whether T is Eulerian, semi-Eulerian or neither.
Explain why no tree with more than one vertex can be Eulerian.
6 marks
Show answer
a) sum 19 is oddb) 6c) 3d) neither: 6 odd verticese) a tree has vertices of degree 1 (odd)
8
The diagram shows three graphs G, H and I, each with six vertices and seven edges.
Show that G and H are isomorphic by writing down which vertex of H corresponds to each vertex of G.
Explain why I is not isomorphic to G, even though both graphs have the same degrees.
5 marks
Show answer
a) A-P, B-R, C-T, D-Q, E-S, F-Ub) I has a 3-cycle, G does not
9
The diagram shows a graph. Ignore the dashed edge CG in part (a).
Explain why the graph without CG has no Hamiltonian cycle.
The edge CG is added. Find a Hamiltonian cycle starting at A.
State, with a reason, whether the graph with CG added is Eulerian, semi-Eulerian or neither.
5 marks
Show answer
a) G has degree 1b) A B C G D E F Ac) neither: odd vertices B, C, D, F
10
The network shows the footpaths in a country park. The vertices are the car park (C), lake (L), mill (M), tower (T), wood (W) and bridge (B). The weights are the lengths of the paths in km.
Find the total length of the footpaths.
Explain why the network is semi-Eulerian.
A ranger wants to walk along every path exactly once. State where she must start and finish, and write down a suitable route.
One path is to be closed so that the ranger can walk along every remaining path exactly once and return to her starting point. State which path, and the length of her walk.
7 marks
Show answer
a) 8.3 kmb) exactly two odd vertices, L and Wc) L to W, e.g. L C B W T M L Wd) LW, 7 km
11
The graph shown has six vertices and nine edges.
State the number of edges in a spanning tree of this graph, and hence the number of edges that must be removed to leave a spanning tree.
Write down the edges of a spanning tree in which vertex A has degree 5
Write down the edges of a spanning tree that is a path, starting at B and ending at A.
Explain why there is no spanning tree in which every vertex has degree at most 1
6 marks
Show answer
a) 5 edges, remove 4b) AB, AC, AD, AE, AFc) BC, CD, DE, EF, FAd) degree sum must be 10 but would be at most 6
12
This question is about the complete graphs Kn, where n ≥ 3
Explain why Kn is Eulerian when n is odd and is neither Eulerian nor semi-Eulerian when n is even.
Find the smallest number of edges that must be removed from K8 to leave an Eulerian graph, and describe which edges could be removed.
Find the number of edges in the graph left in part (b).
The vertices of K8 are labelled 1 to 8 and the edges 12, 34, 56 and 78 are removed. Write down a Hamiltonian cycle in the graph that is left.
8 marks
Show answer
a) degree n - 1: even for odd n; n even gives n odd verticesb) 4 edges, no two sharing a vertexc) 24d) e.g. 1 3 5 7 2 4 6 8 1
Your score
Answer the questions above and your score appears here.
Every question here is original and written by Robinson Tuition. It follows the Edexcel AS Further Mathematics specification and suits AQA and OCR Further Maths too; this is not an exam-board paper.