Graphs and Networks: Definitions and Terminology

Graph theory is the mathematical study of networks — collections of points (vertices) joined by lines (edges). The same abstract object models a road map, a circuit board, a friendship network, a molecule, the dependencies in a building project and the states of a puzzle. The power of the subject is precisely this universality: once a situation is captured as a graph, a single body of theorems and algorithms applies regardless of what the vertices "really are". This lesson lays down the vocabulary and the foundational results — above all the handshaking lemma — on which the entire Discrete option of AQA 7367 is built.

---

1. Where this sits in AQA 7367

This is the opening topic of the Paper 3 Discrete option (7367/3D), one of the three optional applications (you choose two of Mechanics 7367/3M, Statistics 7367/3S, Discrete 7367/3D). Paper 3 is 2 hours, 100 marks, 33⅓% of the qualification, with an assessment-objective split of AO1 40% / AO2 25% / AO3 35% — markedly more problem-solving-weighted than the compulsory pure papers. Terminology questions test AO1 (using and recalling standard definitions) and AO2 (precise mathematical communication: examiners reward the correct word, not a loose paraphrase). Every later Discrete topic — minimum spanning trees, Dijkstra, route inspection, matchings, critical-path analysis — is stated in the language defined here, so fluency now pays dividends across the whole option.

---

2. Core theory: the language of graphs

A graph $G = (V, E)$G=(V,E) is a finite set of vertices $V$V together with a set of edges $E$E, where each edge joins an unordered pair of vertices. We write $|V|$∣V∣ for the number of vertices and $|E|$∣E∣ for the number of edges.

Term	Definition
Vertex (node)	A point of the graph; an element of $V$V
Edge (arc)	A connection between two vertices; an element of $E$E
Loop	An edge joining a vertex to itself
Multiple (parallel) edges	Two or more edges joining the same pair of vertices
Simple graph	A graph with no loops and no multiple edges
Multigraph	A graph that may have loops and/or multiple edges
Directed graph (digraph)	A graph in which each edge has a direction (an ordered pair)
Weighted graph / network	A graph in which each edge carries a numerical weight (distance, cost, time, capacity)
Adjacent	Two vertices joined by an edge are adjacent; an edge is incident to its endpoints

A network is simply a weighted graph; the weight of edge $e$e is written $w(e)$w(e), and the weight of a set of edges is the sum of the individual weights, $\sum_{e} w(e)$∑e​w(e). The distinction between "graph" (pure structure) and "network" (structure + numbers) matters in the exam: spanning-tree and shortest-path questions are network questions, whereas Eulerian/Hamiltonian existence questions are usually about the underlying graph.

Here is a small weighted graph drawn with mermaid:

graph LR
  A((A)) ---|3| B((B))
  A ---|5| C((C))
  B ---|4| C
  C ---|2| D((D))
  C ---|7| E((E))
  D ---|1| E

This network has $|V| = 5$∣V∣=5 and $|E| = 6$∣E∣=6; its total weight is $3 + 5 + 4 + 2 + 7 + 1 = 22$3+5+4+2+7+1=22.

---

3. Degree and the handshaking lemma (with M1/A1 mark scheme)

The degree $\deg(v)$deg(v) of a vertex $v$v is the number of edge-ends meeting at $v$v (a loop contributes $2$2). In a digraph we separate the in-degree $\deg^{-}(v)$deg−(v) and out-degree $\deg^{+}(v)$deg+(v).

The single most useful identity in the topic is the handshaking lemma:

$\sum_{v \in V} \deg(v) = 2\,|E|.$∑v∈V​deg(v)=2∣E∣.

Proof. Each edge has exactly two ends; summing the degrees counts every edge-end once, hence counts every edge exactly twice. $\therefore$∴ the degree sum is $2|E|$2∣E∣. $\blacksquare$■

Two immediate consequences are constantly used as checks:

$|E| = \tfrac{1}{2}\sum_{v \in V} \deg(v), \qquad \#\{v : \deg(v) \text{ odd}\} \text{ is even}.$∣E∣=21​∑v∈V​deg(v),#{v:deg(v) odd} is even.

The second follows because the even-degree vertices contribute an even total, so the odd-degree vertices must also contribute an even total — and a sum of odd numbers is even only if there is an even count of them.

Worked Example 3.1 — degree sum and edge count

