we see that there are N terms altogether in the sum (the number of odd nodes) and
that each term is an odd number. For the sum of N odd numbers to be even, N
must be even. (Can you prove this statement?) We have thus proved the following
theorem.
tHeoRem oN oDD NoDes iN A GRAPh
The number of odd nodes in any graph is even.
Now suppose a graph has an odd node n of degree 2k + 1 and that an Euler
path exists in the graph but does not start at n. Then for each arc we use to enter
n, there is another unused arc for leaving n until we have used k pairs of arcs. The
next time we enter n, there is no new arc on which to leave. Thus, if our path does
not begin at n, it must end at n. The path either begins at n or it does not, and in
the latter case it ends at n, so the path either begins or ends at this arbitrary odd
node. Therefore, if there are more than two odd nodes in the graph, there can be
no path. Thus, there are two possible cases where an Euler path may exist—on a
graph with no odd nodes or on one with two odd nodes.
Consider the graph with no odd nodes. Pick any node m and begin an Euler
path. Whenever you enter a different node, you will always have another arc on
which to exit until you get back to m. If you have used up every arc of the graph,
you are done. If not, there is some node m′ of your path with unused arcs. Then
construct an Euler path beginning and ending at m′, much as you did the previous
section of path, using all new arcs. Attach this cycle as a side trip on the original
path. If you have now used up every arc of the graph, you are done. If not, continue
this process until every arc has been covered.
If there are exactly two odd nodes, an Euler path can be started beginning at
one odd node and ending at the other. If the path has not covered all of the arcs,
extra cycles can be patched in as in the previous case.
We now have a complete solution to the Euler path problem.
tHeoRem oN euleR PAths
An Euler path exists in a connected graph if and only if there are either no odd
nodes or two odd nodes. For the case of no odd nodes, the path can begin at any
node and will end there; for the case of two odd nodes, the path must begin at one
odd node and end at the other.
The theorem on Euler paths is actually an algorithm to determine whether
an Euler path exists on an arbitrary connected graph. To make it look more like
an algorithm, we’ll rewrite it in pseudocode, but first we’ll make a simplifying
Section 7.2 Euler Path and Hamiltonian Circuit
573
praCtiCe 8 Using the preceding theorem, work Practice 7 again.
praCtiCe 9 Is the Königsberg walk possible?
■
■
that each term is an odd number. For the sum of N odd numbers to be even, N
must be even. (Can you prove this statement?) We have thus proved the following
theorem.
tHeoRem oN oDD NoDes iN A GRAPh
The number of odd nodes in any graph is even.
Now suppose a graph has an odd node n of degree 2k + 1 and that an Euler
path exists in the graph but does not start at n. Then for each arc we use to enter
n, there is another unused arc for leaving n until we have used k pairs of arcs. The
next time we enter n, there is no new arc on which to leave. Thus, if our path does
not begin at n, it must end at n. The path either begins at n or it does not, and in
the latter case it ends at n, so the path either begins or ends at this arbitrary odd
node. Therefore, if there are more than two odd nodes in the graph, there can be
no path. Thus, there are two possible cases where an Euler path may exist—on a
graph with no odd nodes or on one with two odd nodes.
Consider the graph with no odd nodes. Pick any node m and begin an Euler
path. Whenever you enter a different node, you will always have another arc on
which to exit until you get back to m. If you have used up every arc of the graph,
you are done. If not, there is some node m′ of your path with unused arcs. Then
construct an Euler path beginning and ending at m′, much as you did the previous
section of path, using all new arcs. Attach this cycle as a side trip on the original
path. If you have now used up every arc of the graph, you are done. If not, continue
this process until every arc has been covered.
If there are exactly two odd nodes, an Euler path can be started beginning at
one odd node and ending at the other. If the path has not covered all of the arcs,
extra cycles can be patched in as in the previous case.
We now have a complete solution to the Euler path problem.
tHeoRem oN euleR PAths
An Euler path exists in a connected graph if and only if there are either no odd
nodes or two odd nodes. For the case of no odd nodes, the path can begin at any
node and will end there; for the case of two odd nodes, the path must begin at one
odd node and end at the other.
The theorem on Euler paths is actually an algorithm to determine whether
an Euler path exists on an arbitrary connected graph. To make it look more like
an algorithm, we’ll rewrite it in pseudocode, but first we’ll make a simplifying
Section 7.2 Euler Path and Hamiltonian Circuit
573
praCtiCe 8 Using the preceding theorem, work Practice 7 again.
praCtiCe 9 Is the Königsberg walk possible?
■
■