Back to the on-screen lesson ·
A walk that uses every edge once exists exactly when the degrees allow it, and the count of odd-degree vertices is the whole of the test.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to decide whether a connected graph has a walk using every edge exactly once, closed or open, by counting its vertices of odd degree — zero for a closed walk, exactly two for an open one — and say why the walk must begin and end at the odd vertices when there are two. You will also be able to give the argument that forces every degree to be even, check the connectivity hypothesis that is easy to drop, and say why the corresponding question about visiting every vertex has no such test.
The handshake lemma from lesson 20, and with it the fact that the number of odd-degree vertices is always even. That fact is why the condition in this lesson can be exactly two odd vertices and never exactly one, and it is worth having in mind before the condition is stated.
An Euler circuit is a closed walk using every edge of a graph exactly once; an Euler path is the same thing allowed to finish somewhere else. A Hamilton cycle, by contrast, visits every vertex exactly once — a question that sounds similar and behaves completely differently.
Euler's theorem. A connected graph has an Euler circuit if and only if every vertex has even degree. It has an Euler path, open at both ends, if and only if exactly two vertices have odd degree — and the walk must start at one of them and finish at the other.
Why the degrees decide it. Each time a walk passes through a vertex it arrives on one edge and leaves on another, using them up in pairs. If the walk uses every edge exactly once, then every edge at that vertex has been paired, so the degree is even. The starting vertex is no exception in a closed walk: the first edge out pairs with the last edge in.
Open the walk up and exactly two vertices lose their pairing — the start has one unpaired edge out, the finish one unpaired edge in — which is why the open version allows exactly two odd vertices. And exactly two rather than one or three because the handshake lemma forbids an odd number of odd vertices.
Necessary and sufficient. The argument above shows the condition is necessary. That it is also sufficient is harder and is the part Euler actually had to prove: in a connected graph with all degrees even, take any closed walk that does not repeat an edge, and if edges remain, some vertex on the walk still has unused edges — splice a second closed walk in there and repeat. The process ends because there are finitely many edges.
A condition that is both necessary and sufficient, and checkable by counting, is rare. The corresponding question about vertices — does a Hamilton cycle exist? — has no such condition known, and is one of the standard hard problems of the subject. Two questions one word apart, with completely different answers.
Another way: steps
To decide whether a walk using every edge exists:
Another way: example
The bridges of Königsberg: four land masses, all of odd degree. Four is neither zero nor two, so there is no walk of either kind — which is the answer to the puzzle that started the subject, and it was reached by counting four numbers rather than by trying routes.
| Euler circuit | Hamilton cycle | |
|---|---|---|
| Visits every | edge, once | vertex, once |
| Condition | connected, all degrees even | none known |
| Deciding it | count the degrees | no efficient method known |
The two questions are one word apart and are not comparable in difficulty. Euler's is settled by adding up degrees, which takes no longer than reading the graph. Hamilton's has no known test short of searching, and the search grows faster than any polynomial in the size of the graph; deciding it is one of the standard hard problems.
It is worth pausing on how little warning the statements give of that gap. Nothing in the phrasing suggests one is easy and the other is not, and a learner who assumes symmetry between them will spend a long time looking for a degree condition that does not exist. Where a small change in a question changes its difficulty completely is itself a thing to notice.
Forgetting connectivity. Two separate triangles have all degrees even and no walk can cross from one to the other.
Allowing one odd vertex. Impossible: the count of odd vertices is always even.
Starting an open walk in the wrong place. With two odd vertices the walk must begin at one and end at the other; beginning elsewhere strands edges.
Treating the Hamilton question as the same question. A graph may have an Euler circuit and no Hamilton cycle, or a Hamilton cycle and no Euler circuit. Neither implies the other.
The theorem has two hypotheses and the second one is easy to drop, because a picture drawn on one page usually looks connected. A graph made of two disjoint squares has every degree even and no walk using all eight edges, since no walk can get from one square to the other. Quoting a conclusion whose hypotheses were not both checked is the standard way a correct-looking argument in this course goes wrong, and this theorem is where it is easiest to do.
Four land masses joined by seven bridges. The degrees are $5$, $3$, $3$ and $3$.
Read the degrees off the map.
All four are odd. A closed walk needs zero odd vertices and an open walk needs exactly two.
Compare the count with the two allowed values.
Four is neither, so no walk crosses every bridge exactly once. No route was tried, and none needed to be — the count settles every possible route at once.
An impossibility proof over all routes.
A path of four vertices in a line has degrees $1, 2, 2, 1$: two odd vertices, at the ends.
Count the odd ones.
Two is too many for a closed walk, so there is no Euler circuit.
Zero odd vertices is what a circuit needs.
Two is exactly right for an open one, and the walk must run from one end to the other — which is obvious here and is the general rule: the walk starts at one odd vertex and finishes at the other.
The theorem also tells you where to start.
Every vertex is joined to the other four, so every degree is $4$.
Degrees first.
All even, and the graph is connected — every pair is joined directly, so certainly every pair is reachable.
Check both hypotheses, not just the degrees.
So an Euler circuit exists, and it uses all $10$ edges. Compare the complete graph on four vertices, where every degree is $3$ and there is no such walk: the parity of $n - 1$ decides it, so complete graphs on an odd number of vertices have Euler circuits and those on an even number do not.
Take a square with its four corners joined in a cycle. Count its odd-degree vertices, then say whether a closed walk can use every edge exactly once — $1$ for yes, $0$ for no.
| Number | |
|---|---|
| Vertices of odd degree | |
| Closed walk using every edge once |
Does a path of four vertices in a line have a closed walk using every edge exactly once?
How many vertices of odd degree has the complete graph on four vertices?
Answer:
Put in order the steps of the argument that a closed walk using every edge exactly once forces every degree to be even.
Number the steps in order (write the number in the box):
Mark every connected graph below that has a walk using each edge exactly once, allowed to finish somewhere other than where it started.
This task has no paper form; do it on a device.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Take two triangles sharing a single vertex. Count its odd-degree vertices, then say whether a closed walk can use every edge exactly once — $1$ for yes, $0$ for no.
| Number | |
|---|---|
| Vertices of odd degree | |
| Closed walk using every edge once |
You can decide the existence of an Euler circuit or path by counting odd-degree vertices, and say where an open walk has to start. Say in your own words why passing through a vertex uses its edges two at a time, and why the number of odd vertices can never be one. Next: the graphs that can be drawn in the plane with no edge crossing another.
10. Your turn: does the complete graph on five vertices have an Euler circuit?, step 3