Further Mathematics · AQA 7367 · Option D · Topic DA

Graphs

Graph theory: vertices, edges, degrees, Eulerian and Hamiltonian graphs, planarity and isomorphism.

  • 7 sub-topics
  • 5 in Year 12, 2 in Year 13
  • 85 practice questions
  • 7 animated lessons
Practice questions (85) Lessons Worksheets All AQA Further Mathematics topics

What the specification says

Every sub-topic AQA can examine in this topic, with its reference number from the official specification. The Y12 and Y13 tags show when each sub-topic is usually taught.

  1. DA1Language of graphs: vertex, edge, trail, cycle, degree, subgraphY12
  2. DA2Eulerian, semi-Eulerian and Hamiltonian graphsY12
  3. DA3Euler's formula for connected planar graphsY12
  4. DA4Kuratowski's theoremY13
  5. DA5Complete and bipartite graphs, adjacency matrices and complementsY12
  6. DA6Simple graphs, connected graphs and treesY12
  7. DA7Isomorphism between graphsY13

Try 3 questions

Easy, medium and hard questions from this topic, each with a worked solutions and the mark for every step. All 85 questions in this topic, free, no account needed.

Algorithms and graph theory

Easy

Graph theory · Year 12 · 5 marks

A connected graph GG has six vertices, AA to FF, with degrees AA: 3, BB: 2, CC: 4, DD: 3, EE: 4, FF: 4.
  1. (a)
    Find the number of edges in GG.
    (2)
  2. (b)
    State, with a reason, whether GG is Eulerian, semi-Eulerian or neither.
    (2)
  3. (c)
    Find the number of edges in the complete graph on six vertices.
    (1)

Check your answer before you look at the solution

Show worked solutionHide worked solution

Part (a)2 marks

  1. Each edge adds 2 to the total of the degrees.∑deg⁡=20\sum \deg = 20
  2. edges=10\text{edges} = 10

Part (b)2 marks

  1. Odd vertices: AA, DD.
  2. 0 odd: Eulerian; 2 odd: semi-Eulerian.GG is semi-Eulerian.

Part (c)1 mark

  1. 6×52=15\tfrac{6 \times 5}{2} = 15

Total5

  • M
  • A
  • B
How did it go?

Report a problem with this question

Graphs

Medium

Euler's formula · Year 12 · 5 marks

A connected planar graph has 8 vertices and 12 edges.
  1. (a)
    Use Euler's formula to find the number of faces.
    (2)
  2. (b)
    Show that a simple connected planar graph with V≥3V \ge 3 vertices has at most 3V−63V - 6 edges, and use it to show that K5K_5 is not planar.
    (3)

Check your answer before you look at the solution

Show worked solutionHide worked solution

Part (a)2 marks

  1. V−E+F=2V - E + F = 2
  2. The outer face counts.F=6F = 6

Part (b)3 marks

  1. Each face has at least 3 edges and each edge borders at most 2 faces.3F≤2E3F \leq 2E
  2. Substitute F=2−V+EF = 2 - V + E.E≤3V−6E \leq 3V - 6
  3. K5: 10>3(5)−6=9K_5: \ 10 > 3(5) - 6 = 9

Total5

  • M
  • A
  • B
How did it go?

Report a problem with this question

Graphs

Not needed for Year 12Hard

The planarity algorithm · Year 13 · 5 marks

A graph has the Hamiltonian cycle ABCDEFA and the four further edges BF, CF, AD, AC.
  1. (a)
    Explain what is meant by a Hamiltonian cycle.
    (1)
  2. (b)
    Use the planarity algorithm to determine whether the graph is planar.
    (4)
Show worked solutionHide worked solution

Part (a)1 mark

  1. A cycle that visits every vertex exactly once and returns to the start.

Part (b)4 marks

  1. Draw the Hamiltonian cycle as a polygon; the other edges must go inside or outside it.
  2. Two chords cross if their end vertices alternate round the cycle.Crossing pairs: BF and AD, BF and AC, CF and AD.
  3. Inside: AD, AC; outside: BF, CF. No crossings remain, so the graph is planar.

Total5

  • M
  • A
  • B
How did it go?

Report a problem with this question