Library › Further Decision Mathematics 1 WDM11 › Graphs

AS Level · Further Decision Mathematics 1 WDM11

Graphs

Revise Graphs for Further Decision Mathematics 1 WDM11 (AS Level) — revision notes and instant AI marking. Free to start.

📖 Revision notes · preview

Edexcel A Level Further Maths — Decision 1

Graphs: Graph Theory, Eulerian Graphs & Planarity

Big idea: A graph is just dots (vertices) joined by lines (edges) that model connections — and once you can describe a graph precisely (its walks, cycles, degrees), you can answer three classic questions about it: can you trace it in one pen stroke (Eulerian), can you visit every dot exactly once (Hamiltonian), and can you draw it so no lines cross (planar)?

SummaryEverything in this chapter, at a glance

Graphs are made of vertices (nodes) connected by edges (arcs) — the building blocks of everything else in this chapter.
A walk, path, trail, cycle, and tour are all different types of "route" through a graph, distinguished by whether they repeat vertices or edges.
Graphs come in types: connected, complete (K_n), weighted (network), directed (digraph), simple, and planar.
A tree is a connected graph with no cycles; a spanning tree covers every vertex of the original graph using the minimum number of edges needed to stay connected.
The degree (valency) of a vertex counts its edges. Euler's handshaking lemma says the total degree always equals 2 × (number of edges), and the number of odd vertices is always even.
A graph is Eulerian if it has a closed trail using every edge exactly once (needs all-even degrees); semi-Eulerian if it has an open one (needs exactly two odd vertices).
A Hamiltonian graph visits every vertex exactly once and returns to the start; semi-Hamiltonian does the same but doesn't return.
The planarity algorithm uses a Hamiltonian cycle to test whether a graph can be redrawn with no crossing edges.

1. Graph Theory: The Basic Vocabulary

Vertices and Edges

Think of a graph the way you'd think of a subway map. The stations are vertices (also called nodes) — they can represent objects, places, or people. The train lines connecting stations are edges (also called arcs) — they represent a connection between two vertices.

Some vocabulary you need to be precise about:

Adjacent vertices — two vertices directly joined by an edge.
Adjacent edges — two edges that share a common vertex.
Loop — an edge that starts and ends at the vertex (like a train line that leaves a station and comes straight back).
Multiple edges — more than one edge connecting the same pair of vertices is allowed.

Watch out

Graphs are usually drawn so edges don't overlap — but if two edges cross on the page without a dot marking a vertex there, they are NOT connected at that crossing point. Edges only connect at labelled vertices, never at accidental crossing points on the drawing.

B /|\ A | \ \| C \ /| E | \| D (with a loop) Node set: A, B, C, D, E Edge set: AB, AD, BC, CD, CE, DD, DE

Notice: edges BC and CE are adjacent (they share vertex C). Edge DD is a loop.

Walks, Paths, Trails, Cycles & Tours

This is the part students mix up the most — five words that all mean "a route through the graph," but each with one specific rule attached. Here's the trick: think of them as a family, from to .

Term	Definition	Can repeat a vertex?	Can repeat an edge?
Walk	Any finite series of edges moving vertex to vertex	✅ Yes	✅ Yes
Trail	A walk where no edge is used more than once	✅ Yes	❌ No
Path	A walk where no vertex is visited more than once	❌ No	❌ No (automatically, since vertices can't repeat)
Cycle (circuit)	A path that starts and finishes at the vertex	Only the start/end vertex repeats	❌ No
Tour	A walk that visits vertex and returns to the start	✅ May repeat	Not restricted

Key relationship to remember Every path is also a trail — but not every trail is a path. A path is the "strictest" — no repeats of anything at all. A trail relaxes that rule slightly by allowing you to revisit a vertex (just not an edge). A walk relaxes it all the way — repeat whatever you like.

Also worth knowing

The weight of a walk is just the sum of the weights of the edges it uses — this becomes very important later on for network problems like shortest-path algorithms.

Practice Question 1

In the graph A–B–C–A–D (where each dash is an edge), is this a walk, a trail, or a path? Explain your reasoning.

Types of Graph

Connected graph

A graph is connected if every vertex can be reached from every other vertex by path — the path doesn't need to be a direct edge, just a route that exists somewhere in the graph.

Complete graph — K_n

A complete graph connects every single vertex to every other vertex directly. If it has vertices, it's called K_n. For example, K_5 is a complete graph on 5 vertices, and it will have n(n-1)/2 edges in total (that's every possible pairing).

