Lesson 9 ~45 min Introduction to Networks · Path +95 XP

The Degree Rule

Searching for an Eulerian trail can take a long time and, if none exists, it never finishes. Counting the odd-degree vertices takes seconds and settles the question completely, which is the difference between a search and a theorem.

Today's hook: Given a network with fifty edges, you could spend an hour hunting for a route covering every one of them. Or you could count how many vertices have an odd degree, which takes half a minute and tells you not only whether a route exists but where it has to begin.

0/5QUESTS

Think First

warm-up

A journey passes through a vertex without stopping. How many of that vertex's edges does it use on that pass? Now: what does that force about the degree of any vertex that is not the start or the finish?

Record your answer in your workbook.

The Big Idea

+5 XP to read

For a connected graph, count the vertices of odd degree. Zero means an Eulerian circuit exists, starting anywhere. Exactly two means an Eulerian trail exists, running from one odd vertex to the other. Any other count means neither.

$$0 \to \text{circuit}, \qquad 2 \to \text{trail}, \qquad \text{more} \to \text{neither}$$

There is no case for one odd vertex, because Lesson 2 proved the number of odd vertices is always even. So the only counts that can occur are $0$, $2$, $4$, $6$ and so on, and only the first two are any use.

$0 \to \text{circuit}, \ 2 \to \text{trail}$

Connected first

The rule assumes it. A disconnected graph with edges in two components fails whatever the degrees say.

The odd ones are the ends

With two odd vertices, the trail must start at one and finish at the other. There is no choice about it.

Check the degree sum

Add the degrees before counting the odd ones. An odd total means you have miscounted.

What You'll Master

objectives

Know

that a connected graph has an Eulerian circuit exactly when every vertex has even degree
that a connected graph has an Eulerian trail but no circuit exactly when exactly two vertices have odd degree
that a connected graph with four or more odd vertices has neither

Understand

why a vertex that is passed through uses its edges in pairs, forcing an even degree
why the two odd vertices, when there are two, must be the start and the finish
why the rule cannot be applied to a disconnected graph however favourable its degrees are

Can Do

decide from the degrees alone whether a connected graph has an Eulerian circuit, an Eulerian trail or neither
state where such a journey must start and finish
determine how many edges must be added to make a graph have an Eulerian trail or circuit

Words You Need

vocabulary

Odd vertexA vertex whose degree is an odd number.

Even vertexA vertex whose degree is an even number.

Necessary conditionSomething that must hold if a claim is true. Failing it disproves the claim.

Sufficient conditionSomething that guarantees a claim. Satisfying it proves the claim.

Route inspectionThe problem of covering every edge with as little repetition as possible when no Eulerian trail exists.

Passing Through Uses Edges in Pairs

+5 XP to read

Take a vertex that a journey passes through without starting or finishing there. Each pass arrives along one edge and departs along another, so each pass uses exactly two of that vertex's edges.

An Eulerian journey uses every edge exactly once, so all of that vertex's edges are used, and they are used two at a time. Therefore the degree is a multiple of $2$, which is to say even.

The exceptions are the start and the finish. At the start the journey departs without having arrived, leaving one edge unpaired. At the finish it arrives without departing, again leaving one unpaired. Each of those makes the degree odd.

For a circuit the start and finish are the same vertex, and its unpaired departure and unpaired arrival pair up with each other, so even that vertex has even degree.

The Rule, Both Ways

+5 XP to read

The argument above shows what must be true if an Eulerian journey exists. The remarkable part is that the converse also holds.

For a connected graph:

Every vertex even $\iff$ an Eulerian circuit exists.

Exactly two vertices odd $\iff$ an Eulerian trail exists but no circuit, and it runs between the two odd vertices.

Four or more odd $\iff$ neither exists.

The forward direction was proved above; the reverse direction is a genuine theorem and is harder, since it must construct a journey rather than merely analyse one. Euler stated it in 1736 and a full proof of the converse came later.

Both directions matter in practice. The forward direction lets you rule a journey out; the reverse lets you promise one exists before you have found it.

Using It

+5 XP to read

The procedure is three steps and takes under a minute.

Check the graph is connected. Explore from any vertex. If edges remain in another component, stop: no Eulerian journey exists whatever the degrees are.

Find every degree and add them. The total must be $2e$. If it is odd, recount.

Count the odd degrees. Zero gives a circuit, two give a trail, more give neither.

Notice what the procedure never does: it never tries to find a route. The answer comes from counting, not searching, and it is right whether the graph has six edges or six thousand.