A simple graph has five vertices A, B, C, D, E with degrees $3, 2, 4, 3, 2$3,2,4,3,2. Find the number of edges and verify the parity corollary.

$$\begin{aligned} \sum_{v} \deg(v) &= 3 + 2 + 4 + 3 + 2 = 14, \\ |E| &= \tfrac{1}{2}(14) = 7. \end{aligned}$$v∑​deg(v)∣E∣​=3+2+4+3+2=14,=21​(14)=7.​

(M1 for summing the degrees; A1 for $|E| = 7$∣E∣=7.) The odd-degree vertices are A and D — exactly two of them, an even number, consistent with the corollary. (B1 for the parity check.)

Worked Example 3.2 — using the lemma in reverse

A connected simple graph has $8$8 edges and every vertex has degree $2$2 or $4$4. If there are $2$2 vertices of degree $4$4, how many vertices of degree $2$2 are there?

Let there be $k$k vertices of degree $2$2. The degree sum is $2(4) + 2k = 8 + 2k$2(4)+2k=8+2k, and by the handshaking lemma this equals $2|E| = 16$2∣E∣=16:

$8 + 2k = 16 \;\implies\; 2k = 8 \;\implies\; k = 4.$8+2k=16⟹2k=8⟹k=4.

(M1 for equating the degree sum to $2|E|$2∣E∣; A1 for $k = 4$k=4.) So there are $4$4 vertices of degree $2$2, giving $6$6 vertices in total.

Exam tip. If your degree sum is odd you have made an arithmetic slip — the lemma guarantees it must be even. Quote the lemma by name; examiners reward the precise statement $\sum \deg(v) = 2|E|$∑deg(v)=2∣E∣.

Directed graphs and the in/out-degree identity

In a digraph every edge is an ordered pair, drawn as an arrow. Each vertex then has an in-degree $\deg^{-}(v)$deg−(v) (arrows pointing in) and an out-degree $\deg^{+}(v)$deg+(v) (arrows pointing out). Because every arc has exactly one tail and one head, summing out-degrees counts each arc once at its tail, and summing in-degrees counts each arc once at its head, so

$\sum_{v \in V} \deg^{+}(v) = \sum_{v \in V} \deg^{-}(v) = |E|.$∑v∈V​deg+(v)=∑v∈V​deg−(v)=∣E∣.

This is the directed analogue of the handshaking lemma — note the right-hand side is $|E|$∣E∣, not $2|E|$2∣E∣, because each arc is counted once in each sum rather than twice in a single sum. Digraphs model one-way streets, precedence in scheduling (Critical Path Analysis later in this module), and the "follows" relation in a social network. A digraph is strongly connected if there is a directed path from every vertex to every other; this is a stronger requirement than connectivity of the underlying undirected graph, and is exactly what a courier needs if every depot must be reachable from every other along legal one-way routes.

Worked Example 3.3 — a small digraph

A digraph on vertices A, B, C, D has arcs $A\!\to\!B,\ B\!\to\!C,\ C\!\to\!A,\ A\!\to\!C,\ D\!\to\!A$A→B, B→C, C→A, A→C, D→A. Find every in- and out-degree and verify the identity.

Vertex	$\deg^{+}$deg+ (out)	$\deg^{-}$deg− (in)
A	2 ($A\!\to\!B,\ A\!\to\!C$A→B, A→C)	2 ($C\!\to\!A,\ D\!\to\!A$C→A, D→A)
B	1	1
C	1	2
D	1	0

$\sum \deg^{+} = 2 + 1 + 1 + 1 = 5$∑deg+=2+1+1+1=5 and $\sum \deg^{-} = 2 + 1 + 2 + 0 = 5 = |E|$∑deg−=2+1+2+0=5=∣E∣ — both equal the five arcs, as the identity demands. (M1 for separating in/out correctly; A1 for the verified totals.) Vertex D has in-degree $0$0, so it is a source; no arc returns to D, so this digraph is not strongly connected.

---

4. Families of graphs