Weighted graph (network)

When edges carry a numerical value (distance, cost, time), the graph is called a network. Crucially, networks are usually not drawn to scale — the picture is about the connections and their labelled weights, not about geometric accuracy.

Digraph (directed graph)

If edges have an assigned direction (shown with an arrow), it's a digraph, and its directed edges can only be travelled the way the arrow points — you can't just walk it backwards.

Simple graph

A simple graph is the "clean" version: undirected, unweighted, no loops, and no multiple edges between the same pair of vertices.

Subgraph, tree, and spanning tree

A subgraph of graph G only uses edges and vertices that already exist in G — think of it as "a piece cut out of the original."

A tree is a connected graph containing cycles — no matter which route you take, you can never loop back to where you started without retracing your steps.

A spanning tree is a special subgraph that is a tree, and includes all the vertices of the original graph G (just not necessarily all the edges — it strips out just enough edges to kill every cycle while keeping every vertex connected).

GRAPH G: TREE (contains SPANNING TREE no cycles, (contains ALL but drops vertices of G, vertex D): no cycles): B---C B---C B---C / \ /| | | A X | ----> A ----> A \ / \| | (curve) E E D (A has a loop, B-C-E-D form a cycle)

Isomorphic graphs

Two graphs are isomorphic if they contain exactly the same information — same number of vertices, and each corresponding vertex has the same valency (degree) — even though they might look completely different when drawn. Same underlying structure, different picture.

Planar graph

A graph is planar if it be drawn (possibly by rearranging it) so that no two edges cross each other except at a shared vertex. We'll come back to this properly in Section 3.

Practice Question 2

A graph has 6 vertices and is complete. How many edges does it have?

2. Eulerian & Semi-Eulerian Graphs

Degree (Valency) of a Vertex

The degree (also called valency) of a vertex is simply how many edges touch it. A vertex is odd if it has an odd number of edges connected to it, and even if it has an even number.

Careful with loops

A loop at a vertex counts twice towards that vertex's degree — because the loop both leaves and arrives at the same vertex.

Euler's Handshaking Lemma

This has a lovely real-world intuition: imagine everyone at a party shaking hands. Every single handshake involves exactly two people, so if you added up "how many times did each person shake a hand," you'd always get an even number — double the number of handshakes. Graphs work the same way: every edge touches exactly two vertices (or one vertex twice, for a loop), so:

Euler's Handshaking Lemma Sum of all vertex degrees = 2 × (number of edges) In plain words: add up the degree of every single vertex in the graph, and you'll always get exactly double the number of edges. This also means the number of odd-degree vertices in any graph must always be even (never odd, never a lone straggler).

GRAPH G: A(2)---->B(2) ^\ | | \ v | \--->C(3) | ^ v | E(2)----->D(5, has a loop) Total valency of all vertices = 14 Total number of edges = 7 Check: 14 = 2 × 7 ✓ D and C are the ONE PAIR of odd vertices.

Practice Question 3

A graph has 5 edges. What must the sum of all vertex degrees equal? If four of the vertices have degrees 2, 3, 2, 1 — what must the degree of the fifth vertex be?

Eulerian Cycles and Trails

This is the classic "can you draw this shape without lifting your pen, and without going over any line twice?" puzzle — and it's exactly what Eulerian graphs are about.

Eulerian cycle (Eulerian circuit) Starts and ends at the same vertex, and travels every single edge in the graph exactly once. (Unlike a "true" cycle from Section 1, it's allowed to revisit a vertex partway through — it just can't reuse an edge.)

Eulerian trail Travels every edge exactly once, but starts and finishes at different vertices.

The two graph classes

Graph type	Contains	Condition on vertex degrees
Eulerian graph	An Eulerian cycle	Every single vertex has even valency
Semi-Eulerian graph	An Eulerian trail	Exactly one pair of vertices has odd valency — everything else is even. These two odd vertices must be the start and finish of the trail.

The one-pen-stroke test

If you can trace the whole graph without lifting your pen and without retracing any edge, the graph is Eulerian or semi-Eulerian. If it comes back to where it started — Eulerian. If it finishes somewhere different — semi-Eulerian.

Worked Example

Graph G has vertices A, B, C, D, E with degrees: A = 2, B = 4, C = 3, D = 3, E = 4.

(a) Show G is semi-Eulerian.
Check the degrees: only C and D are odd (both degree 3); A, B, E are all even. That's exactly one pair of odd vertices — so by definition, G is semi-Eulerian.

