A graph is a set of vertices joined by edges. The degree of a vertex counts the edges meeting there, and the degrees control whether you can trace the graph without lifting your pen.
On this page
Before you start
This page is easier if you are comfortable with:
What this topic covers
The handshaking lemma (handshaking lemma) says degrees sum to 2E. Whether you can traverse every edge once depends on Euler circuits and trails ; trees have V − 1 edges. Specific results: bipartite graphs , Hall’s marriage theorem , max-flow min-cut and colouring theorems .
Each part of this topic has its own page with the formula, worked examples and a solver: Chromatic polynomial of a cycle , Max-flow min-cut theorem, Hall's marriage theorem, Brooks and four-colour theorems, Cayley's formula (labelled trees) , Bipartite graphs, Dirac's theorem (Hamiltonian cycle) .
Closely related topics: Sets and Venn diagrams, Logic and truth tables , Matrices , Modular arithmetic .
What is it used for? A graph is a set of vertices joined by edges. Graph theory studies degrees, paths, cycles, trees and colouring.
Modelling road, computer and social networks. Deciding whether a route can use every edge once. Colouring maps and scheduling.
How to solve it
List the vertices and count the degree of each. Handshaking lemma: the degrees add up to twice the number of edges. A graph is connected if you can get from any vertex to any other. Euler circuit: connected and all degrees even. Euler trail: connected with exactly two odd vertices.
Worked examples
The examples marked with a button were worked out by the solver on this page. You can try each one yourself.
Example 1: graph with edges AB, BC, CD, DA, AC Worked out by the solver on this page. Press the button to try it yourself.
Try this in the solver: graph with edges AB, BC, CD, DA, AC
Graph theory Answer checked
Answer
4 vertices, 5 edges; degrees A=3, B=2, C=3, D=2; connected \text{4 vertices, 5 edges; degrees A=3, B=2, C=3, D=2; connected} 4 vertices, 5 edges; degrees A=3, B=2, C=3, D=2; connected Vertices and edges
V = { A , B , C , D } , ∣ E ∣ = 5 : A B , B C , C D , D A , A C
Degree of each vertex (number of edges meeting there)
deg ( A ) = 3 , deg ( B ) = 2 , deg ( C ) = 3 , deg ( D ) = 2
Adjacency matrix
A B C D A 0 1 1 1 B 1 0 1 0 C 1 1 0 1 D 1 0 1 0
Handshaking lemma
The degrees always add up to twice the number of edges.
∑ deg = 3 + 2 + 3 + 2 = 10 = 2 × 5
Connected?
Yes, every vertex can be reached from every other.
Euler trails and circuits
Euler trail exists (not a circuit): exactly two odd vertices, A and C, so start at one and end at the other.
Check: the row sums of the adjacency matrix equal the degrees
3 , 2 , 3 , 2 ✓
Example 2: graph with edges AB, BC, CA, DE Worked out by the solver on this page. Press the button to try it yourself.
Try this in the solver: graph with edges AB, BC, CA, DE
Graph theory Answer checked
Answer
5 vertices, 4 edges; degrees A=2, B=2, C=2, D=1, E=1; not connected \text{5 vertices, 4 edges; degrees A=2, B=2, C=2, D=1, E=1; not connected} 5 vertices, 4 edges; degrees A=2, B=2, C=2, D=1, E=1; not connected Vertices and edges
V = { A , B , C , D , E } , ∣ E ∣ = 4 : A B , B C , C A , D E
Degree of each vertex (number of edges meeting there)
deg ( A ) = 2 , deg ( B ) = 2 , deg ( C ) = 2 , deg ( D ) = 1 , deg ( E ) = 1
Adjacency matrix
A B C D E A 0 1 1 0 0 B 1 0 1 0 0 C 1 1 0 0 0 D 0 0 0 0 1 E 0 0 0 1 0
Handshaking lemma
The degrees always add up to twice the number of edges.
∑ deg = 2 + 2 + 2 + 1 + 1 = 8 = 2 × 4
Connected?
No, the graph splits into separate parts.
Euler trails and circuits
No Euler trail: the graph is not connected.
Check: the row sums of the adjacency matrix equal the degrees
2 , 2 , 2 , 1 , 1 ✓
Example 3: graph with edges AB, BC, CD, DA Worked out by the solver on this page. Press the button to try it yourself.
Try this in the solver: graph with edges AB, BC, CD, DA
Graph theory Answer checked
Answer
4 vertices, 4 edges; degrees A=2, B=2, C=2, D=2; connected \text{4 vertices, 4 edges; degrees A=2, B=2, C=2, D=2; connected} 4 vertices, 4 edges; degrees A=2, B=2, C=2, D=2; connected Vertices and edges
V = { A , B , C , D } , ∣ E ∣ = 4 : A B , B C , C D , D A
Degree of each vertex (number of edges meeting there)
deg ( A ) = 2 , deg ( B ) = 2 , deg ( C ) = 2 , deg ( D ) = 2
Adjacency matrix
A B C D A 0 1 0 1 B 1 0 1 0 C 0 1 0 1 D 1 0 1 0
Handshaking lemma
The degrees always add up to twice the number of edges.
∑ deg = 2 + 2 + 2 + 2 = 8 = 2 × 4
Connected?
Yes, every vertex can be reached from every other.
Euler trails and circuits
Euler circuit exists: the graph is connected and every vertex has even degree.
Check: the row sums of the adjacency matrix equal the degrees
2 , 2 , 2 , 2 ✓
Special cases
A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.
Degree sum Edges AB, BC, CD, DA, AC: degrees 3, 2, 3, 2 sum to 10
2 × 5 edges.
Edges Degree sum 10: 5 edges
Sum ÷ 2.
Euler trail Exactly 2 odd vertices: yes
A and C have degree 3.
Euler circuit AB, BC, CD, DA: all degrees even
Circuit exists.
Word problems
Count degrees, use the handshaking lemma, and use the number of odd vertices to decide if an Euler trail or circuit exists.
Degrees Degrees in the graph with AB, BC, CD, DA, AC.
A 3 B 2 C 3 D 2 Check: sum 10 ✓ 10
Edges Number of edges.
Sum ÷ 2 5 Check: ✓ 5
Euler trail Higher Is there an Euler trail?
Odd vertices 2 (A and C) Check: yes, from A to C ✓ 2
Euler circuit Higher AB, BC, CD, DA.
Degrees all 2 Check: 4 edges, all even ✓ 4
Common mistakes
Degree sum equals E sum = 5 ✗
sum = 2E = 10 ✓
Each edge counted twice.
Euler circuit with odd vertices two odd vertices ✗
needs all even ✓
Trail only.
Forgetting separate components one component ✗
count components ✓
A graph can be disconnected.
Counting a loop once one ✗
two ✓
A loop adds 2.
Exam tips
Σdeg = 2E.
All even: Euler circuit.
Two odd: Euler trail.
Tree: E = V − 1.
Draw the graph.
Practice questions
Try each one on paper, then open the answer. Use the solver above to see the full working.
1. Edges if the degree sum is 14 Foundation 7
2. Edges of K₅ Foundation 10
3. Edges of a tree on 9 vertices Foundation 8
4. Degree sum if E = 12 Higher 24
5. Odd vertices in a graph with degrees 3, 3, 2, 2 Higher 2
6. Edges of a 4-cycle Higher 4
Practice generator Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.
Foundation Higher Mixed New question
Solve: …
The practice generator needs JavaScript.
Key terms
Vertex A point. Edge A link. Degree Edges at a vertex. Euler trail Uses every edge once. Tree Connected with no cycles. Bipartite Two sets of vertices.
Frequently asked questions
What is the handshaking lemma? The sum of the degrees is twice the number of edges.
When does an Euler circuit exist? When the graph is connected and all vertices have even degree.
How many edges does a tree have? V − 1.
Which page covers the lemma? handshaking lemma.
Which page covers Euler trails? Euler circuits and trails.
Which page covers trees? edges in a tree.