Graph Theory Basics (AI HL)
Before you can run an algorithm on a graph, you need to be fluent in its vocabulary - vertices, edges, degree, and what it means for two graphs to secretly be "the same" graph in disguise. This page covers the handshaking lemma and degree sequences, with worked examples and the mistakes that lose marks. It's part of the broader Graph Theory topic.
11 questions on this sub-topic.
Degree, and what it tells you
Covered under IB syllabus reference AHL3.14: vertices, edges, adjacent vertices and edges, and the degree of a vertex.
Handshaking lemma
\(\displaystyle\sum \deg(v) = 2E\)
Not in the formula booklet - it follows because every edge adds exactly 1 to the degree of each of its two endpoints. It also proves that any graph has an even number of odd-degree vertices.
Degree sequences
A proposed degree sequence can only belong to a real graph if it sums to an even number. Two isomorphic graphs must share the same degree sequence - but a matching sequence alone doesn't guarantee two graphs are isomorphic.
Use the sum test first to rule out impossible sequences, then compare sequences to rule out isomorphism.
Want the full syllabus wording and how graphs represent real networks and maps? See Graph Theory.
Worked examples
A graph has 6 vertices with degrees \(3, 3, 4, 2, 2, 2.\)
(a) State the handshaking lemma.
(b) Find the number of edges.
Worked solution
(a) The sum of all vertex degrees equals twice the number of edges: \(\sum\deg(v) = 2E.\) A1
(b) Sum \(= 16 = 2E \Rightarrow E\) M1
\(= 8.\) A1
Can a simple graph have degree sequence \(5, 5, 5, 5, 5\)? Explain.
Worked solution
Degree sum \(= 25\), which is odd. M1 A1
By handshaking the sum must equal \(2E\) (even). M1 A1
An odd sum is impossible, so no such graph exists. A1
Common mistakes
- Forgetting the factor of 2 in the handshaking lemma. The sum of degrees equals \(2E\), not \(E\) - each edge is counted once at each of its two endpoints, so halve the degree sum to get the number of edges.
- Assuming matching degree sequences prove two graphs are isomorphic. It's a necessary condition, not a sufficient one - the same set of degrees can be wired together in structurally different ways, so a full isomorphism needs an explicit vertex correspondence.
- Trying to sketch a graph before checking the degree sum is even. Any proposed degree sequence with an odd total sum is impossible for a simple graph - check the handshaking lemma first and save yourself the wasted diagram.
Ready to practise properly?
20 graph theory basics questions, marked instantly like the real exam.
Quick answers
What is the handshaking lemma?
The sum of all vertex degrees in a graph equals twice the number of edges, since every edge contributes 1 to the degree of each of its two endpoints.
Do two graphs with the same degree sequence have to be isomorphic?
No. A matching degree sequence is necessary for two graphs to be isomorphic, but not sufficient - the same degrees can be arranged into structurally different graphs.