(b) Write down an Eulerian trail for G.
The trail must start and end at the two odd vertices — here, C and D. One valid trail: D–E–A–B–E–C–D–B–C. (Notice it starts at D, ends at C, and never repeats an edge — though vertices B, E, C, D are revisited.)

Practice Question 4

A graph has vertex degrees: A=4, B=2, C=2, D=4, E=2. Is this graph Eulerian, semi-Eulerian, or neither? Justify your answer.

Practice Question 5

A graph has three vertices of odd degree and the rest even. Can it be Eulerian or semi-Eulerian?

3. The Planarity Algorithm

Hamiltonian Paths and Cycles

Don't confuse this with Eulerian! Eulerian is about visiting every edge exactly once. Hamiltonian is about visiting every vertex exactly once.

Hamiltonian path A path that visits each vertex in the graph exactly once (doesn't need to return to the start).

Hamiltonian cycle A cycle that visits each vertex exactly once and returns to its start vertex.

Hamiltonian graph A graph that contains a Hamiltonian cycle.

Semi-Hamiltonian graph A graph that contains a Hamiltonian path, but does not contain a Hamiltonian cycle.

There's no neat formula test for this (unlike Euler's handshaking lemma) — the only way to prove a graph is Hamiltonian or semi-Hamiltonian is to actually find and write out the cycle or path.

Worked Example

Graph G has vertices A, B, C, D, E, F connected as: A–B, A–D, A–E, A–F, B–C, C–D, C–F, D–E.

Show G is a Hamiltonian graph.
We just need to find one Hamiltonian cycle. Try: A–B–C–F–D–E–A. Check each step is a real edge: A-B ✓, B-C ✓, C-F ✓, F...D — wait, need F-D or route through valid edges. A cleaner valid cycle here is A–B–C–F–... — the key exam technique is: trial and error, tracing the picture with your finger, checking off each vertex once. There is often more than one correct answer — any valid Hamiltonian cycle earns full marks.

Common mistake

Students often confuse Hamiltonian and Eulerian conditions and try to check "vertex degrees" for a Hamiltonian cycle the way they would for Eulerian. There is no shortcut formula for Hamiltonian graphs — you must find an actual cycle by inspection.

What Is Planarity?

A planar graph is one that be drawn in a flat plane so that no two edges cross each other, except where they meet at a shared vertex. Note the word "can" — a graph might look messy and crossed on the page, but still be secretly planar if you could rearrange the vertices to untangle it.

The planarity algorithm is a step-by-step method to test this rigorously — and it only works on graphs that contain a Hamiltonian cycle.

The Planarity Algorithm — Step by Step

STEP 1: Find a Hamiltonian cycle in the original graph. Draw a regular polygon with the same number of vertices, and label them in the order of that Hamiltonian cycle.
STEP 2: Add every remaining edge from the original graph onto the new polygon diagram, drawn inside the polygon. Make a list of these leftover edges.
STEP 3: Pick any edge inside the polygon that hasn't been labelled yet, and label it (I) for "Inside." (If every inside edge already has a label at this point, the graph is planar — stop here.)
STEP 4: Look for any edges (inside the polygon) that intersect the edge you just labelled.
- If there are none, go back to Step 3 and label a new edge.
- If the intersecting edges also cross each other, the graph is non-planar — stop, you're done.
- If the intersecting edges don't cross each other, give them all the label — (O) for "Outside." Then go back to Step 3.

Keep repeating Steps 3–4 until either every edge has a label (planar) or you find two crossing edges that both need the same label (non-planar). If it's planar, redraw the graph with all (I) edges curving inside the polygon and all (O) edges curving outside — and you'll have a picture with zero crossings.

Why this works

Inside and outside the polygon are like two separate "layers." As long as you can sort every leftover edge into one of the two layers without any two edges in the layer needing to cross, you've proven the graph can be drawn flat with zero overlaps.

Worked Example — Full Walkthrough

A graph on 6 vertices (A, B, C, D, E, F) is tested for planarity.

Step 1: A Hamiltonian cycle is found: A–C–B–E–D–F–A. Redraw these six vertices as a hexagon in that order.

Step 2: The leftover edges (not part of the hexagon outline) are: AB, AE, AD, CE, EF. These get drawn inside the hexagon.

Step 3 & 4, repeated:

Label AB (I). Only CE crosses it → label CE (O).
Nothing crosses CE further, so return to Step 3. Label AE (I). Nothing crosses it.
Return to Step 3. Label AD (I). Only EF crosses it → label EF (O).