Family	Definition	Edge count
Complete graph $K_n$Kn​	Every pair of vertices joined by exactly one edge	$\binom{n}{2} = \dfrac{n(n-1)}{2}$(2n​)=2n(n−1)​
Complete bipartite $K_{m,n}$Km,n​	Vertices split into sets of sizes $m, n$m,n; every cross-pair joined	$mn$mn
Cycle $C_n$Cn​	$n$n vertices joined in a single closed loop	$n$n
Path $P_n$Pn​	$n$n vertices joined in a line	$n-1$n−1
Tree	Connected graph with no cycles	$n-1$n−1
Bipartite graph	Vertices two-colourable so no edge is monochromatic	varies
Planar graph	Drawable in the plane with no edge crossings	$\le 3n-6$≤3n−6 (simple, $n \ge 3$n≥3)

In $K_n$Kn​ every vertex has degree $n - 1$n−1, so the handshaking lemma gives $|E| = \tfrac{1}{2}\,n(n-1)$∣E∣=21​n(n−1), agreeing with $\binom{n}{2}$(2n​):

$n$n	Vertices	Edges $\binom{n}{2}$(2n​)	Degree of each vertex
3	3	3	2
4	4	6	3
5	5	10	4
6	6	15	5

A graph is bipartite iff it contains no cycle of odd length — a characterisation worth remembering because it is the quickest way to disprove bipartiteness (find an odd cycle).

---

5. Walks, trails, paths and cycles

These four words are routinely confused; the exam penalises the wrong one. The hierarchy is by what may repeat.

Term	May repeat vertices?	May repeat edges?
Walk	yes	yes
Trail	yes	no
Path	no	no
Cycle (closed path)	only the start = end	no

A graph is connected if there is a walk between every pair of vertices. A maximal connected piece is a component. A bridge is an edge whose removal increases the number of components; a cut vertex is a vertex whose removal (with its incident edges) does so.

Eulerian and Hamiltonian structures

Concept	Definition	Existence condition
Eulerian circuit	Closed trail using every edge exactly once	Connected and all degrees even
Eulerian (semi-Eulerian) trail	Open trail using every edge exactly once	Connected and exactly two odd-degree vertices
Hamiltonian cycle	Cycle visiting every vertex exactly once	No simple degree criterion (NP-complete in general)
Hamiltonian path	Path visiting every vertex exactly once	No simple criterion

The contrast is examinable in its own right: Eulerian = "every edge" and is settled instantly by reading degrees; Hamiltonian = "every vertex" and generally needs search. This Eulerian/odd-degree connection is the engine behind the route inspection problem met later in this module.

graph LR
  P((P)) --- Q((Q))
  Q --- R((R))
  R --- S((S))
  S --- P
  P --- R

In this graph the degrees are $\deg(P) = \deg(R) = 3$deg(P)=deg(R)=3 and $\deg(Q) = \deg(S) = 2$deg(Q)=deg(S)=2; exactly two vertices (P, R) are odd, so a semi-Eulerian trail exists (e.g. $P\!-\!Q\!-\!R\!-\!S\!-\!P\!-\!R$P−Q−R−S−P−R) but no Eulerian circuit.

---

6. Trees, planarity and two classical theorems

A tree is a connected acyclic graph; a forest is a disjoint union of trees. Trees are the backbone of the spanning-tree algorithms studied next.

Property of a tree on $n$n vertices	Holds?
Exactly $n - 1$n−1 edges	Yes
Unique path between any two vertices	Yes
Adding any new edge creates exactly one cycle	Yes
Removing any edge disconnects it	Yes
Connected and acyclic	Yes (defining)

Cayley's formula counts the labelled trees on $n$n vertices:

$\tau(K_n) = n^{\,n-2}.$τ(Kn​)=nn−2.

So $\tau(K_3) = 3^{1} = 3$τ(K3​)=31=3, $\tau(K_4) = 4^{2} = 16$τ(K4​)=42=16 and $\tau(K_5) = 5^{3} = 125$τ(K5​)=53=125.

A graph is planar if it can be drawn with no edges crossing. For a connected planar drawing, Euler's polyhedral formula relates vertices, edges and faces (counting the unbounded outer face):

$V - E + F = 2.$V−E+F=2.

From this one derives the edge bounds $E \le 3V - 6$E≤3V−6 (simple, $V \ge 3$V≥3) and $E \le 2V - 4$E≤2V−4 (simple bipartite), which give quick non-planarity proofs. Kuratowski's theorem states that a graph is planar iff it contains no subdivision of $K_5$K5​ or $K_{3,3}$K3,3​.

