Mathematics · Topic 1.4 · Extended
Networks and Combinatorics
Graph theory provides mathematical models for real-world networks — road systems, social networks, computer circuits. Combinatorics gives powerful counting tools for arrangements and selections. Both are Extended-level discrete mathematics topics assessed in the eAssessment calculator paper.
What You'll Learn
- Define and identify key graph theory terms: vertices, edges, degree, path, circuit
- Apply Euler's theorem to determine whether an Euler circuit or path exists
- Find minimum spanning trees using Kruskal's and Prim's algorithms
- Calculate permutations (nPr) and combinations (nCr) using factorials
- Distinguish when to use permutations vs combinations in context
- Apply counting principles (multiplication and addition rules) to multi-stage problems
eAssessment Focus
Criterion A: Apply Euler's theorem and counting formulas correctly in unfamiliar network contexts.
Criterion B: Investigate patterns in networks — e.g., how does vertex degree relate to traversability?
Criterion C: Use correct terminology: degree, Euler circuit, permutation, combination — define before applying.
Criterion D: Apply combinatorics to real contexts (scheduling, genetics, password security).
Key Vocabulary
| Term | Definition |
|---|---|
| Graph (network) | A set of vertices (nodes) connected by edges (arcs) |
| Vertex (node) | A point in a graph; plural: vertices |
| Edge (arc) | A connection between two vertices |
| Degree of a vertex | The number of edges meeting at that vertex |
| Path | A route through a graph that does not repeat any vertex |
| Circuit | A path that begins and ends at the same vertex |
| Connected graph | Every vertex can be reached from every other vertex |
| Weighted graph | A graph where edges have numerical values (weights), e.g., distances |
| Spanning tree | A subgraph connecting all vertices with no cycles and minimum edges |
| Permutation (nPr) | An ordered arrangement of r items from n: nPr = n! / (n−r)! |
| Combination (nCr) | An unordered selection of r items from n: nCr = n! / (r!(n−r)!) |
| Factorial (n!) | n! = n × (n−1) × … × 2 × 1; defined 0! = 1 |
Mathematics · Topic 1.4 · Extended
Graph Theory Basics
A graph is a mathematical structure consisting of vertices and edges. Understanding the properties of graphs is the foundation for network problems.
Graph Properties
Simple Graph
No loops (edges connecting a vertex to itself) and no multiple edges between the same pair of vertices.
Complete Graph (Kn)
Every vertex is connected to every other vertex. Kn has n(n−1)/2 edges.
Directed Graph
Edges have a direction (arrows). Used for one-way streets, website links, task dependencies.
Bipartite Graph
Vertices split into two groups; edges only connect between groups (not within). Used for matching problems.
The Handshaking Lemma
Theorem
The sum of all vertex degrees in any graph equals twice the number of edges.∑deg(v) = 2|E|
This means the number of vertices with odd degree is always even. This is a powerful fact for checking your work.
Example: A graph has 5 edges. The sum of all vertex degrees = 2 × 5 = 10. If vertex degrees are 1, 2, 2, 3, then one more vertex must have degree 10 − 8 = 2.
Degree Table Approach
For exam questions, always build a degree table first:
| Vertex | Connected to | Degree |
|---|---|---|
| A | B, C, D | 3 (odd) |
| B | A, C | 2 (even) |
| C | A, B, D | 3 (odd) |
| D | A, C | 2 (even) |
Sum of degrees = 3 + 2 + 3 + 2 = 10 = 2 × 5 edges ✓
Key Insight: In an undirected graph, each edge contributes 1 to the degree of each of its two endpoints, hence total degree = 2 × edges. Always verify your degree table sums to an even number.
Mathematics · Topic 1.4 · Extended
Euler Paths & Circuits
An Euler path traverses every edge exactly once. An Euler circuit does the same but returns to the starting vertex. Euler's theorem gives a simple test for when these exist.
Euler's Theorem
Theorem (Euler, 1736)
Euler circuit exists ⇔ graph is connected AND every vertex has even degree.Euler path (not a circuit) exists ⇔ graph is connected AND exactly two vertices have odd degree (these are the start and end points).
Decision Table
| Odd-degree vertices | Result |
|---|---|
| 0 | Euler circuit exists (start/end anywhere) |
| 2 | Euler path exists (start at one odd vertex, end at the other) |
| 4 or more | No Euler path or circuit exists |
The Königsberg Bridge Problem (1736): Euler proved that you cannot walk across all seven bridges of Königsberg exactly once and return to the start — because the graph has four odd-degree vertices. This founded graph theory.
Hamiltonian Path vs Euler Path
Euler Path/Circuit
Visits every edge exactly once. Vertices may be revisited. Can test with the degree rule.
Hamiltonian Path/Circuit
Visits every vertex exactly once. No simple rule — must try systematically. Hamiltonian circuit = travelling salesman problem.
Common Mistake: Confusing Euler (every edge once) with Hamiltonian (every vertex once). The exam will test both. Euler has a simple theorem; Hamiltonian does not — you must trace possibilities.
Mathematics · Topic 1.4 · Extended
Minimum Spanning Trees
A spanning tree connects all vertices of a graph with no cycles. A minimum spanning tree (MST) does so with the smallest total edge weight. MSTs model efficient network design: road, cable, or pipeline systems.
Kruskal's Algorithm
- List all edges in ascending order by weight.
- Add the cheapest edge that does not create a cycle.
- Repeat until all n vertices are connected (you will add exactly n−1 edges).
Prim's Algorithm
- Start at any vertex.
- At each step, add the cheapest edge connecting the current tree to a new (not yet included) vertex.
- Repeat until all vertices are included.
Example (5-vertex network):
Edges: AB=4, AC=2, BC=5, BD=3, CD=1, DE=6
Kruskal's step-by-step:
1. CD=1 ✓ (add)
2. AC=2 ✓ (add)
3. BD=3 ✓ (add)
4. AB=4 — skip (would create cycle A-C-D-B-A... check: A already connects to C and C to D and D to B; adding AB creates cycle ABCA)
Wait: A is connected to C; D is connected to C and B. Adding AB connects A to B; is there already a path A to B? A-C-D-B yes! Skip.
5. DE=6 ✓ (add)
MST total = 1+2+3+6 = 12
Edges: AB=4, AC=2, BC=5, BD=3, CD=1, DE=6
Kruskal's step-by-step:
1. CD=1 ✓ (add)
2. AC=2 ✓ (add)
3. BD=3 ✓ (add)
4. AB=4 — skip (would create cycle A-C-D-B-A... check: A already connects to C and C to D and D to B; adding AB creates cycle ABCA)
Wait: A is connected to C; D is connected to C and B. Adding AB connects A to B; is there already a path A to B? A-C-D-B yes! Skip.
5. DE=6 ✓ (add)
MST total = 1+2+3+6 = 12
Key Rule: A spanning tree on n vertices has exactly n−1 edges. If you count your edges and get more or fewer, something is wrong. Also, if the graph is not connected, no spanning tree exists.
Mathematics · Topic 1.4 · Extended
Combinatorics: Permutations & Combinations
Combinatorics is the mathematics of counting. Two fundamental tools — permutations and combinations — handle the vast majority of counting problems at MYP level.
The Fundamental Counting Principle
Multiplication Rule
If event A can occur in m ways AND event B can occur in n ways, then both A and B can occur in m × n ways.
Example: A restaurant offers 4 starters, 6 mains, and 3 desserts. How many 3-course meals are possible?
Total = 4 × 6 × 3 = 72 meals
Total = 4 × 6 × 3 = 72 meals
Permutations (Order Matters)
Formula
nPr = n!(n−r)!The number of ordered arrangements of r items chosen from n distinct items.
Worked Example — Permutation
Arrange 3 students from 10 in assigned seats
order matters → nPr
10P3 = 10!(10−3)! = 10!7!
apply formula
= 10 × 9 × 8
cancel 7! terms
720 arrangements
Special case — all n items: nPn = n! (arranging all n items in a line). E.g., 5 people in a row: 5! = 120 ways.
Combinations (Order Does NOT Matter)
Formula
nCr = n!r!(n−r)! = nPrr!The number of unordered selections of r items from n distinct items. Also written as C(n,r) or nCr.
Worked Example — Combination
Choose a committee of 3 from 10 students
order irrelevant → nCr
10C3 = 10!3! × 7! = 10 × 9 × 83 × 2 × 1
apply formula
= 7206
simplify
120 ways
Permutation vs Combination: Decision Guide
| Situation | Order? | Use |
|---|---|---|
| Arranging books on a shelf | Yes | Permutation |
| Creating a PIN code / password | Yes | Permutation |
| First/second/third place in a race | Yes | Permutation |
| Choosing a committee | No | Combination |
| Selecting students for a group | No | Combination |
| Drawing cards from a deck (hand) | No | Combination |
Critical Rule: The key question is: does changing the order produce a different outcome? A committee of {A,B,C} is the same as {B,C,A} → combination. A podium of 1st=A, 2nd=B, 3rd=C is different from 1st=B, 2nd=A, 3rd=C → permutation.
Mathematics · Topic 1.4 · Extended
Worked Examples
These examples cover the range of question types expected in the eAssessment. Show all steps.
EXAMPLE 1A graph has vertices A, B, C, D, E with degrees 2, 3, 4, 3, 2 respectively. Does an Euler circuit exist? Justify.
+
Full Solution
Sum of degrees = 2+3+4+3+2 = 14 = 2 × 7 edges ✓ (consistent)
Odd-degree vertices: B (degree 3) and D (degree 3) — two vertices with odd degree.
By Euler's theorem: An Euler circuit requires ALL vertices to have even degree. Since B and D are odd, no Euler circuit exists.
However, since exactly two vertices are odd, an Euler path exists starting at B and ending at D (or vice versa).
Odd-degree vertices: B (degree 3) and D (degree 3) — two vertices with odd degree.
By Euler's theorem: An Euler circuit requires ALL vertices to have even degree. Since B and D are odd, no Euler circuit exists.
However, since exactly two vertices are odd, an Euler path exists starting at B and ending at D (or vice versa).
EXAMPLE 2How many 4-digit PIN codes can be formed using digits 0–9 if digits cannot repeat?
+
Full Solution
Order matters (PIN 1234 ≠ 4321), so use permutation.
n = 10 digits, r = 4 chosen
10P4 = 10! / (10−4)! = 10! / 6! = 10 × 9 × 8 × 7 = 5040 PIN codes
Alternative method (multiplication principle): 10 choices for 1st digit × 9 for 2nd × 8 for 3rd × 7 for 4th = 5040 ✓
n = 10 digits, r = 4 chosen
10P4 = 10! / (10−4)! = 10! / 6! = 10 × 9 × 8 × 7 = 5040 PIN codes
Alternative method (multiplication principle): 10 choices for 1st digit × 9 for 2nd × 8 for 3rd × 7 for 4th = 5040 ✓
EXAMPLE 3A school committee of 4 is chosen from 7 teachers and 5 students, with exactly 2 teachers and 2 students. How many ways?
+
Full Solution
Order does not matter for committee selection → combinations.
Ways to choose 2 teachers from 7: 7C2 = 7! / (2! × 5!) = (7 × 6) / 2 = 21
Ways to choose 2 students from 5: 5C2 = 5! / (2! × 3!) = (5 × 4) / 2 = 10
By the multiplication principle: Total = 21 × 10 = 210 ways
Ways to choose 2 teachers from 7: 7C2 = 7! / (2! × 5!) = (7 × 6) / 2 = 21
Ways to choose 2 students from 5: 5C2 = 5! / (2! × 3!) = (5 × 4) / 2 = 10
By the multiplication principle: Total = 21 × 10 = 210 ways
EXAMPLE 4Apply Kruskal's algorithm to find the MST of a graph with edges: AB=5, AC=3, AD=8, BC=4, CD=2, BD=7.
+
Full Solution
Sort edges ascending: CD=2, AC=3, BC=4, AB=5, BD=7, AD=8
Step 1: Add CD=2 ✓ (no cycle)
Step 2: Add AC=3 ✓ (no cycle; connects A to C–D)
Step 3: Add BC=4 — check: B not yet connected to tree {A,C,D}, so ✓ add
Now all 4 vertices connected. n−1 = 3 edges added. Stop.
MST edges: CD=2, AC=3, BC=4. Total weight = 9.
Skip: AB=5 (would create cycle A-B-C-A), BD=7, AD=8.
Step 1: Add CD=2 ✓ (no cycle)
Step 2: Add AC=3 ✓ (no cycle; connects A to C–D)
Step 3: Add BC=4 — check: B not yet connected to tree {A,C,D}, so ✓ add
Now all 4 vertices connected. n−1 = 3 edges added. Stop.
MST edges: CD=2, AC=3, BC=4. Total weight = 9.
Skip: AB=5 (would create cycle A-B-C-A), BD=7, AD=8.
EXAMPLE 58 athletes compete. How many ways can the gold, silver, and bronze medals be awarded?
+
Full Solution
Order matters (gold ≠ silver ≠ bronze) → permutation.
8P3 = 8! / (8−3)! = 8! / 5! = 8 × 7 × 6 = 336 ways
8P3 = 8! / (8−3)! = 8! / 5! = 8 × 7 × 6 = 336 ways
EXAMPLE 6From a standard deck of 52 cards, how many 5-card poker hands are possible?
+
Full Solution
Order does not matter in a hand → combination.
52C5 = 52! / (5! × 47!) = (52 × 51 × 50 × 49 × 48) / (5 × 4 × 3 × 2 × 1)
= 311,875,200 / 120 = 2,598,960 hands
52C5 = 52! / (5! × 47!) = (52 × 51 × 50 × 49 × 48) / (5 × 4 × 3 × 2 × 1)
= 311,875,200 / 120 = 2,598,960 hands
EXAMPLE 7A graph has 6 vertices each of degree 4. How many edges does it have? Does an Euler circuit exist?
+
Full Solution
By the Handshaking Lemma: sum of degrees = 2 × |E|
6 × 4 = 24 = 2|E|
|E| = 12 edges
For an Euler circuit: every vertex must have even degree. All vertices have degree 4 (even). If the graph is also connected, an Euler circuit exists.
6 × 4 = 24 = 2|E|
|E| = 12 edges
For an Euler circuit: every vertex must have even degree. All vertices have degree 4 (even). If the graph is also connected, an Euler circuit exists.
Mathematics · Topic 1.4 · Extended
Practice Q&A
Attempt each question before revealing the model answer. Always state whether you are using a permutation or combination, and why.
CALCULATEEvaluate 6! and 8P3.
+
Model Answer
6! = 6 × 5 × 4 × 3 × 2 × 1 = 720
8P3 = 8! / 5! = 8 × 7 × 6 = 336
8P3 = 8! / 5! = 8 × 7 × 6 = 336
DECIDEA password is 3 letters followed by 2 digits (no repeats). How many passwords are possible? (26 letters, 10 digits)
+
Model Answer
Order matters → permutation for each part.
Letters: 26P3 = 26 × 25 × 24 = 15,600
Digits: 10P2 = 10 × 9 = 90
Total = 15,600 × 90 = 1,404,000 passwords
Letters: 26P3 = 26 × 25 × 24 = 15,600
Digits: 10P2 = 10 × 9 = 90
Total = 15,600 × 90 = 1,404,000 passwords
EULERA graph has vertices with degrees 1, 2, 3, 4, 2, 2. Does it have an Euler circuit? An Euler path?
+
Model Answer
Odd degree vertices: degree 1 and degree 3 — that's two odd-degree vertices.
By Euler's theorem: no Euler circuit (not all even), but an Euler path exists (exactly 2 odd vertices), starting at the degree-1 vertex and ending at the degree-3 vertex.
By Euler's theorem: no Euler circuit (not all even), but an Euler path exists (exactly 2 odd vertices), starting at the degree-1 vertex and ending at the degree-3 vertex.
COMBINATIONA school offers 10 elective subjects. A student must choose 3. How many combinations are possible?
+
Model Answer
Order does not matter (choosing subjects, not ranking them) → combination.
10C3 = 10! / (3! × 7!) = (10 × 9 × 8) / 6 = 720 / 6 = 120 combinations
10C3 = 10! / (3! × 7!) = (10 × 9 × 8) / 6 = 720 / 6 = 120 combinations
MSTExplain why a spanning tree on n vertices always has exactly n−1 edges.
+
Model Answer
A tree is a connected graph with no cycles. To connect n vertices with no cycle, each new vertex you add requires exactly one new edge. Starting from 1 vertex, adding n−1 vertices one at a time (each with one edge) gives n−1 edges. If you add more edges, you create a cycle; if fewer, the graph is not connected.
MULTI-STEPHow many ways can 5 people sit around a circular table? (Rotations of the same arrangement are identical.)
+
Model Answer
For circular arrangements, fix one person to eliminate equivalent rotations. Then arrange the remaining 4 people in (5−1)! = 4! = 24 ways.
Note: for a straight line, the answer would be 5! = 120.
Note: for a straight line, the answer would be 5! = 120.
REAL-WORLDA city has 5 districts to connect with water pipes. The costs (in thousands) between pairs are given. Why would you use a MST rather than connecting every pair?
+
Model Answer
A complete graph on 5 vertices has 5(5−1)/2 = 10 edges. Installing all 10 connections would be wasteful and expensive. A minimum spanning tree connects all 5 districts with only 4 edges (n−1) at minimum total cost, ensuring every district gets water without redundant pipelines. The MST gives the most cost-efficient connected network.
VERIFYVerify that nCr = nC(n−r) using n=8, r=3.
+
Model Answer
8C3 = 8! / (3! × 5!) = (8 × 7 × 6) / 6 = 56
8C5 = 8! / (5! × 3!) = (8 × 7 × 6) / 6 = 56
8C3 = 8C5 = 56 ✓
This makes sense: choosing 3 items to include is equivalent to choosing 5 items to exclude.
8C5 = 8! / (5! × 3!) = (8 × 7 × 6) / 6 = 56
8C3 = 8C5 = 56 ✓
This makes sense: choosing 3 items to include is equivalent to choosing 5 items to exclude.
Mathematics · Review
Flashcard Review
Tap each card to reveal the answer. Try to answer from memory first.
State Euler's theorem for an Euler circuit.
An Euler circuit exists if and only if the graph is connected AND every vertex has even degree.
Tap to reveal
When does an Euler path (not circuit) exist?
The graph is connected AND exactly two vertices have odd degree. The path starts at one odd-degree vertex and ends at the other.
Tap to reveal
What is the Handshaking Lemma?
The sum of all vertex degrees equals twice the number of edges: ∑deg(v) = 2|E|.
Tap to reveal
Formula for a permutation nPr.
nPr = n! / (n−r)! — ordered arrangements of r from n items.
Tap to reveal
Formula for a combination nCr.
nCr = n! / (r!(n−r)!) — unordered selections of r from n items.
Tap to reveal
When do you use a permutation vs a combination?
Permutation: order matters (rankings, passwords, arrangements). Combination: order doesn't matter (committees, groups, hands of cards).
Tap to reveal
What is 0! equal to and why?
0! = 1, by definition. It represents the one way to arrange zero objects (doing nothing).
Tap to reveal
What is a minimum spanning tree?
A subgraph that connects all vertices with no cycles and minimum total edge weight. A spanning tree on n vertices has exactly n−1 edges.
Tap to reveal
Describe Kruskal's algorithm in one sentence.
Repeatedly add the cheapest edge that does not create a cycle until all vertices are connected.
Tap to reveal
What is the degree of a vertex?
The number of edges meeting at (incident to) that vertex.
Tap to reveal
How many edges does a complete graph Kn have?
n(n−1)/2 edges — every vertex connects to every other vertex exactly once.
Tap to reveal
Why does nCr = nC(n−r)?
Choosing r items to include is equivalent to choosing n−r items to exclude. Both count the same sets.
Tap to reveal
Difference between Euler path and Hamiltonian path?
Euler path: traverse every edge exactly once. Hamiltonian path: visit every vertex exactly once. Euler has a simple theorem; Hamiltonian does not.
Tap to reveal
State the multiplication counting principle.
If one event can occur in m ways and a second in n ways, both can occur in m × n ways.
Tap to reveal
How many arrangements of all 5 letters in the word MATHS (no repeats)?
5! = 120 arrangements (all 5 distinct letters arranged in a line).
Tap to reveal
Mathematics · Practice Test
Practice Test — 20 Questions
0Score / 20
Q 1 / 20
Correct
Wrong
Score