Result: All five inside edges now have labels — AB(I), AE(I), AD(I), CE(O), EF(O) — with no clash. So the graph is planar. Redraw with I-edges curving inside the hexagon and O-edges curving around the outside, and you get a picture with zero crossing edges.

Practice Question 6

During the planarity algorithm, you label an edge (I). Two other unlabelled edges cross it — and those two edges also cross . What do you conclude?

Practice Question 7

Why does the planarity algorithm require you to start by finding a Hamiltonian cycle specifically, rather than just any cycle?

What to Memorise

Walk / Trail / PathWalk = anything goes. Trail = no repeated edges. Path = no repeated vertices (and therefore no repeated edges either).

CycleA path that starts and ends at the same vertex.

TourA walk that visits every vertex and returns to the start (may repeat vertices/edges along the way).

K_nComplete graph on n vertices; total edges = n(n−1)/2.

Handshaking LemmaSum of all degrees = 2 × number of edges. Number of odd-degree vertices is always even.

Eulerian graphContains an Eulerian cycle (closed, every edge once). Requires: all vertices even degree.

Semi-Eulerian graphContains an Eulerian trail (open, every edge once). Requires: exactly one pair of odd vertices — these are the start/end points.

Hamiltonian graphContains a Hamiltonian cycle (visits every vertex once, returns to start). No shortcut test — must find it by inspection.

Semi-Hamiltonian graphContains a Hamiltonian path but not a Hamiltonian cycle.

Planar graphCan be drawn with no edges crossing except at vertices. Test using the Planarity Algorithm (needs a Hamiltonian cycle first).

Tree / Spanning treeTree = connected, zero cycles. Spanning tree = a tree subgraph that includes every vertex of the original graph.

Concepts Checklist

I can define vertex, edge, loop, adjacent vertices/edges, and multiple edges
I can distinguish between a walk, trail, path, cycle, and tour
I can identify a connected graph, complete graph (K_n), network, digraph, and simple graph
I understand what a tree and a spanning tree are, and how they differ
I can explain isomorphic graphs and identify them
I can calculate the degree (valency) of a vertex, including loops counting twice
I can state and apply Euler's handshaking lemma
I can identify whether a graph is Eulerian, semi-Eulerian, or neither, using vertex degrees
I can find an actual Eulerian cycle or Eulerian trail in a given graph
I know the difference between Hamiltonian and Eulerian (vertices vs. edges)
I can find a Hamiltonian cycle or path by inspection to prove a graph is Hamiltonian/semi-Hamiltonian
I can apply the full planarity algorithm step by step (polygon → inside edges → I/O labelling)
I can conclude non-planarity when two crossing edges both need the same label
I can redraw a planar graph with zero crossing edges once the algorithm confirms it's planar

Exam Tips

Draw big, draw in pencil

Diagrams for this topic (especially planarity) need space to redraw and correct. Always sketch large and in pencil so you can erase mistakes cleanly — examiners need to clearly follow your working.

Loops count TWICE

A very common slip is forgetting that a loop contributes 2 to a vertex's degree (not 1), since it both leaves and returns to that vertex. Always double-check loop vertices when applying the handshaking lemma.

Eulerian ≠ Hamiltonian

Eulerian is about edges (traverse every edge once). Hamiltonian is about vertices (visit every vertex once). Mixing these up is one of the most common exam errors — always re-read the question to check which one is being asked about.

Any valid answer is accepted

For "write down a cycle / trail / Hamiltonian cycle" questions, there is very often more than one correct answer. Mark schemes accept valid route that satisfies the definition — don't waste time hunting for "the" answer; find answer that works and move on.

Planarity algorithm — show full working

Examiners want to see: the Hamiltonian cycle you chose, the polygon redraw, the full list of inside edges, and each labelling step (I/O) in order. Skipping straight to "it's planar" without this working loses method marks even if your final conclusion is correct.

Fast planarity gut-check

If you can trace a graph with your finger and it clearly looks "star-shaped" with everything crossing through a central hub, it's often (but not always!) non-planar — a useful sanity check before you commit to the full algorithm, though you should never skip the formal proof in an exam answer.

Also in the full note

Walks, Paths, Trails, Cycles & Tours

What's inside

📖 Revision notes ✦ AI flashcards ✓ Instant AI marking

Read the full Graphs notes free

That's the preview — create a free account to read the rest, plus flashcards and practice questions with instant AI marking. No credit card.

Unlock the full notes free →