A graph is dots joined by lines: A graph is a picture of connections: dots for places, lines for the links between them.
Towns and roads: Picture a map of 5 towns with roads between some of them. Draw each town as a dot and each road as a line joining two dots — that picture is a graph.
The words you need
- The dots are vertices (one is a vertex), the lines are edges.
- A graph only records which towns are connected, not how far apart they are drawn — so the same graph can be sketched in many ways.
- The degree of a vertex is simply how many edge-ends touch it — how many roads leave that town. A town with 3 roads has degree 3.
The handshake lemma — why degrees add to twice the edges
Two ends per edge
Every edge has two ends, and each end adds 1 to the degree of the vertex it touches.
Count every edge twice
So if you add up the degrees of all vertices, you count every edge exactly twice (once for each end).
The lemma
The sum of all degrees equals 2 × (number of edges).
Sum of degrees = 2 × edges
Why it helps: It's a fast check on any graph — and it forces the number of odd-degree vertices to be even.
IB-style question — degrees of a road network
A small road network links 5 towns A, B, C, D, E. The roads are: A–B, A–C, A–D, B–C, C–D, C–E.
Write the degree of each town, and use the handshake lemma to check the number of roads.
Step by step
- Count the roads meeting each town. A touches B, C, D → 3 roads.
- B touches A, C → 2. C touches A, B, D, E → 4. D touches A, C → 2. E touches C → 1.
- Add all degrees.
- Handshake lemma: total degree = 2E, so E = 12 ÷ 2 = 6 — which matches the six roads listed.
Final answer
Degrees 3, 2, 4, 2, 1; total 12 = 2 × 6, confirming there are 6 roads.
Free preview
This is the free notes preview
You're reading the free notes. Aimnova Pro unlocks the full study experience — and you can try it with your first topic free to keep:
- FlashcardsLock in vocabulary and key terms with spaced repetition.
- Practice questionsAnswer exam-style questions and get instant AI marking.
- Mock exams & past-paper vaultSit full mocks and see exactly how examiners award marks.
- Personalised study planA daily plan built around your exam date and weak areas.
Special families of graphs: The exam expects you to recognise and use these five names.
| Name | What it means |
|---|---|
| Simple | No loops (an edge from a vertex to itself) and no repeated edges between the same two vertices. Most real networks are simple. |
| Connected | You can travel from any vertex to any other by following edges (no isolated piece). |
| Complete | Every pair of vertices is joined by an edge. The complete graph on n vertices is written Kₙ. |
| Bipartite | The vertices split into two groups, and edges only go between the groups, never within a group (e.g. students on one side, clubs on the other). |
| Tree | A connected graph with no cycles. A tree on n vertices has exactly n − 1 edges — the fewest edges that still keep everything connected. |
IB-style question — a complete social network
Six members of a project team are each directly messaging every other member, modelled by the complete graph K₆.
(a) How many direct message links are there?
(b) State the degree of each member.
Step by step
- (a) In Kₙ every pair is joined, so count pairs: edges = n(n − 1)/2.
- (b) In a complete graph each vertex joins to all n − 1 others.
- Check with the handshake lemma: 6 vertices × degree 5 = 30 = 2 × 15. ✓
Final answer
(a) 15 links. (b) Every member has degree 5.
IB-style question — is it a tree?
A company's reporting structure is connected, has 9 staff (vertices) and 8 reporting links (edges), with no cycles.
Explain whether this is a tree, and what would happen to connectivity if one link were removed.
Step by step
- A tree is connected with no cycles — both hold here.
- Check the edge count: a tree on n vertices has n − 1 edges.
- A tree has the fewest edges that keep it connected, so removing any single edge disconnects it.
Final answer
Yes — it is a tree (connected, no cycles, 8 = 9 − 1 edges). Removing any link would break it into two disconnected groups.