Contents · 0% complete

Learning objectives
Core idea
Key formulae
Worked examples
Explore the graph
Common mistakes
Exam tip
Guided practice
Practice questions
Challenge
Summary
Quick quiz
Same topic, different board
Past paper questions

Learn7367Paper 3 · Discrete optionGraphsGraphs and their properties

Graphs · Subtopic 1 of 1

Graph Theory

A graph is vertices joined by edges. The sum of the degrees is twice the number of edges (handshaking lemma), so the number of odd vertices is even. A connected graph is Eulerian if every vertex has even degree; a connected planar graph satisfies $V-E+F=2$ .

Edexcel 9FM0 OptionAQA 7367 Paper 3≈ 40 minRevision 1 · updated 2026-10-27

Practise this topicTimed test Ask Salam TutorSwitch board

Section 1 of 14

Learning objectives

Use graph terminology precisely.
Apply the handshaking lemma.
Recognise trees, complete graphs $K_n$ and bipartite graphs $K_{m,n}$ .
Decide whether a graph is Eulerian; use Euler's formula for planar graphs.

Pause and think

Can you draw a figure with exactly three vertices of odd degree?

Section 2 of 14

Core idea

Start hereSeven bridges

The citizens of Königsberg wondered whether they could walk across each of their seven bridges exactly once and get home. Euler realised only the connections mattered, not the distances, and in answering invented graph theory.

The big idea

A graph is vertices joined by edges. Counting degrees gives the handshaking lemma $\sum\deg=2E$ ; the parity of degrees decides whether an Eulerian trail exists; and planar graphs obey $V-E+F=2$ .

1. Degrees

The handshaking lemma

$\text{each edge has two ends}$
An edge joins two vertices (a loop meets one vertex twice).
$\sum\deg(v)=2E$
Summing degrees counts every end once.
$\#\text{odd vertices is even}$
An even total needs an even number of odd terms.

Worked exampleCan this graph exist?

Is there a graph with degrees $3,3,3,2,2$ ?

Goal: Yes or no.
Strategy: Handshaking.

$3+3+3+2+2=13$
Sum of degrees.
$13\ \text{is odd}$
Must equal $2E$ .

AnswerNo such graph exists.

✓ CheckThree odd vertices, an odd number ✓ (impossible).

2. Eulerian and planar graphs

V-E+F=2\qquad K_n:\tfrac12n(n-1)\ \text{edges}

$F$: faces, including the outer one.

Worked examplePlanarity bound

Show $K_5$ is not planar.

Goal: Contradiction.
Strategy: Each face has $\ge3$ edges, each edge borders $\le2$ faces.

$3F\le2E$
Count edge–face incidences.
$E\le3V-6$
Substitute $F=2-V+E$ .
$10\le9\ ?$
$K_5$ : $E=10$ , $V=5$ .

AnswerFalse, so

K_5

is not planar.

✓ CheckAny drawing of

K_5

needs at least one crossing ✓.

Eulerian test

Drawing diagram…

Count odd vertices to decide.

Common misconceptionEuler vs Hamilton Eulerian: every edge once. Hamiltonian: every vertex once.

Key takeawayTrees A tree is connected with no cycles; it always has

E=V-1

Pause and think

Is $K_4$ Eulerian?

Summary

$\sum\deg=2E$ .
Eulerian: all even.
$V-E+F=2$ ; $E\le3V-6$ .

Degree: Number of edge-ends at a vertex.
Planar: Drawable with no crossing edges.
Bipartite: Vertices in two sets, edges only between sets.

HistoryBridges of Königsberg. In 1736 Euler proved you can't cross Königsberg's seven bridges once each and return home: all four land masses had odd degree. Graph theory was born.

Fun factSix degrees. Facebook found in 2016 that any two users are linked by an average of about 3.5 intermediate friends: graph distances in a network of billions.

Section 3 of 14

Key formulae

Handshaking

\sum\deg(v)=2E

Special graphs

K_n:\ \tfrac12n(n-1)\text{ edges};\ K_{m,n}:\ mn;\ \text{tree}: E=V-1

Euler's formula

V-E+F=2\ \ (\text{connected planar})

TrickEulerian check. Count odd vertices:

0

