140 Chapter 12
Grasp the big picture. When reading a proof, aim to understand the underlying
idea. There are multiple levels involved with reading and understanding proofs. At
a basic level, one can read a proof by understanding every word in it and verifying
that the steps are all logically correct and that they establish the truth of the theorem.
A deeper understanding of a proof, however, involves a holistic understanding of the
argument, including the ability to summarize the argument, identifying the main ideas
and strategy of the proof. If you have truly grasped a proof, then you can easily state
and prove the theorem again entirely on your own.
Exercises
12.1 Prove that if a finite graph admits an Euler circuit, then for any particular edge of the graph,
there is such an Euler circuit ending with exactly that edge.
12.2 Prove that in any finite graph, the total degree, meaning the sum of the degrees of all the
vertices, is always even. Conclude as a corollary that no finite graph can have an odd number
of odd-degree vertices.
12.3 Prove that in any finite graph with exactly two vertices of odd degree, every Euler path must
start at one of those odd-degree vertices and end at the other.
12.4 Give a direct proof of the converse implication of theorem 99, analogous to that of the proof
of theorem 97. [Hint: Take care to start with the right vertex.]
12.5 Let K
n
be the complete graph on n vertices. This is the graph with n vertices and an edge
between any two distinct vertices. Show for nonzero n that K
n
has an Euler circuit if and only
if n is odd. For which n does K
n
have an Euler path?
12.6 Suppose that in the city of K
¨
onigsberg, the North Prince lives in a castle on the north bank
and the South Prince lives in a castle on the south bank. The university is on the east island,
but the center of the townspeople’s mathematical discussions is, as we mentioned, at the pub
on the center island, with challenges and late-night attempts to “walk the bridges.” Now, the
North Prince has a plan to build a new bridge, an eighth bridge, in such a way that from his
castle he could traverse all eight bridges and end at the pub, for celebration. Where should
he build a bridge that would enable him to do this? Prove that there is essentially only one
location for such a bridge, in terms of its connectivity, and furthermore, if such a bridge were
built, the South Prince would definitely not have the same ability from his own castle.
12.7 After the North Prince builds his bridge, the infuriated South Prince seeks revenge by building
a ninth bridge, which will enable him to traverse all nine bridges exactly once, starting from
his own castle and ending at the pub, while simultaneously preventing the analogous ability
for the North Prince. Where should he build the ninth bridge?
12.8 In order to settle the dispute—and get more customers—the pub keeper decides to build a tenth
bridge, which will enable everyone in town to traverse all the bridges, starting at whichever
location they wish. Where must the innkeeper build his bridge?