How to Use Graph Theory to Solve SASMO Problems Without a Graph
You sit down at the SASMO paper, and the problem looks like a tangle of relationships. Five friends, each with a different favorite subject. Some pairs study together, others don’t. Your instinct is to draw a diagram, but the problem doesn’t give you one. It feels like you’re missing a puzzle piece. The good news? You don’t need a picture at all. You can solve these problems using graph theory, a branch of math that turns relationships into pure logic. And in this guide, we’ll show you exactly how to do it.
Graph theory lets you solve SASMO problems by modeling connections as vertices and edges, even when no diagram is provided. You’ll learn to identify graph structures in word problems, apply simple rules like handshaking lemma and bipartite graphs, and avoid common traps. This skill turns messy relationship questions into clean, solvable puzzles.
What Is Graph Theory, Really?
Graph theory is the study of points and the lines that connect them. In math competitions, a “graph” doesn’t mean a bar chart or a pie chart. It means a collection of vertices (the points) and edges (the connections between them).
Think about a problem that says, “In a group of 6 students, each student shakes hands with exactly 3 others.” That’s a graph. The students are the vertices. The handshakes are the edges. You don’t need to draw the handshake circle to know that the total number of handshakes is 9. How? Because each handshake involves two people, and the sum of all handshakes counted by each person is 6 times 3, which equals 18. Divide by 2, and you get 9. That’s the handshaking lemma in action.
Why SASMO Loves Graph Problems
SASMO problems often test your ability to see structure where there is none drawn. They give you a paragraph about friendships, train routes, or tournament matchups. They want to see if you can translate that paragraph into a graph model. If you can, the problem becomes a set of rules you already know. If you can’t, it feels like a confusing mess.
Graph theory shows up in these SASMO topics:
- Combinatorics and counting problems – Counting pairs, groups, or paths.
- Logic and reasoning problems – Figuring out who is connected to whom.
- Network or travel problems – Finding the shortest route or checking if a path exists.
- Matching and pairing problems – Assigning tasks or partners without conflict.
If you have a strong foundation in understanding patterns and sequences, graph theory becomes a natural extension. You start seeing patterns in connections, not just numbers.
The Core Ideas You Need
Before we jump into solving, let’s lay out the building blocks. These are the concepts that will appear in nearly every SASMO graph theory problem.
| Concept | What It Means | Common SASMO Application |
|---|---|---|
| Vertex | A point in the graph (a person, a city, a number) | Representing each item in a set |
| Edge | A connection between two vertices | A handshake, a friendship, a road |
| Degree | The number of edges connected to a vertex | How many friends a person has |
| Handshaking Lemma | Sum of all degrees equals twice the number of edges | Finding total connections |
| Path | A sequence of edges from one vertex to another | A route through a network |
| Cycle | A path that starts and ends at the same vertex without repeating edges | A loop in a tournament |
| Bipartite Graph | Vertices split into two groups, edges only between groups | Matching problems |
The handshaking lemma is your best friend. It’s simple, but it unlocks many problems. For example: “In a party of 10 people, each person shakes hands with an even number of people. Prove that the total number of handshakes is a multiple of 5.” The sum of degrees is even (because all degrees are even), so the number of edges is half of that, which could be a multiple of 5. You don’t draw a thing.
How to Spot Graph Problems in SASMO
Not every problem screams “graph.” You have to train your eye. Here are the clues:
- The problem mentions pairs, groups, or connections.
- It talks about relationships like “knows,” “plays against,” “is connected to.”
- It asks for the number of ways to travel, the minimum number of connections, or whether a certain arrangement is possible.
- It gives you constraints like “no two friends share the same hobby” or “each student is in exactly two clubs.”
When you see these, pause. Ask yourself: “Can I represent each item as a vertex and each relationship as an edge?” If yes, you have a graph problem.
Solving Without Drawing: A Step-by-Step Process
You don’t need a diagram. You need a mental model. Here is a process that works.
- Identify the vertices. List every distinct object, person, or location. Give each a label (A, B, C, or 1, 2, 3).
- Identify the edges. For each pair, decide if there is a connection. Write it as a pair (A, B).
- Count degrees. For each vertex, count how many edges touch it. Write the degree next to the label.
- Apply the handshaking lemma. Sum all degrees. Divide by 2. That’s the number of edges.
- Check for special structures. Is the graph complete? Bipartite? A tree? These have known properties.
- Answer the question. Use the numbers you have.
Let’s test this with a real SASMO-style problem.
Problem: In a school, there are 8 clubs. Each club has exactly 3 members. Each student is in exactly 2 clubs. How many students are there?
Step 1: Vertices could be clubs or students. We have two types. This is a bipartite graph. Let’s make clubs one set and students the other.
Step 2: Edges represent membership. Each club connects to its 3 members. So there are 8 clubs times 3 edges, which equals 24 edges from the club side.
Step 3: Each student is in 2 clubs, so each student vertex has degree 2.
Step 4: Handshaking lemma says sum of degrees equals 2 times edges. Sum of degrees for all students is 2 times number of students. Sum of degrees for all clubs is 8 times 3, which is 24. Total sum of degrees is 24 (from clubs) plus 2S (from students). But total sum of degrees also equals 2 times 24, which is 48. So 24 + 2S = 48. That gives 2S = 24, so S = 12.
Answer: There are 12 students.
No drawing required. Just logic.
Common Mistakes and How to Avoid Them
Even experienced competitors slip up. Here are the pitfalls to watch for.
| Mistake | Why It Happens | How to Fix It |
|---|---|---|
| Counting edges twice | Forgetting that each edge connects two vertices | Always divide the sum of degrees by 2 |
| Missing a vertex | Overlooking a person or item in the problem | List all items before you start |
| Confusing degree with edges | Thinking degree equals number of edges | Degree is per vertex; edges are total |
| Assuming a graph is simple | Not considering loops or multiple edges | Read the problem carefully for special cases |
| Forgetting bipartite structure | Treating a two-set problem as one set | Identify two distinct groups early |
One more tip: if the problem feels impossible, check for a hidden bipartite structure. Many SASMO problems split the set into two groups, like boys and girls, or cities and roads. Once you see the split, the solution often falls into place.
Expert Advice: “When you encounter a SASMO problem about relationships, write down the vertices first. Don’t try to visualize the whole graph. Just list the points. Then connect them one by one. The pattern will emerge. Most students panic and draw messy diagrams. You don’t need to. The math does the work for you.” – Coach Maria, 5-time SASMO medalist coach
Putting It All Together: A Practice Problem
Try this one on your own. Then check the solution.
Problem: Five friends – Alice, Ben, Carla, Dan, and Eva – are at a party. Each person shakes hands with exactly two other people. No two people shake hands more than once. Is it possible for Alice to shake hands with Ben, Carla to shake hands with Dan, and Eva to shake hands with Alice? If so, how many total handshakes occur?
Solution: Let’s model this. Vertices: A, B, C, D, E. We know each has degree 2. The sum of degrees is 5 times 2, which is 10. So the number of edges is 5. The given handshakes are (A, B), (C, D), (E, A). That’s 3 edges. We need 2 more edges to reach 5. Also, each vertex must end up with degree 2. Currently, A has degree 2 (with B and E), so A is done. B has degree 1, C has degree 1, D has degree 1, E has degree 1. We need to add edges so that B, C, D, and E each gain one more degree. The only way is to connect B to C and D to E, or B to D and C to E, or B to E and C to D. But E already has degree 1, so if we connect B to E, E would have degree 2, and then D and C would need to connect to each other. That works. So one possible graph is edges: (A,B), (C,D), (E,A), (B,E), (C,D) is already there, wait, we already have (C,D). Let’s redo. We need two more edges. Options: (B,C) and (D,E), or (B,D) and (C,E), or (B,E) and (C,D) but (C,D) is already there. If we use (B,E) and (C,D) again? No, no repeats. So the only valid set is (B,C) and (D,E). That gives each of B, C, D, E degree 2. Yes, it is possible. Total handshakes are 5.
When Graph Theory Meets Other SASMO Topics
Graph theory doesn’t live in a bubble. It connects to other areas you’re already studying. For example, how to use the pigeonhole principle to solve tricky SASMO questions often works hand in hand with graph models. If you have a graph with many vertices and limited edges, the pigeonhole principle can tell you that some vertex must have a certain degree.
Similarly, combinatorics made simple covers counting principles that directly apply to counting edges and paths in graphs. The more you practice graph theory, the stronger your combinatorics becomes.
And if you’re working on building your SASMO competition toolkit, add these graph theory facts to your mental list:
- In any graph, the number of vertices with odd degree is even.
- A complete graph with n vertices has n(n-1)/2 edges.
- A tree (a connected graph with no cycles) with n vertices has exactly n-1 edges.
Train Your Graph Theory Instinct
The best way to get comfortable is to practice. Start with simple problems. For each one, force yourself to write the vertices and edges before you do any math. Don’t peek at the diagram if one exists. Cover it up.
Here are three ways to practice without a coach:
- Rewrite problems. Take a SASMO word problem and rewrite it as a list of vertices and edges.
- Check your work. After solving, verify using the handshaking lemma. If the sum of degrees isn’t even, you made a mistake.
- Explain it to a friend. Teaching someone else forces you to clarify your own thinking.
You can also try the weekly SASMO problem challenge to get fresh graph theory problems regularly. The more you see them, the faster you’ll recognize them.
Your Next Step
Graph theory is a secret weapon for SASMO. It turns messy relationship problems into clean, solvable equations. You don’t need to be an artist. You don’t need to draw a single line. You just need to see the structure.
Start with the next SASMO problem you encounter. Ask yourself: “Where are the vertices? Where are the edges?” Write them down. Apply the handshaking lemma. Watch the answer appear.
You’ve got this. Now go practice.