Worked Example 6.1 — Euler's formula and a non-planarity argument

A connected planar graph is drawn with $V = 6$V=6 and $E = 9$E=9. How many faces does the drawing have? Show that $K_5$K5​ cannot be planar.

$F = 2 - V + E = 2 - 6 + 9 = 5.$F=2−V+E=2−6+9=5. (M1 rearrange Euler; A1 $F = 5$F=5.)

For $K_5$K5​: $V = 5,\ E = 10$V=5, E=10. If it were planar then $E \le 3V - 6 = 9$E≤3V−6=9. But $10 > 9$10>9, a contradiction, so $K_5$K5​ is non-planar. (M1 apply the bound; A1 contradiction stated.)

---

7. Specimen-style exam question

(Specimen-style — not from any past paper.)

A network of seven sites A–G is modelled by a simple connected graph. The degrees of the vertices are $4, 3, 3, 2, 2, 2, 2$4,3,3,2,2,2,2. (a) Find the number of edges. [2] (b) Explain why the graph cannot have an Eulerian circuit but does have a semi-Eulerian trail. [2] (c) The graph is drawn in the plane with no edges crossing. Find the number of regions (faces) the drawing creates. [2]

Model solution. (a) $\sum \deg(v) = 4 + 3 + 3 + 2 + 2 + 2 + 2 = 18$∑deg(v)=4+3+3+2+2+2+2=18, so $|E| = \tfrac{1}{2}(18) = 9.$∣E∣=21​(18)=9. [M1 A1] (b) An Eulerian circuit requires every vertex to be even; here two vertices have odd degree (the two of degree $3$3), so no Eulerian circuit exists. Because there are exactly two odd-degree vertices and the graph is connected, a semi-Eulerian trail exists between those two vertices. [B1 B1] (c) Euler's formula: $F = 2 - V + E = 2 - 7 + 9 = 4.$F=2−V+E=2−7+9=4. [M1 A1]

---

8. Synoptic links

• Route inspection (Chinese Postman) rests entirely on the handshaking lemma and the even-degree Eulerian condition — the same odd-vertex idea, reused.
• Minimum spanning trees are trees with $n-1$n−1 edges; Kruskal's correctness is exactly the "adding an edge creates a cycle" property of trees.
• Adjacency matrices (next lesson) re-encode $\deg(v)$deg(v) as a row sum, and $(A^2)_{vv} = \deg(v)$(A2)vv​=deg(v).
• Counting / binomial coefficients from A-Level Maths underpin $K_n$Kn​ having $\binom{n}{2}$(2n​) edges.
• Proof by contradiction and parity arguments (Paper 1 pure) appear directly in the planarity bound and the odd-degree corollary.

---

9. Mark-scheme literacy

• "State" / "Write down" — a bare answer earns the mark; no working demanded (e.g. $|E|$∣E∣ from a clear degree sum).
• "Show that" — the target answer is given; you must produce every connecting line. A correct final number with no reasoning typically scores 0.
• "Explain why" — communicate the reason (e.g. "two odd-degree vertices, so no Eulerian circuit"), in words tied to the definition; vague assertions lose the AO2 mark.
• Use the exact vocabulary: circuit vs trail, vertex vs node are fine as synonyms, but path and walk are not interchangeable.
• Follow-through (ft) marks: if you mis-add the degrees but then halve correctly, the method mark for halving can still be awarded.

---

10. Grade-band model answers

Question. Prove that in any graph the number of vertices of odd degree is even. [3]

Mid-band response. "The total of all the degrees is $2E$2E because each edge adds 2. $2E$2E is even. So the odd-degree vertices must add up to an even number, which means there are an even number of them." Examiner-style commentary. The key facts are present and the conclusion is right, but the logic is compressed: it is asserted, not shown, that "an even sum forces an even count of odd numbers". This would likely earn the method and a partial reasoning mark but miss the final rigour mark.

Stronger response. "By the handshaking lemma $\sum_v \deg(v) = 2|E|$∑v​deg(v)=2∣E∣, which is even. Split the vertices into those of even degree and those of odd degree. The even-degree vertices contribute an even sum, so the odd-degree vertices also contribute an even sum. A sum of odd numbers is even only when there is an even quantity of them, so the number of odd-degree vertices is even." Examiner-style commentary. Complete and correctly structured: lemma quoted, a clean partition, and the parity step justified. Full marks. The phrase "only when there is an even quantity of them" supplies the reasoning the Mid-band answer omitted.

