HelpContactFor teachers and institutes
>_StemPy Lab
Mock TestsClasses

>_StemPy Lab

Learn. Solve. Code the solutions. Test yourself.

Live examsFree mock exams, timed and rankedEveryone starts together, and your score and rank come the moment it ends.See the exams →
Live examsInternational live exams are comingTell us which exam you want first. Timed practice papers are open now.See what is coming →

Learn

  • Physics
  • Chemistry
  • Mathematics
  • Biology
  • Python Programming
  • Statistics & Data Science
  • Computer Science
  • Space Science and Astronomy
  • Earth and Environmental Science
  • Classes
  • Groups

Practice

  • Problems
  • Quizzes
  • Mock Tests
  • Prepare for an Exam
  • Question Sets
  • Exams
  • Certificates
  • Python Labs
  • AI Practice Generator
  • Student-Created Tests

Community

  • Discussions
  • Resources
  • Notes
  • Glossary
  • Blog

Account

  • Log in
© 2026 senLearn. All rights reserved.HelpFor SchoolsAboutContactPrivacy PolicyTerms of UseRefund Policy
Graph Theory
  1. 1Graphs, degrees and the handshake lemma
  2. 2Trees, bipartite graphs and Euler trails
  3. 3Planar graphs, colouring and Ramsey numbers
  1. Mathematics
  2. /Graph Theory
  3. /Trees, bipartite graphs and Euler trails

Course 30.3·Lesson 2 of 3

Trees, bipartite graphs and Euler trails

A tree is a connected graph with no cycle; with nnn vertices it has n−1n - 1n−1 edges and at least two leaves. A graph is bipartite when its vertices split into two parts with every edge going across, which happens exactly when it has no odd cycle. A connected graph has an Euler circuit when every degree is even, and an Euler trail when exactly two degrees are odd.

about 25 min1 simulation1 practice question1 Python program5 questions to check yourself

This lesson is free to read. Enroll free to keep your place and take the tests.

Lesson 2 of 3Show all lessonsHide
Graph Theory
  1. 1Graphs, degrees and the handshake lemma
  2. 2Trees, bipartite graphs and Euler trails
  3. 3Planar graphs, colouring and Ramsey numbers

Try the code and the simulations beside the lesson.

What you will be able to do

  • use the properties of trees: n−1n - 1n−1 edges, leaves, unique paths;
  • test whether a graph is bipartite, and use Mantel's bound for graphs with no triangle;
  • decide whether an Euler trail or circuit exists, and find one.

Trees

A family tree, the folders on a computer and the pipes of a water supply branch out without loops. A tree is a connected graph with no cycle. A vertex of degree 111 is a leaf.

Facts about a tree with nnn vertices.

  1. Between any two vertices there is exactly one path.
  2. If n≥2n \ge 2n≥2, it has at least two leaves. Take a longest path: its two ends cannot have another neighbour, or the path would be longer or a cycle would appear.
  3. It has exactly n−1n - 1n−1 edges. Remove a leaf and its edge: what is left is a tree with n−1n - 1n−1 vertices. Repeat down to one vertex. This is a proof by induction.

A graph with no cycle that may have several components is a forest. A forest with nnn vertices and ccc components has n−cn - cn−c edges, because each component is a tree.

Cayley's formula. There are nn−2n^{n-2}nn−2 different trees on nnn labelled vertices. For n=4n = 4n=4 that is 161616: the 121212 paths and the 444 stars.

Three trees side by side. The first is a path of five vertices with its two end leaves marked. The second is a star: one centre joined to four leaves. The third is a branching tree of eight vertices with five leaves marked in green. Under each tree its number of vertices and edges is written: 5 and 4, 5 and 4, 8 and 7.

Bipartite graphs

A graph is bipartite when its vertices split into two parts, so that every edge joins the two parts. Think of students and clubs, with an edge when a student is in a club. The complete bipartite graph Km,nK_{m,n}Km,n​ joins each of mmm vertices to each of nnn others. It has mnmnmn edges.

Theorem. A graph is bipartite exactly when it has no cycle of odd length.

Why. Going round a cycle in a bipartite graph, you switch parts at every step, so you return after an even number of steps. Conversely, if there is no odd cycle, colour each vertex by whether its distance from a fixed start is even or odd. No edge then joins two vertices of the same colour.

Mantel's theorem. A graph on nnn vertices with no triangle has at most n24\dfrac{n^2}{4}4n2​ edges.