A count of one odd vertex would mean an arithmetic error, since Lesson 2 showed the number of odd vertices is always even. Treat it as a signal to recount rather than as a result.

Where It Starts and Finishes

+5 XP to read

The rule says more than whether a journey exists; it says where.

With zero odd vertices, an Eulerian circuit exists and may start at any vertex you like, finishing at the same one. There is complete freedom.

With exactly two odd vertices, an Eulerian trail exists and must start at one of them and finish at the other. There is no freedom at all: starting anywhere else fails.

That second case is often the useful part of the answer. A question asking where a plough must begin its round is answered by finding the odd vertices, not by trying routes.

The reason is the pairing argument. The two odd vertices each have one unpaired edge, and only a start or a finish can leave an edge unpaired, so those two roles are forced onto exactly those two vertices.

Repairing a Graph

+5 XP to read

When a graph has too many odd vertices, the natural next question is what would fix it.

Adding an edge between two odd vertices makes both of them even, reducing the odd count by $2$. So a graph with $2k$ odd vertices needs at least $k - 1$ added edges to bring the count down to $2$, and $k$ added edges to bring it to $0$.

In practice you often cannot add edges, because you cannot build a new road just to make the round tidy. The alternative is to repeat an existing edge, walking one street twice, which has the same effect on the degrees and costs only the extra distance.

That is the route inspection problem: cover every edge with the least possible repetition. The degree rule is what turns it from a search into a calculation, because it identifies exactly which vertices need pairing up.

Choosing which repeats to make, so that the extra distance is smallest, needs edge weights and is beyond this area. Knowing how many repeats are needed does not.

Watch Me Solve It · 3 examples

Watch Me Solve It · Deciding, then finding

+15 XP per step

PROBLEM

A connected graph has vertices $A$ to $E$ with edges $AB$, $BC$, $CD$, $DE$, $EA$, $AC$. Decide whether it has an Eulerian circuit, an Eulerian trail or neither, and produce the journey if one exists.

1

Find the degrees and check the sum

$\deg(A) = 3, \ \deg(B) = 2, \ \deg(C) = 3, \ \deg(D) = 2, \ \deg(E) = 2$

$3 + 2 + 3 + 2 + 2 = 12 = 2 \times 6$

The sum matches twice the edge count, so the degrees are right.
2

Count the odd vertices

Only $A$ and $C$ are odd, which is exactly two. So an Eulerian trail exists, running from $A$ to $C$, and there is no Eulerian circuit.
3

Produce the trail

$A \to B \to C \to D \to E \to A \to C$

Uses $AB$, $BC$, $CD$, $DE$, $EA$, $AC$, which is all six edges once each. It starts at $A$ and finishes at $C$, the two odd vertices, as the rule requires.
4

Confirm the length

Six edges used and seven vertices listed, matching $e = 6$.

AnswerAn Eulerian trail from $A$ to $C$: $A \to B \to C \to D \to E \to A \to C$

Watch Me Solve It · Ruling it out by counting

+15 XP per step

PROBLEM

A connected graph has degrees $3$, $3$, $3$, $3$, $4$, $4$. Determine whether it has an Eulerian trail or circuit, and state how many extra edges would be needed for each.

1

Check the degree sum

$3 + 3 + 3 + 3 + 4 + 4 = 20 = 2 \times 10$

So the graph has $10$ edges and the degree list is consistent.
2

Count the odd vertices

Four vertices have degree $3$, which is odd. Four odd vertices is more than two, so the graph has neither an Eulerian trail nor an Eulerian circuit.
3

Work out the repair for a trail

Adding an edge between two odd vertices makes both even, cutting the odd count by $2$. Going from four odd to two odd needs one added edge.
4

Work out the repair for a circuit

Going from four odd to zero odd needs two added edges, pairing up all four odd vertices. Either repair works, and which is wanted depends on whether the round must return to its start.

AnswerNeither; one extra edge gives a trail, two give a circuit

Watch Me Solve It · Where must the round begin?

+15 XP per step

PROBLEM

A road network has intersections $P$, $Q$, $R$, $S$, $T$ with road sections $PQ$, $PR$, $PS$, $QR$, $QS$, $RT$, $ST$. A sweeper must clear every section once. Decide whether this is possible and, if so, where it must start and finish.

1

Find the degrees

$\deg(P) = 3, \ \deg(Q) = 3, \ \deg(R) = 3, \ \deg(S) = 3, \ \deg(T) = 2$

