Overview
Graph theory studies relationships between objects.
A graph consists of vertices joined by edges. The vertices represent objects, and the edges represent connections between them.
For example:
- People can be vertices, with friendships as edges
- Cities can be vertices, with roads as edges
- Rooms can be vertices, with doors as edges
- Numbers can be vertices, with edges joining numbers that satisfy a condition
Graph theory appears often in olympiad and contest problems because many problems about movement, pairing, networks, games, and arrangements can be translated into graph language.
In AMC style problems, a particularly common type asks about walks:
How many ways can we move through a graph in exactly steps?
This module gives the basic vocabulary of graph theory and then spends extra time on walk counting strategies.
What Is a Graph?
A graph is made of two parts:
- A set of vertices
- A set of edges joining pairs of vertices
Formally, a graph is written as
where is the vertex set and is the edge set.
For example, suppose
and
This graph has four vertices and four edges. It forms a cycle:
In this module, unless otherwise stated, graphs are simple and undirected.
That means:
- There is at most one edge between any two vertices
- No edge joins a vertex to itself
- Edges have no direction
A simple undirected graph is the most common type in introductory contest problems.
Vertices and Edges
The points of a graph are called vertices.
The connections between vertices are called edges.
If an edge joins vertices and , we may write it as
Since the graph is undirected,
If there is an edge between and , we say that and are adjacent.
If a vertex lies on an edge , we say that is incident to .
Degree of a Vertex
The degree of a vertex is the number of edges incident to it.
The degree of a vertex is written as
For example, if vertex is joined to , , and , then
A vertex of degree is called an isolated vertex.
The Handshaking Lemma
In any finite undirected graph,
This is called the Handshaking Lemma.
It is true because every edge contributes to the degree of each of its two endpoints. Therefore, every edge is counted exactly twice in the degree sum.
Consequence
The number of vertices with odd degree is even.
Why?
The sum of all degrees is even, since it equals
A sum of integers is even only if it contains an even number of odd terms.
So every graph has an even number of odd degree vertices.
This simple fact is surprisingly useful in contest problems.
Subgraphs
A graph is a subgraph of if its vertices and edges are taken from .
If
and
then is a subgraph of when
and
An induced subgraph is formed by choosing some vertices and keeping every edge from the original graph whose endpoints are both among those chosen vertices.
For example, if a graph has vertices and we choose only , then the induced subgraph on contains all edges among that were already present in the original graph.
Complete Graphs
A complete graph is a graph in which every pair of distinct vertices is joined by an edge.
The complete graph on vertices is denoted
Since every edge is determined by choosing vertices from , the number of edges in is
For example,
has
edges.
A complete subgraph is often called a clique.
Null Graphs and Independent Sets
A null graph is a graph with vertices but no edges.
Equivalently, every vertex is isolated.
An independent set in a graph is a set of vertices with no edges between any two of them.
For example, if no two selected people are friends, then those selected people form an independent set in the friendship graph.
Independent sets are closely related to complements of graphs.
Complement of a Graph
The complement of a graph is the graph with the same vertex set, but with exactly the missing edges.
In other words, two vertices are adjacent in the complement when they are not adjacent in the original graph.
If has vertices and edges, then its complement has
edges.
This is useful because sometimes it is easier to count missing edges than present edges.
Connected Graphs
A graph is connected if every vertex can be reached from every other vertex by following edges.
If a graph is not connected, it breaks into connected components.
A connected component is a largest possible connected subgraph.
For example, a graph made of two separate triangles has two connected components.
Directed Graphs
A directed graph, or digraph, has directed edges.
A directed edge from to is written as
This is different from
Directed graphs are useful for modelling one way roads, tournament results, or processes with allowed directions.
A directed graph is strongly connected if every vertex can be reached from every other vertex by following directed edges in the correct direction.
Weighted Graphs
A weighted graph is a graph whose edges have weights.
The weights may represent:
- Distances
- Costs
- Times
- Probabilities
- Scores etc.
For example, a road map can be modelled by a weighted graph where cities are vertices and road distances are edge weights.
Shortest path problems often use weighted graphs.
Bipartite Graphs
A graph is bipartite if its vertices can be split into two sets, say and , such that every edge connects a vertex in to a vertex in .
There are no edges within , and no edges within .
A graph is bipartite if and only if it has no odd cycle.
Equivalently, a graph is bipartite if and only if its vertices can be coloured using two colours so that adjacent vertices always have different colours.
Complete Bipartite Graphs
The complete bipartite graph
has two parts of sizes and , and every vertex in the first part is joined to every vertex in the second part.
It has
edges.
Planar Graphs
A graph is planar if it can be drawn in the plane so that no edges cross except at vertices.
For example,
is planar, but
is not planar.
Also,
is not planar.
A planar drawing divides the plane into regions called faces. The outside region is also counted as a face.
Euler's Formula for Planar Graphs
For a connected planar graph with
vertices,
edges, and
faces, Euler's formula says
This is one of the main results about planar graphs.
For a connected simple planar graph with
we also have
If the graph is triangle free and planar, then
These inequalities are often used to prove that certain graphs are not planar.
Walks, Trails, Paths, and Cycles
This is one of the most important sections for contest problem solving.
A walk is a sequence of vertices where each consecutive pair is joined by an edge.
Vertices and edges may repeat in a walk.
For example,
is a walk if all the needed edges exist.
A trail is a walk that does not repeat any edge.
A path is a walk that does not repeat any vertex.
A closed walk starts and ends at the same vertex.
A cycle is a closed path, meaning it starts and ends at the same vertex and does not repeat other vertices.
These words are similar, so it is important to distinguish them carefully.
Walk Length
The length of a walk is the number of edges used.
For example,
has length , because it uses the edges
A walk of length has steps.
AMC style questions often ask:
How many walks of length go from one vertex to another?
This means we count sequences of moves, not just simple paths.
Repeating vertices is allowed unless the problem says otherwise.
The Main Walk Counting Idea
When counting walks, the most important question is:
Where can I be after each step?
A walk counting problem is often solved by tracking the number of ways to be at each type of vertex after each move.
This is dynamic programming on a graph.
Instead of listing every walk, we update counts step by step.
Walks on a Small Graph
Suppose a graph has vertices
and edges
This is a path of length :
How many walks of length start at and end at ?
Let
be the number of ways to be at after steps,
be the number of ways to be at after steps,
and
be the number of ways to be at after steps.
Initially,
From , we can only move to .
From , we can move to or .
From , we can only move to .
Therefore,
and
Now work out:
After step,
After steps,
After steps,
After steps,
So there are
walks of length from back to .
They are
and
Walks on a Square
Consider a square with vertices
and edges
How many walks of length start at and end at ?
A direct listing would be annoying, but symmetry makes the problem simple.
At any step, relative to , a walker can be:
- At
- At the opposite vertex
- At one of the two adjacent vertices or
Let
be the number of ways to be at after steps.
Let
be the total number of ways to be at or after steps.
Let
be the number of ways to be at after steps.
Initially,
From , a move goes to one of .
From , a move also goes to one of .
From or , a move goes either to or to .
As such,
and
Now work out:
Therefore, there are
walks of length from back to .
Bipartite Graphs and Parity of Walks
Parity is extremely important in walk problems.
In a bipartite graph, every move switches sides.
If a walk starts in , then:
- After an odd number of steps, it is in
- After an even number of steps, it is in
Therefore, in a bipartite graph, there is no odd length closed walk.
This gives fast zero answers.
Example
A square is bipartite.
Therefore, the number of walks of length from a vertex back to itself is
The walker would need to return to the same side after an odd number of moves, which is impossible.
Walks on Complete Graphs
Complete graphs also appear in counting problems.
In
each vertex is connected to every other vertex, but not to itself.
Suppose we want the number of walks of length from a fixed vertex back to itself.
Let
be the number of walks of length ending at the starting vertex.
Let
be the total number of walks of length ending at any other vertex.
Initially,
To return to the starting vertex at step , we must have been at another vertex at step :
To end at a different vertex at step :
- From the starting vertex, there are choices
- From a different vertex, there are choices that still end at a different vertex
Therefore,
This recurrence solves many complete graph walk problems quickly.
Example
In
how many walks of length start and end at a fixed vertex?
Here,
So
and
Start with
Then
So the number of walks of length from a vertex back to itself is
Walks Using an Adjacency Matrix
For a graph with vertices
the adjacency matrix is the matrix where the entry in row , column is
if is joined to , and
otherwise.
A useful result is:
The entry in row , column of is the number of walks of length from to .
This is a very useful method when the graph is small.
Why the Adjacency Matrix Method Works
The entry in row , column of counts the number of ways to go from to in two steps.
In turn, a two step walk has the form
For each possible middle vertex , we need both:
and
This is what matrix multiplication counts.
Similarly, counts three step walks, and in general counts step walks.
Example Using an Adjacency Matrix
Consider the path graph
Using the vertex order
the adjacency matrix is
Then
The entry in row , column is , so there is exactly one walk of length from to :
The entry in row , column is , so there are two walks of length from back to :
and
Walks vs. Paths
In contest problems, do not confuse walks and paths.
A walk may repeat vertices and edges.
A path may not repeat vertices.
For example, in the graph
the sequence
is a walk from to .
It is not a path, because it repeats vertices and edges.
If a problem asks for 'routes', 'ways to move', or 'walks', repetition is often allowed unless the problem says otherwise.
If a problem asks for 'paths' or says 'without visiting a vertex more than once', then repetition is not allowed.
Euler Trails
An Euler trail is a trail that uses every edge of a graph exactly once.
An Euler circuit is an Euler trail that starts and ends at the same vertex.
For a connected graph with at least one edge:
- An Euler circuit exists if and only if every vertex has even degree
- An Euler trail that is not a circuit exists if and only if exactly two vertices have odd degree
The two odd degree vertices, if they exist, must be the start and end of the Euler trail.
This is another direct application of parity.
Trees
A tree is a connected graph with no cycles.
A forest is a graph with no cycles. Each connected component of a forest is a tree.
For a tree with vertices, the number of edges is
Conversely, a connected graph with vertices and edges is a tree.
Trees are important because there is exactly one path between any two vertices in a tree.
Leaves in Trees
A leaf is a vertex of degree .
Every tree with at least two vertices has at least two leaves.
This is often useful in induction arguments and graph counting problems.
Worked Examples
Example 1
A graph has vertices and edges. What is the sum of the degrees of all vertices?
By the Handshaking Lemma,
Since
the sum of the degrees is
Example 2
Can a graph have exactly three vertices of odd degree?
No.
The number of odd degree vertices in any graph must be even.
Therefore a graph cannot have exactly three odd degree vertices.
Example 3
How many edges does have?
A complete graph on vertices has one edge for each pair of vertices.
So the number of edges is
Example 4
How many edges does have?
In a complete bipartite graph, every vertex in one part is joined to every vertex in the other part.
So
has
edges.
Example 5
A graph is bipartite. How many closed walks of odd length can it have?
It has none.
In a bipartite graph, each step switches sides. After an odd number of steps, a walk must be on the opposite side from where it began.
So it cannot be closed.
Example 6
Consider the triangle graph . How many walks of length start and end at a fixed vertex?
Use the complete graph recurrence with
Let be the number of walks ending at the starting vertex after steps, and the total number of walks ending at one of the other two vertices.
Then
and
Start with
Then
So there are
walks of length from a vertex back to itself.
Example 7
A square has vertices in order. How many walks of length go from to ?
A square is bipartite.
Vertices and are in the same part because they are opposite vertices.
After an odd number of steps, a walk starting at must be in the other part.
Since is odd, it is impossible to end at .
Therefore, the number of walks is
Example 8
A square has vertices in order. How many walks of length go from to ?
Use the same symmetry notation as before:
- is the number of walks ending at
- is the total number ending at or
- is the number ending at
Initially,
The recurrences are
and
Work out:
So the number of walks of length from to is
Problem Solving Methods for Walk Questions
Walk questions can look different, but most are solved using a small set of methods.
Method 1: Track Each Vertex
If the graph is small and asymmetric, keep a separate count for each vertex after each step.
This is the safest method.
Let
be the number of ways to be at each vertex after steps.
Then update using the edges of the graph.
Method 2: Use Symmetry
If several vertices behave the same way, group them together.
For example, in a square starting at , vertices and are symmetric. So instead of tracking and separately, we can track the total number of ways to be at either of them.
This makes the recurrence much shorter.
Method 3: Use Parity
If the graph is bipartite, parity often gives an immediate answer.
A walk switches sides every step.
So:
- Same side requires an even number of steps
- Opposite side requires an odd number of steps
This can quickly show that the answer is .
Method 4: Use an Adjacency Matrix
If the graph has a small number of vertices and the walk length is not too large, form the adjacency matrix.
Then entries of powers of the adjacency matrix count walks.
This method is systematic and works especially well when the graph is fixed.
Method 5: Use Complementary States
Sometimes the exact vertex does not matter. What matters is whether we are:
- At the starting vertex
- At a neighbouring vertex
- At a non neighbouring vertex
- In a certain region
This is common in complete graphs, cubes, regular polygons, and symmetric networks.
Common AMC Style Walk Patterns
AMC 10 and AMC 12 walk problems often use small graphs and a fixed number of steps.
The most common patterns are:
- Moving around a polygon
- Moving on a small network of points
- Walking on the edges of a cube
- Counting routes with exactly moves
- Returning to the starting point
- Reaching an opposite vertex
- Using parity to eliminate impossible cases
The safest approach is to avoid listing all walks. Instead, track the number of ways to be in each state after each step.
Key Contest Insight
Graph theory problems often become much easier after translating the problem into vertices and edges.
For walk counting problems, remember:
- A walk may repeat vertices and edges
- Count by number of steps
- Update possible positions after each step
- Use symmetry whenever possible
- Use bipartite parity to detect impossible walks
The question is rarely about drawing an actual good looking graph. It is usually about choosing the right states to track.
Strategy Tips
- Identify the vertices and edges clearly
- Decide whether the graph is directed or undirected
- Check whether the graph is bipartite
- For walk problems, determine whether repetition is allowed
- Track positions after each step instead of listing walks
- Use symmetry to combine equivalent vertices
- For complete graphs, use a recurrence involving the starting vertex and all other vertices
- For small graphs, consider the adjacency matrix method
- For Euler trail problems, count odd degree vertices
- For tree problems, use the facts that a tree has no cycles and has edges
Common Pitfalls
- Confusing walks with paths
- Forgetting that walks may repeat vertices and edges
- Counting paths when the problem asks for walks
- Ignoring parity in bipartite graphs
- Forgetting that a closed walk starts and ends at the same vertex
- Assuming a graph is connected without checking
- Forgetting that the degree sum is twice the number of edges
- Using Euler trail conditions without checking connectedness
- Treating directed edges as undirected
- Counting rotations or symmetries incorrectly when the graph itself has symmetry
Practice Problems
| Status | Source | Problem Name | Difficulty | Tags | ||
|---|---|---|---|---|---|---|
Module Progress:
Join the Discord Community!
Stuck on a problem, or don't understand a module? Join the Discord and get help with your doubts while making more math friends.