Proof. Let vvv have the largest degree Δ\DeltaΔ. Its neighbours are not joined to each other, or there would be a triangle. So every edge has an end among the other n−Δn - \Deltan−Δ vertices, and each of those has degree at most Δ\DeltaΔ. Hence E≤(n−Δ)Δ≤n24E \le (n - \Delta)\Delta \le \dfrac{n^2}{4}E≤(n−Δ)Δ≤4n2​, by AM-GM. The bound is reached by Kn/2,n/2K_{n/2, n/2}Kn/2,n/2​ when nnn is even.

Euler trails and circuits

The town of Königsberg had seven bridges joining four land areas. Can a walk cross every bridge exactly once? In 1736 Euler showed that it cannot, and graph theory began.

An Euler trail uses every edge exactly once. An Euler circuit does so and ends where it started.

Euler's theorem. A connected graph (or multigraph) has an Euler circuit exactly when every degree is even. It has an Euler trail that is not a circuit exactly when it has exactly two odd vertices, and the trail then runs from one odd vertex to the other.

Why the degrees must be even. Each time the walk passes through a vertex, it uses one edge in and one edge out. Only the start and the end can use an odd number of edges.

Why even degrees are enough. Start anywhere and walk along unused edges. You can only get stuck back at the start. If some edges are unused, start a new closed walk at a vertex of the first one and splice it in. This method is called Hierholzer's algorithm.

In Königsberg the four land areas had degrees 5,3,3,35, 3, 3, 35,3,3,3. Four odd vertices: no Euler trail.

On the left, a sketch of a river and seven bridges joining four land areas: the north bank, the south bank, an island and the land to the east. On the right, the same map as a multigraph with four vertices and seven edges. The island has degree 5 and the other three land areas have degree 3, so all four vertices are odd.

A walk that visits every vertex once is a different question: a Hamilton cycle. No simple test like Euler's is known for it.

Practise with new numbers

Try it in Python

The program checks two things about a graph given as a list of edges: whether an Euler circuit or trail exists, and whether the graph is bipartite, by colouring outwards from a vertex.

Read it first. Then run it. Which test does the graph pass?

1. Add the edge (0, 2). This makes a triangle. What happens to the bipartite test?

2. Replace the edges with those of K2,4K_{2,4}K2,4​. Predict both answers first.

Common mistakes

  • Forgetting connected. Even degrees give an Euler circuit only in a connected graph (ignoring isolated vertices).
  • Mixing up Euler and Hamilton. Euler uses every edge once; Hamilton visits every vertex once.
  • Counting a forest as a tree. A forest with ccc components has n−cn - cn−c edges, not n−1n - 1n−1.
  • An odd cycle in a "bipartite" graph. One triangle is enough to make two colours impossible.

Remember these

  • A tree on nnn vertices has n−1n - 1n−1 edges, a unique path between any two vertices and, for n≥2n \ge 2n≥2, at least two leaves.
  • Bipartite exactly when there is no odd cycle. Km,nK_{m,n}Km,n​ has mnmnmn edges.
  • No triangle: at most n24\dfrac{n^2}{4}4n2​ edges.
  • Euler circuit: connected and all degrees even. Euler trail: exactly two odd vertices.

Check yourself

Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.

  1. A tree has 151515 vertices. How many edges does it have?
  1. A forest has 202020 vertices and 161616 edges. How many trees make it up?
  1. Is the cycle C7C_7C7​ bipartite?
  1. Does K4K_4K4​ have an Euler trail?
  1. What is the largest number of edges in a graph on 101010 vertices with no triangle?

References

  • D. B. West, Introduction to Graph Theory, Chapter 1 (bipartite graphs, Euler circuits) and Chapter 2 (trees).
  • R. J. Wilson, Introduction to Graph Theory, Chapters 3 and 4.

Enroll free in Graph Theory

Every lesson is open to read. Enrolling also lets you:

  • Mark lessons done and carry on where you stopped.
  • Take the tests of this lesson and its course.
  • Count the course towards the certificate for its chapter.
No payment. You can leave at any time.

Problems (4)

A water company lays pipes as a tree: every junction is joined to the network, and there are no…Hard · High School (11–12) · by StemPy Lab
In a group of 6 students, some pairs are friends…Advanced · High School (11–12) · by StemPy Lab
A river town has five land areas, A, B, C, D and E, joined by ten bridges…Hard · High School (11–12) · by StemPy Lab
Next: lesson 3Planar graphs, colouring and Ramsey numbers
← Graph Theory
← Graphs, degrees and the handshake lemmaPlanar graphs, colouring and Ramsey numbers →

Discussion (0)

Log in to join the discussion.

Loading…

The complete bipartite graph K_(m,n) joins each of m left vertices to each of n right vertices…
Advanced · High School (11–12) · by StemPy Lab

Python Labs (1)

Euler and two coloursPython Lab · by StemPy Lab