Check: $3 + 3 + 3 + 3 + 2 = 14 = 2 \times 7$, matching the seven sections.
2

Count the odd vertices

$P$, $Q$, $R$ and $S$ are all odd, giving four. More than two, so no Eulerian trail exists and the round is impossible as stated.
3

Say what would make it possible

Repeating one section joining two odd intersections, say $PQ$, makes both $P$ and $Q$ even, leaving $R$ and $S$ odd. A trail then exists, running from $R$ to $S$.
4

Answer the practical question

The sweeper cannot cover every section exactly once. Repeating one section allows a round starting at $R$ and finishing at $S$, covering eight sections in total to clear seven.

AnswerImpossible as stated; repeating one section allows a round from $R$ to $S$

Brain Trainer · 5 problems

Brain Trainer · Count the odd ones

5 problems

Five items. Assume every graph is connected unless the item says otherwise.

1 All degrees in a connected graph are even. What exists?

Zero odd vertices is the circuit case.An Eulerian circuit
2 A connected graph has exactly two odd vertices, $X$ and $Y$. Where must an Eulerian trail start and finish?

The odd vertices are forced to be the endpoints.At $X$ and $Y$
3 A connected graph has six vertices of odd degree. What exists?

More than two odd vertices rules both out.Neither
4 A student counts three odd vertices. What has gone wrong?

The number of odd vertices is always even.A miscount
5 A graph has all even degrees but is in two pieces, each with edges. Does an Eulerian circuit exist?

The rule requires connectedness.No

Complete in your workbook.

Multiple Choice · 5 questions

MC1

The circuit condition

+10 XP

A connected graph has an Eulerian circuit exactly when:

MC2

Applying the rule

+10 XP

A connected graph has degrees $2$, $2$, $3$, $3$, $4$. It has:

MC3

The forced endpoints

+10 XP

A connected graph has odd vertices only at $M$ and $N$. An Eulerian trail on it:

MC4

The condition that is easy to forget

+10 XP

A graph has every vertex of even degree, but it consists of two separate triangles. It has:

MC5

Repairing a graph

+10 XP

A connected graph has six vertices of odd degree. The least number of extra edges needed to give it an Eulerian circuit is:

Short Answer · 3 questions

Decide and produce

+15 XP

SHORT ANSWER

A connected graph has vertices $A$, $B$, $C$, $D$ and edges $AB$, $AC$, $AD$, $BC$, $BD$, $CD$. Determine whether it has an Eulerian circuit, an Eulerian trail or neither, justifying your answer from the degrees, and produce the journey if one exists.

Write your working in your book.

Justify the endpoints

+15 XP

SHORT ANSWER

A connected graph has exactly two vertices of odd degree, $U$ and $V$. Explain why any Eulerian trail must have $U$ and $V$ as its endpoints, and why the trail cannot be closed.

Write your working in your book.

Plan a round

+15 XP

SHORT ANSWER

A park's paths form a connected network with junctions $A$ to $F$ and paths $AB$, $AC$, $AD$, $BC$, $BE$, $CF$, $DE$, $EF$. A gardener must sweep every path. Determine whether every path can be swept exactly once, state where the round begins and ends if so, and if not, state the smallest number of paths that must be swept twice.

Write your working in your book.

Stretch Challenge · The route inspection problem

+25 XP

CHALLENGE

A postal round must cover every street and return to the depot. When the network has $2k$ odd vertices with $k \geq 1$, some streets must be walked twice. Explain why at least $k$ streets must be repeated, work out the answer for a network with $8$ odd vertices, and explain why knowing $k$ still does not tell a planner which streets to repeat.

Quick Review

recap

Count the odd vertices

For a connected graph: zero gives an Eulerian circuit, exactly two give an Eulerian trail, four or more give neither. One is impossible.

The pairing argument is the reason

A vertex passed through uses its edges two at a time, so its degree is even. Only a start or a finish leaves an edge unpaired, and there are at most two of those.

The odd vertices are the endpoints

With two odd vertices the trail must start at one and finish at the other. With none, a circuit may start anywhere.

Connectedness is a precondition

Even degrees guarantee nothing across two components. Check the graph is in one piece before reading anything from the degrees.

Your Badges

0 of 6

First Steps

3-Day Streak

3 in a Row

Lesson Ace

Stretch Seeker

Daily Warrior

Mark lesson as complete

Tick when you've finished Learn, Practice and the Stretch. Earns +95 XP and +25 coins.

Introduction to Networks (Path) index · Maths subject page