A graph is just dots and lines
A graph is made of dots and lines.
In graph theory, the dots are called vertices and the lines joining them are called edges.
The exact position of the dots usually does not matter. What matters is which vertices are connected to which.
A graph
Each dot is called a vertex (plural vertices), and the lines joining them are called edges.
Quick check: How many vertices does this graph have? How many edges?
Reveal answer
There are 3 vertices and 2 edges.
Graphs can take very peculiar forms. Just a bunch of vertices with no edges, or a single vertex with multiple loops coming out of it. When studying graphs, mathematicians often limit the graphs to so called simple graphs.
Simple graph
A simple graph has no loops and no repeated edges between the same pair of vertices.
Multigraph
A multigraph can have loops or repeated edges between the same pair of vertices.
Same graph, different picture
A graph can be drawn in many different ways. Moving the vertices around, changing the lengths of the edges, or even making edges cross does not change the graph. What matters is the pattern of connections.
Challenge: Can two drawings look completely different but still represent exactly the same graph?
Graph A
Graph B
Question: Do Graph A and Graph B represent the same graph? How can you tell?
Reveal answer
Yes. Graph B can be obtained from Graph A by rotating and adjusting the lengths of the edges.
Same number of dots and lines — but the same graph?
Both of the graphs below have four vertices and four edges. Does that mean they represent the same graph?
Graph C
Graph D
Question: Do Graph C and Graph D represent the same graph? Try to explain how you know.
Reveal answer
No. In Graph C, two edges meet at every vertex. In Graph D, one vertex has three edges meeting it and another has only one. Their connection patterns are different, so they cannot be the same graph.
The degree of a vertex
Look again at Graphs C and D. A useful way to describe a vertex is to count how many edges meet there.
Graph C
Graph D
In Graph C every vertex has degree 2. In Graph D the degrees are 3, 2, 2 and 1.
Definition
Degree of a vertex
💡
The degree of a vertex is the number of edges that meet at that vertex.
Check: Look back at Graph A. What are the degrees of its four vertices?
Reveal answer
The four degrees are 3, 3, 2 and 2.
The handshake puzzle
Imagine a group of people at a party. We draw one vertex for each person, and draw an edge whenever two people shake hands.
The handshakes between Alice, Ben, Charlie, Dom and Ethan have been recorded on the graph:
Think about it: How many people did each person shake hands with? Now add those five numbers together. There were only 4 handshakes, so why does your total come to something different?
Reveal answer
Alice shook hands with 2 people, Ben with 1, Charlie with 3, Dom with 1 and Ethan with 1. So the total is 2 + 1 + 3 + 1 + 1 = 8.
Every handshake involves two people, so every edge is counted twice when we add all the degrees.
Important rule
The degree-sum rule
sum of the degrees = 2 × number of edges
Every edge meets two vertices, so every edge is counted twice when we add all the vertex degrees.
An impossible party?
At a party, with any number of guests, could exactly one person have shaken hands with an odd number of people?
Reveal answer
No — it is impossible.
The most useful fact here is that the sum of all the degrees is twice the number of edges, so it must be even.
If exactly one vertex had odd degree (only one person had shaken hands with an odd number of people), while all the others had even degree, the total would be odd, since
odd + even + even + … + even = odd
but we know the total has to be even, which contradicts the fact above.
The result we have discovered is known as the Handshaking Lemma. This simple observation turns out to be surprisingly powerful.
Theorem
Handshaking Lemma
💡
Every graph has an even number of vertices of odd degree.
Building a graph
Imagine six vertices. If every vertex is joined to every other vertex, how many edges will there be?
Try predicting the answer first.
Another way to ask this question is: how many different pairs can we choose from six objects? Counting & Combinatorics explores exactly this kind of problem.
Practice Puzzles
1. Get creative
The most important practice is to get your hands dirty. Draw some graphs and try to describe them in terms of vertices and edges. Experiment with different shapes and arrangements.
2. Read a graph
Look at the graph below.
Try answering these questions by reading the graph.
a) How many edges are there?
b) Add all the degrees together. What do you get?
c) Which vertices have odd degree?
Reveal answer
There are 7 edges. The degrees add to 14, which is twice the number of edges. The odd-degree vertices are A and C.
3. Draw your own graph
Draw a graph with 6 vertices in which exactly 4 vertices have odd degree. Can you do it using exactly 5 edges?
💡
Reveal answer
There are many possible answers. One example uses the edges AB, AC, AD, BE and CF.
The degrees are 3, 2, 2, 1, 1, 1, so exactly four vertices have odd degree.
Why use the degree rule? For a small graph like this, drawing examples is useful. But if the graph had dozens or hundreds of vertices, trying to draw every possibility would quickly become impractical. The degree-sum rule lets us reason about what is possible using numbers alone, so the same idea still works when the graph becomes much larger.
4. The party of nine
Nine people go to a party. Each person claims that they shook hands with exactly 3 other people. Could everyone be telling the truth? Explain your answer.
Reveal answer
No. The Handshaking Lemma says that the sum of all vertex degrees must be even, because every edge contributes 2 to the total. Here the claimed total would be 9 × 3 = 27, which is odd, so everyone cannot be telling the truth.
5. Degree-sequence detective
Graph X: 4, 3, 2, 2, 1
Graph Y: 3, 2, 2, 1, 1
Could both graphs exist?
Reveal answer
X is possible, but Y is impossible.
For X, the degrees add to 12, so the degree-sum test does not rule it out. Here is one graph that actually has degree sequence 4, 3, 2, 2, 1.
For Y, the degrees add to 9, which is odd, so no such graph can exist.
Challenge
Is knowing the degrees of all the vertices enough to tell you exactly what a graph looks like?
Reveal answer
No. Six vertices of degree 2 could form one six-cycle, or two separate triangles. The degree list is the same, but the graphs are different.
So a degree list tells us something important about a graph, but it does not tell us exactly how the vertices are connected.
Download the printable lesson materials, practice and answers for What Is a Graph?.
Find the resources →What did you think?
Whether you explored this together or worked independently, we would love to hear from both learners and parents. Tell us what you enjoyed, what was confusing, or what you would like to see next.
Share your feedback
The form is short and you do not need to give your name.