Top-band response. "By the handshaking lemma, $\sum_{v} \deg(v) = 2|E| \equiv 0 \pmod 2$∑v​deg(v)=2∣E∣≡0(mod2). Write $V = V_{\text{even}} \cup V_{\text{odd}}$V=Veven​∪Vodd​. Then $\sum_{v \in V_{\text{even}}} \deg(v) \equiv 0 \pmod 2$∑v∈Veven​​deg(v)≡0(mod2), so $\sum_{v \in V_{\text{odd}}} \deg(v) \equiv 0 \pmod 2$∑v∈Vodd​​deg(v)≡0(mod2). Each term in the latter sum is odd $\equiv 1 \pmod 2$≡1(mod2), so the sum is congruent to $|V_{\text{odd}}| \pmod 2$∣Vodd​∣(mod2). Hence $|V_{\text{odd}}| \equiv 0$∣Vodd​∣≡0, i.e. even. $\blacksquare$■" Examiner-style commentary. Model rigour: modular-arithmetic language makes every step airtight and the conclusion follows by an explicit congruence rather than a verbal appeal. This is the standard expected of a strong STEP/MAT candidate and communicates why, not merely that.

---

11. Common misconceptions

1. "Degree = number of neighbours." False with multiple edges or loops: degree counts edge-ends, so a loop adds $2$2 and parallel edges each add $1$1.
2. "A graph must be connected." No — graphs can have several components; "connected" is an extra property to check.
3. "Eulerian and Hamiltonian are the same idea." Eulerian is about every edge; Hamiltonian is about every vertex. They are independent.
4. "$K_5$K5​ is planar — I can draw it." Any attempt forces a crossing; $E = 10 > 3V - 6 = 9$E=10>3V−6=9 proves it cannot be drawn planar.
5. "Path and walk mean the same." A walk may revisit vertices and edges; a path may not. The wrong word loses communication marks.
6. "A tree can have a cycle if it is small." By definition a tree is acyclic; any cycle disqualifies it.
7. "Odd number of odd-degree vertices is possible." Forbidden by the handshaking corollary — always an even number.

---

12. Common errors

• Forgetting the $\tfrac{1}{2}$21​ when converting degree sum to edge count (writing $|E| = \sum \deg(v)$∣E∣=∑deg(v)).
• Miscounting a loop as degree $1$1 instead of $2$2.
• Stating the planar bound as $E \le 3V$E≤3V or $E \le 3V - 2$E≤3V−2 instead of $E \le 3V - 6$E≤3V−6.
• Quoting Euler's formula as $V - E + F = 1$V−E+F=1 (forgetting the outer face) or $V + E - F = 2$V+E−F=2 (sign slip).
• Asserting bipartiteness without checking for odd cycles.
• Confusing directed in-/out-degree: in a digraph $\sum \deg^{+}(v) = \sum \deg^{-}(v) = |E|$∑deg+(v)=∑deg−(v)=∣E∣, not $2|E|$2∣E∣.

---

13. Going further (STEP / MAT / Oxbridge)

The handshaking lemma is the simplest case of a double-counting argument — counting one quantity (edge-ends) two ways. The same idea, generalised, proves Euler's formula by induction on edges, and underlies the degree-sum version of the first theorem of graph theory. A natural extension: the number of labelled graphs on $n$n vertices is $2^{\binom{n}{2}}$2(2n​) (each of the $\binom{n}{2}$(2n​) possible edges is independently present or absent). Compare this with Cayley's $n^{n-2}$nn−2 for trees — the ratio quantifies how special "being a tree" is. A classic olympiad-style question: prove that any graph on $6$6 vertices contains either a triangle or an independent set of size $3$3 — this is the smallest Ramsey result $R(3,3) = 6$R(3,3)=6, provable by a one-line pigeonhole on the degrees at a single vertex. These double-counting and extremal ideas are exactly the flavour of STEP III and the MAT graph-theory questions.

---

14. A* practice (with worked answers)

