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 simple 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 graph
A multigraph has 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 usually 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
Six vertices are shown below. If every vertex is joined to every other vertex, how many edges will there be?
Try predicting the answer first.
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.
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 total of all their handshake counts would be 9 × 3 = 27, but the sum of the degrees in any graph must be even.
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, and such a graph can be drawn. 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.
Come back to it later
When you learn something new, it is important to come back to it later. Revisiting an idea after some time has passed helps you discover what you remember, what needs another look, and often makes the idea clearer the second time around. Our handouts are a perfect excuse to do exactly that.
Printable Graphs course
Prefer paper, a tablet, or studying offline? Open the printable booklet for Lesson 1, including space to work and the corresponding answers.
Open Lesson 1 PDF →Additional practice
Ready to return to the ideas from this lesson? The Lesson 1 Examples booklet contains eight extra problems, a challenge, answer checks and fully worked model solutions.
Open additional practice →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.
GRAPH COURSE