→ Eulerian (closed trail),

2

→ semi-Eulerian (start and end at the odd ones), more → neither.

Section 4 of 14

Worked examples

Example 1 · Handshaking0 / 2 steps

A graph has degrees

3,3,2,2,4

. How many edges?

Example 2 · Euler0 / 2 steps

A connected planar graph has

6

vertices and

9

edges. How many faces?

Section 5 of 14

Explore the graph

A network

Loading the interactive graph…

Try this

Vertices: $A(0,2)$ , $B(2,4)$ , $C(2,0)$ , $D(4,4)$ , $E(5,1)$ . Weights: $AB=4$ , $AC=3$ , $BC=2$ , $BD=5$ , $CD=6$ , $CE=7$ , $DE=3$ .
Degrees: $A2$ , $B3$ , $C4$ , $D3$ , $E2$ . Two odd vertices, so semi-Eulerian.

Sum of degrees $14=2\times7$ edges.

In the real worldSocial networks. Recommendation engines treat people as vertices and friendships as edges: high-degree vertices are "influencers".

Section 6 of 14

Common mistakes

IncorrectForgetting the outer face

CorrectCount it

Euler's formula includes the infinite face.

IncorrectEulerian means visits every vertex

CorrectUses every edge once

Visiting every vertex once is Hamiltonian.

IncorrectLoops add 1 to degree

CorrectAdd 2

Both ends meet the vertex.

Königsberg residents: let's walk each bridge once

Euler: four odd vertices. No.

Section 7 of 14

Exam tip

Exam tipTabulate degrees. List every vertex with its degree before answering Eulerian or handshaking questions.

Section 8 of 14

Guided practice

SA-DM-GR-G011 markL1 FoundationNon-calculatorTerminology

A graph has vertex degrees

3,3,2,2,4

. How many edges does it have?

Salam Academy Original Practice · Proposed mark scheme

Section 9 of 14

Practice questions

SA-DM-GR-0011 markL1 FoundationNon-calculatorTypes of graph

How many edges does

K_6

have?

Salam Academy Original Practice · Proposed mark scheme

SA-DM-GR-0021 markL1 FoundationNon-calculatorTypes of graph

How many edges does

K_{3,4}

have?

Salam Academy Original Practice · Proposed mark scheme

SA-DM-GR-0032 marksL2 StandardNon-calculatorEuler

A connected planar graph has

6

vertices and

9

edges. How many faces does it have?

Salam Academy Original Practice · Proposed mark scheme

SA-DM-GR-0041 markL1 FoundationNon-calculatorTypes of graph

How many edges does a tree with

10

vertices have?

Salam Academy Original Practice · Proposed mark scheme

More questions on every skill in this subtopic are in the question bank under Practise.

Section 10 of 14

Challenge

SA-DM-GR-0052 marksL3 ExamNon-calculatorEuler

A simple connected planar graph has every face bounded by at least 3 edges, so

3F\le2E

. Use Euler's formula to find the greatest number of edges possible with

5

vertices.

Salam Academy Original Practice · Proposed mark scheme

Section 11 of 14

Summary

$\sum\deg=2E$ .
$K_n$ , $K_{m,n}$ , trees.
Eulerian: all even.
$V-E+F=2$ .

Section 12 of 14

Quick quiz

Q1 · SA-DM-GR-Q011 markL1 FoundationNon-calculatorEuler

A connected graph has exactly two odd vertices. It is

Salam Academy Original Practice · Proposed mark scheme

Section 13 of 14

Same topic, different board

Specification: 7367 A-level Further Mathematics
Where: Discrete · Graphs
Expected: Graph terminology; simple, connected, complete, bipartite and planar graphs; Euler’s formula; Eulerian and semi-Eulerian graphs; Hamiltonian cycles; isomorphism; adjacency matrices.
Calculator: Permitted on all papers.
Typical style: AQA mixes short multiple-choice questions with longer structured ones.
Open in: 7367 · Paper 3

Section 14 of 14

Past paper questions

No past paper questions are tagged to this subtopic yet. We add papers every week.

Browse past papers

Salam Academy original content · Content status: reviewed and published. Syllabus mapping: AQA 7367, First teaching 2017 (official specification).