P1. A simple graph has $7$7 vertices and $12$12 edges. Can every vertex have the same degree? If so, what is it? Answer. If every vertex has degree $d$d, then $7d = 2(12) = 24$7d=2(12)=24. But $24 / 7$24/7 is not an integer, so no such regular graph exists.

P2. Show that a tree with at least two vertices has at least two leaves (degree-1 vertices). Answer. A tree on $n \ge 2$n≥2 vertices has $n - 1$n−1 edges, so $\sum \deg(v) = 2(n-1) = 2n - 2$∑deg(v)=2(n−1)=2n−2. If it had at most one leaf, at least $n - 1$n−1 vertices would have degree $\ge 2$≥2, giving $\sum \deg(v) \ge 2(n-1) + 1 = 2n - 1 > 2n - 2$∑deg(v)≥2(n−1)+1=2n−1>2n−2, a contradiction. Hence at least two leaves. $\blacksquare$■

P3. For which $n$n is $K_n$Kn​ Eulerian? Answer. Every vertex of $K_n$Kn​ has degree $n - 1$n−1; an Eulerian circuit needs all degrees even, i.e. $n - 1$n−1 even, i.e. $n$n odd. So $K_3, K_5, K_7, \dots$K3​,K5​,K7​,… are Eulerian (and $K_1$K1​ trivially).

P4. A connected simple planar graph has $V = 10$V=10 and is drawn with $F = 7$F=7 faces. Find $E$E, and state whether it could be a tree. Answer. $E = V + F - 2 = 10 + 7 - 2 = 15$E=V+F−2=10+7−2=15. A tree would have $E = V - 1 = 9 \ne 15$E=V−1=9=15, so it is not a tree (and indeed has cycles, since $F > 1$F>1).

P5. Prove that $K_{3,3}$K3,3​ is non-planar using an edge bound. Answer. $K_{3,3}$K3,3​ is simple and bipartite with $V = 6,\ E = 9$V=6, E=9. A simple bipartite planar graph satisfies $E \le 2V - 4 = 8$E≤2V−4=8. Since $9 > 8$9>8, $K_{3,3}$K3,3​ cannot be planar. $\blacksquare$■

---

15. Board-alignment footer

Aligned to AQA A-Level Further Mathematics 7367, Paper 3 Discrete option (7367/3D) — graph terminology, degree, the handshaking lemma, Eulerian/Hamiltonian conditions, trees and planarity. Edexcel (Decision 1) and OCR (MEI Discrete / OCR A Discrete) cover the same definitions and the handshaking lemma; the vocabulary transfers directly across boards.

---

16. Visual summary

graph TD
  G[Graph G = V,E] --> D[Degree deg v]
  D --> H["Handshaking: sum deg v = 2|E|"]
  H --> P[Parity: #odd-degree vertices is even]
  G --> T[Tree: connected + acyclic, n-1 edges]
  G --> PL[Planar: V - E + F = 2]
  G --> E1[Eulerian: all degrees even]
  G --> E2[Semi-Eulerian: exactly 2 odd]

$$\boxed{\;\sum_{v \in V} \deg(v) = 2|E| \quad\Longrightarrow\quad \#\{\text{odd-degree } v\}\ \text{even};\qquad K_n:\ \binom{n}{2}\ \text{edges};\qquad \text{tree}:\ n-1\ \text{edges};\qquad V - E + F = 2.\;}$$v∈V∑​deg(v)=2∣E∣⟹#{odd-degree v} even;Kn​: (2n​) edges;tree: n−1 edges;V−E+F=2.​

Result	Statement
Handshaking lemma	$\sum_v \deg(v) = 2
Odd-degree parity	The count of odd-degree vertices is even
Complete graph	$K_n$Kn​ has $\binom{n}{2} = \tfrac{n(n-1)}{2}$(2n​)=2n(n−1)​ edges, each vertex degree $n-1$n−1
Tree edge count	A tree on $n$n vertices has exactly $n-1$n−1 edges
Cayley's formula	$\tau(K_n) = n^{\,n-2}$τ(Kn​)=nn−2 labelled trees
Euler's formula	Connected planar: $V - E + F = 2$V−E+F=2, with $E \le 3V - 6$E≤3V−6

Exam tip. When you describe a graph, always quote $|V|$∣V∣, $|E|$∣E∣, and any structural property (connected / tree / bipartite / Eulerian). The handshaking lemma is your free self-check on every degree calculation — use it.