\documentclass[11pt]{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage{amsfonts}
\usepackage{epsfig}
\setkeys{Gin}{keepaspectratio}
\setlength{\topmargin}{-.55in} \setlength{\oddsidemargin}{0in} \setlength{\evensidemargin}{0in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9.1in}
\newcommand{\br}{\mathbf {R}}
\newcommand{\bq}{\mathbf {Q}}
\newcommand{\bz}{\mathbf {Z}}
\newcommand{\bn}{\mathbf {N}}
\newcommand{\z}{$\circ$}
\newcommand{\lph}{$\leftharpoondown$}
\begin{document}
\title{Early Writings on Graph Theory:\\Euler Circuits and The K\"onigsberg
Bridge Problem}
\author{Janet Heine Barnett\footnote{Department of Mathematics and Physics;
Colorado State University - Pueblo; Pueblo, CO 81001 - 4901; {\tt janet.barnett@colostate-pueblo.edu}.}}
\date{}
\maketitle
\bigskip
\begin{figure}[htb]
\centerline{\epsfig{figure=euler1.eps,height=2.2in}}
\end{figure}
\bigskip
In a 1670 letter to Christian Huygens (1629 - 1695), the celebrated philosopher and mathematician Gottfried W.
Leibniz (1646 - 1716) wrote as follows:
\begin{quote}
\textsf{I am not content with algebra, in that it yields neither the shortest proofs nor the most beautiful
constructions of geometry. Consequently, in view of this, I consider that we need yet another kind of analysis,
geometric or linear, which deals directly with position, as algebra deals with magnitude. \cite[p. 30]{JBBiggs}}
\end{quote}
\noindent Known today as the field of `topology,' Leibniz's `geometry of position' was slow to develop as a
mathematical field. As C.\ F.\ Gauss (1777 - 1855) noted in 1833,
\begin{quote}
\textsf{Of the geometry of position, which Leibniz initiated and to which only two geometers, Euler and
Vandermonde, have given a feeble glance, we know and possess, after a century and a half, very little more than
nothing. \cite[p. 30]{JBBiggs}}
\end{quote}
\noindent The `feeble glance' which Leonhard Euler (1707 - 1783) directed towards the geometry of position
consists of a single paper now considered to be the starting point of modern graph theory. Within the history of
mathematics, the eighteenth century itself is commonly known as `The Age of Euler' in recognition of the
tremendous contributions that Euler made to mathematics during this period. Born in Basel, Switzerland, Euler
studied mathematics under Johann Bernoulli (1667 - 1748), then one of the leading European mathematicians of the
time and among the first --- along with his brother Jakob Bernoulli (1654 - 1705) --- to apply the new
calculus techniques developed by Leibniz in the late seventeenth century to the study of curves. Euler soon
surpassed his early teacher, and made important contributions to an astounding variety of subjects, ranging from
number theory and analysis to astronomy and optics to mapmaking, in addition to graph theory and topology. His
work was particularly important in re-defining calculus as the study of analytic functions, in contrast to the
seventeenth century view of calculus as the study of curves. Amazingly, nearly half of Euler's nearly 900
books, papers and other works were written after he became almost totally blind in 1771.
The paper we examine in this project appeared in \emph{Commentarii Academiae Scientiarum Imperialis
Petropolitanae} in 1736. In it, Euler undertakes a mathematical formulation of the now-famous K\"onigsberg
Bridge Problem: is it possible to plan a stroll through the town of K\"onigsberg which crosses each of the
town's seven bridges once and only once? Like other early graph theory work, the K\"onigsberg Bridge Problem
has the appearance of being little more than an interesting puzzle. Yet from such deceptively frivolous origins,
graph theory has grown into a powerful and deep mathematical theory with applications in the physical,
biological, and social sciences. The resolution of the Four Color Problem --- one of graph theory's most famous
historical problems --- even raised new questions about the notion of mathematical proof itself. First
formulated by Augustus De Morgan in a 1852 letter to Hamilton, the Four Color Problem asks whether four colors
are sufficient to color every planar map in such a way that regions sharing a boundary are colored in different
colors. In 1976, after a long history of failed attempts to prove this is the case, Kenneth Appel (1932 - ) and
Wolfgang Haken (1928 - ) published a computer-assisted proof which many mathematicians were unwilling to accept
as valid. At the heart of the issue is a question that could be asked of any computer-assisted proof: should an
argument that can not be directly checked by any member of the mathematical community be considered a valid
proof?
This modern controversy highlights the historical fact that standards of proof have always varied from century
to century, and from culture to culture. This project will highlight one part of this historical story by
examining the differences in precision between an eighteenth century proof and a modern treatment of the same
result. In particular, we wish to contrast Euler's approach to the problem of finding necessary and sufficient
conditions for the existence of what is now known as an `Euler circuit' to a modern proof of the main result of
the paper.
In what follows, we take our translation from \cite[pp. 3 - 8]{JBBiggs}, with some portions eliminated in order to
focus only on those most relevant to Euler's reformulation of the `bridge crossing problem' as a purely
mathematical problem. Definitions of modern terminology are introduced as we proceed through Euler's paper;
modern proofs of two lemmas used in the proof of the main result are also included in an appendix.
%Begin Euler citation.
\bigskip
\begin{quote}
\centerline{\textsf{SOLUTIO PROBLEMATIS AD GEOMETRIAM SITUS PERTINENTIS}}
\textsf{
\begin{description}
\item[1\hspace{11pt}] In addition to that branch of geometry which is concerned
with magnitudes, and which has always received the greatest
attention, there is another branch, previously almost unknown,
which Leibniz first mentioned, calling it the \emph{geometry of
position}. This branch is concerned only with the determination
of position and its properties; it does not involve measurements,
nor calculations made with them. It has not yet been
satisfactorily determined what kind of problems are relevant to
this geometry of position, or what methods should be used in
solving them. Hence, when a problem was recently mentioned, which
seemed geometrical but was so constructed that it did not require
the measurement of distances, nor did calculation help at all, I
had no doubt that it was concerned with the geometry of position ---
especially as its solution involved only position, and no
calculation was of any use. I have therefore decided to give here
the method which I have found for solving this kind of problem, as
an example of the geometry of position.
\vspace{5pt}
\item[2\hspace{11pt}] The problem, which I am told is widely known, is as follows:
in K\"onigsberg in Prussia, there is an island \emph{A}, called \emph{the
Kneiphof}; the river which surrounds it is divided into two
branches, as can be seen in Fig. [1.2], and these branches are
crossed by seven bridges, \emph{a, b , c , d , e , f} and
\emph{g}. Concerning these bridges, it was asked whether anyone
could arrange a route in such a way that he would cross each
bridge once and only once. I was told that some people asserted
that this was impossible, while others were in doubt: but nobody
would actually assert that it could be done. From this, I have
formulated the general problem: whatever be the arrangement and
division of the river into branches, and however many bridges
there be, can one find out whether or not it is possible to cross
each bridge exactly once?
\end{description}}
\end{quote}
\begin{figure}[h]
\centerline{\epsfig{figure=euler2.eps,height=1.4in}}
\end{figure}
% Project questions
Notice that Euler begins his analysis of the `bridge crossing' problem by first replacing the map of
the city by a simpler diagram showing only the main feature. In modern graph theory, we simplify this diagram
even further to include only points (representing land masses) and line segments (representing bridges). These
points and line segments are referred to as \emph{vertices} (singular: vertex) and \emph{edges} respectively.
The collection of vertices and edges together with the relationships between them
is called a \emph{graph}. More precisely, a graph consists of a set of vertices and a set of edges, where each edge may be viewed as an
ordered pair of two (usually distinct) vertices. In the case where an edge connects a vertex to itself, we refer
to that edge as a \emph{loop}.
% Project questions
\begin{enumerate}
\item[1.] Sketch the diagram of a graph with 5 vertices and 8
edges to represent the bridge crossing problem illustrated in the following figure.
\end{enumerate}
\vspace*{-.5in}
\begin{figure}
\centerline{\epsfig{file=bridges.eps,width=3.3in}}
\end{figure}
\newpage
Returning now to Euler's original paper, paragraphs 3 -- 5 provide additional simplifications of the bridge
crossing problem.
\textsf{
\begin{quote}
\begin{description}
\item[3\hspace{11pt}]As far as the problem of the seven bridges of K\"onigsberg is concerned, it can be solved by making an exhaustive
list of all possible routes, and then finding whether or not any route satisfies the conditions of the problem.
Because of the number of possibilities, this method of solution would be too difficult and laborious, and in
other problems with more bridges it would be impossible. Moreover, if this method is followed to its conclusion,
many irrelevant routes will be found, which is the reason for the difficulty of this method. Hence I rejected
it, and looked for another method concerned only with the problem of whether or not the specified route could be
found; I considered that such a method would be much simpler.
\vspace{5pt}
\item[4\hspace{11pt}] My whole method relies on the particularly convenient way in
which the crossing of a bridge can be represented. For this I use
the capital letters \emph{A, B, C, D,} for each of the land areas
separated by the river. If a traveller goes from \emph{A} to
\emph{B} over bridge \emph{a} or \emph{b}, I write this as
\emph{AB} --- where the first letter refers to the area the
traveller is leaving, and the second refers to the area he
arrives at after crossing the bridge. Thus, if the traveller
leaves \emph{B} and crosses into \emph{D} over bridge \emph{f}, this crossing is
represented by \emph{BD}, and the two crossing \emph{AB} and \emph{BD} combined I shall
denote by the three letters \emph{ABD}, where the middle letter \emph{B}
refers to both the area which is entered in the first crossing
and to the one which is left in the second crossing.
\vspace{5pt}
\item[5\hspace{11pt}] Similarly, if the traveller goes on from D to C over the bridge g,
I shall represent these three successive crossings by the four letters ABDC,
which should be taken to mean that the traveller, starting in A, crosses to B,
goes on to D, and finally arrives in C. Since each land area is separated from
every other by a branch of the river, the traveller must have crossed three bridges.
Similarly, the successive crossing of four bridges would be represented by five letters,
and in general, however many bridges the traveller crosses, his
journey
is denoted by a number of letters one greater than the number of bridges.
Thus the crossing of seven bridges requires eight letters to represent it.
\end{description}
\end{quote}}
\vspace{10pt}
% Project questions
After rejecting the impractical strategy of solving the bridge-crossing problem by making an exhaustive list of
all possible routes, Euler again reformulates the problem in terms of sequences of letters (vertices)
representing land masses, thereby making the diagram itself unnecessary to the solution of the problem. Today,
we say that two vertices joined by an edge in the graph are \emph{adjacent}, and refer to a sequence of adjacent
vertices as a \emph{walk}. Technically, a walk is a sequence of alternating (adjacent) vertices and edges
$v_0e_1v_1e_1\ldots e_n v_n$ in which both the order of the vertices and the order of the edges used between
adjacent vertices are specified. In the case where no edge of the graph is repeated (as required in a
bridge-crossing route), the walk is known as a \emph{path}. If the initial and terminal vertex are equal, the
path is said to be a \emph{circuit}. If \emph{every} edge of the graph is used \emph{exactly once} (as desired
in a bridge-crossing route), the path (circuit) is said to be a \emph{Euler path (circuit)}.
%Project questions
\bigskip
\begin{enumerate}
\item[2.] For the bridge problem shown in Project Question 1 above,
how many capital letters (representing graph vertices) will be needed to represent an Euler path?
\end{enumerate}
\bigskip
Having reformulated the bridge crossing problem in terms of sequences of letters (vertices) alone, Euler now
turns to the question of determining \emph{whether} a given bridge crossing problem admits of a solution. As
you read through Euler's development of a procedure
for deciding this question in paragraphs 7 - 13 below, pay
attention to the style of argument employed, and how this differs
from that used in a modern textbook.
\bigskip
\textsf{
\begin{quote}
\begin{description}
\item[7\hspace{11pt}]The problem is therefore reduced to finding a sequence of
eight letters, formed from the four letters \emph{A},
\emph{B}, \emph{C} and \emph{D}, in which the various pairs of
letters occur the required number of times. Before I turn to the
problem of finding such a sequence, it would be useful to find out
whether or not it is even possible to arrange the letters in this
way, for if it were possible to show that there is no such
arrangement, then any work directed toward finding it would be
wasted. I have therefore tried to find a rule which will be
useful in this case, and in others, for determining whether or not
such an arrangement can exist.%
\\
\end{description}
\end{quote}}
%\vspace{2in}
\begin{figure}[htb]
\centerline{\epsfig{figure=euler3.eps}}
\end{figure}
\textsf{
\begin{quote}
\begin{description}
%
\item[8\hspace{11pt}]In order to try to find such a rule, I
consider a single area A, into which there lead any number of bridges a, b, c, d, etc.\ (Fig.\ [1.3]). Let us
take first the single bridge a which leads into A: if a traveller crosses this bridge, he must either have been
in A before crossing, or have come into A after crossing, so that in either case the letter A will occur once in
the representation described above. If three bridges (a, b and c, say) lead to A, and if the traveller crosses
all three, then in the representation of his journey the letter A will occur twice, whether he starts his
journey from A or not. Similarly, if five bridges lead to A, the representation of a journey across all of them
would have three occurrences of the letter A. And in general, if the number of bridges is any odd number, and if
it is increased by one, then the number of occurrences of A is half of the result.
\end{description}
\end{quote}}
% Project questions
\bigskip
\begin{enumerate}
\item[3.] In paragraph 8, Euler deduces a rule for
determining how many times a vertex must appear in the representation of the route for a given bridge problem
for the case where an odd number of bridges leads to the land mass represented by that vertex. \textbf{Before
reading further}, use this rule to determine how many times each of the vertices A , B , C and D would appear in
the representation of a route for the K\"onigsberg Bridge Problem. Given Euler's earlier conclusion (paragraph
5) that a solution to this problem requires a sequence of 8 vertices, is such a sequence possible? Explain.
\end{enumerate}
\bigskip
%Continue with Euler's paper
\bigskip
\textsf{
\begin{quote}
\begin{description}
\item[9\hspace{10pt}]In the case of the K\"onigsberg bridges, therefore, there must be
three occurrences of the letter A in the representation of the route, since five bridges (a, b, c, d, e) lead to
the area A. Next, since three bridges lead to B, the letter B must occur twice; similarly, D must occur twice,
and C also. So in a series of eight letters, representing the crossing of seven bridges, the letter A must occur
three times, and the letters B, C and D twice each - but this cannot happen in a sequence of eight letters. It
follows that such a journey cannot be undertaken across the seven bridges of K\"onigsberg.
%
\vspace{5pt}
%
\item[10\hspace{11pt}]It is similarly possible to tell whether a journey can
be made crossing each bridge once, for any arrangement of bridges, whenever the number of bridges leading to
each area is odd. For if the sum of the number of times each letter must occur is one more than the number of
bridges, then the journey can be made; if, however, as happened in our example, the number of occurrences is
greater than one more than the number of bridges, then such a journey can never be accomplished. The rule which
I gave for finding the number of occurrences of the letter A from the number of bridges leading to the area A
holds equally whether all of the bridges come from another area B, as shown in Fig.\ [1.3], or whether they come
from different areas, since I was considering the area A alone, and trying to find out how many times the letter
A must occur.
%
\vspace{5pt}
%
\item[11\hspace{10pt}]If,
however, the number of bridges leading to A is even, then in describing the journey one must consider whether or
not the traveller starts his journey from A; for if two bridges lead to A, and the traveller starts from A, then
the letter A must occur twice, once to represent his leaving A by one bridge, and once to represent his
returning to A by the other. If, however, the traveller starts his journey from another area, then the letter A
will only occur once; for this one occurrence will represent both his arrival in A and his departure from there,
according to my method of representation.
\vspace{5pt}
\item[12\hspace{10pt}]If there are four bridges leading to
A, and if the traveller starts from A, then in the representation of the whole journey, the letter A must occur
three times if he is to cross each bridge once; if he begins his walk in another area, then the letter A will
occur twice. If there are six bridges leading to A, then the letter A will occur four times if the journey
starts from A, and if the traveller does not start by leaving A, then it must occur three times. So, in general,
if the number of bridges is even, then the number of occurrences of A will be half of this number if the journey
is not started from A, and the number of occurrences will be one greater than half the number of bridges if the
journey does start at A.
\vspace{5pt}
\item[13\hspace{10pt}]Since one can start from only one area in any
journey, I shall define, corresponding to the number of bridges leading to each area, the number of occurrences
of the letter denoting that area to be half the number of bridges plus one, if the number of bridges is odd, and
if the number of bridges is even, to be half of it. Then, if the total of all the occurrences is equal to the
number of bridges plus one, the required journey will be possible, and will have to start from an area with an
odd number of bridges leading to it. If, however, the total number of letters is one less than the number of
bridges plus one, then the journey is possible starting from an area with an even number of bridges leading to
it, since the number of letters will therefore be increased by one.
\end{description}
\end{quote}}
\bigskip
Notice that Euler's definition concerning `the number of occurrences of the letter denoting that area' depends
on whether the the number of bridges (edges) leading to each area (vertex) is even or odd. In contemporary
terminology, the number of edges incident on a vertex $v$ is referred to as the \emph{degree of vertex $v$}.
%Project Questions
\bigskip
\begin{enumerate}
\item[4.] Let $deg(v)$ denote the degree of vertex $v$ in a graph $G$.
Euler's definition of `the number of occurrences of $v$' can then be re-stated as follows:
\begin{itemize}
\item If $deg(v)$ is even, then $v$ occurs $\frac{1}{2}deg(v)$ times.
\item If $deg(v)$ is odd, then $v$ occurs $\frac{1}{2}\left[deg(v)+1\right]$ times.
\end{itemize}
Based on Euler's discussion in paragraphs 9 - 12, how convinced are you that this definition gives a correct
description of the K\"onigsberg Bridge Problem? How convincing do you find Euler's claim (in paragraph 13) that
the required route can be found in the case where `the total of all the occurrences is equal to the number of
bridges plus one'? Comment on how a proof of this claim in a modern textbook might differ from the argument
which Euler presents for it in paragraphs 9 - 12.
\end{enumerate}
%Back to Euler
\textsf{
\begin{quote}
\begin{description}
\item[14\hspace{10pt}]So, whatever arrangement of water and bridges is
given, the following method will determine whether or not it is possible to cross each of the bridges: I first
denote by the letters A, B, C, etc.\ the various areas which are separated from one another by the water. I then
take the total number of bridges, add one, and write the result above the working which follows. Thirdly, I
write the letters A, B, C, etc.\ in a column, and write next to each one the number of bridges leading to it.
Fourthly, I indicate with an asterisk those letters which have an even number next to them. Fifthly, next to
each even one I write half the number, and next to each odd one I write half the number increased by one.
Sixthly, I add together these last numbers, and if this sum is one less than, or equal to, the number written
above, which is the number of bridges plus one, I conclude that the required journey is possible. It must be
remembered that if the sum is one less than the number written above, then the journey must begin from one of
the areas marked with an asterisk, and it must begin from an unmarked one if the sum is equal. Thus in the
K\"onigsberg problem, I set out the
working as follows:\\
\\
\centerline{Number of bridges 7, which gives 8}
$$\begin{tabular}{cc|c}
% after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
& \emph{Bridges} & \\
A, & 5 & 3 \\
B, & 3 & 2 \\
C, & 3 & 2 \\
D, & 3 & 2 \\
\end{tabular}$$
Since this gives more than 8, such a journey can never be made.
%
\vspace{5pt}%
%
\begin{figure}[htb]
\centerline{\epsfig{figure=euler4.eps, height=1.5in}}
\end{figure}
%
%
\newpage
\vspace{5pt}
\item[15\hspace{10pt}] Suppose that there are two islands A and B surrounded by water which leads to
four rivers as shown in Fig.\ [1.4]. Fifteen bridges (a, b, c, d, etc.) cross the rivers and the water
surrounding the islands, and it is required to determine whether one can arrange a journey which crosses each
bridge exactly once. First, therefore, I name all the areas separated by water as A, B, C, D, E, F, so that
there are six of them. Next, I increase the number of bridges (15) by one, and write the result (16) above the
working which follows.
\\
\\
$$\begin{tabular}{cc|c}
\\
& & 16\\
\hline
A*, & 8 & 4 \\
B*, & 4 & 2 \\
C*, & 4 & 2 \\
D, & 3 & 2 \\
E, & 5 & 3 \\
F*, & 6 & 3 \\
\hline
& & 16
\end{tabular}$$
Thirdly, I write the letters A, B, C, etc.\ in a column, and write next to each one the number of bridges which
lead to the corresponding area, so that eight bridges lead to A, four to B, and so on. Fourthly, I indicate with
an asterisk those letters which have an even number next to them. Fifthly, I write in the third column half the
even numbers in the second column, and then I add one to the odd numbers and write down half the result in each
case. Sixthly, I add up all the numbers in the third column in turn, and I get the sum 16; since this is equal
to the number (16) written above, it follows that the required journey can be made if it starts from area D or
E, since these are not marked with an asterisk. The journey can be done as follows:
\\
\\
\centerline{E\,a\,F\,b\,B\,c\,F\,d\,A\,e\,F\,f\,C\,g\,A\,h\,C\,i\,D\,k\,A\,m\,E\,n\,A\,p\,B\,o\,E\,l\,D,}
\\
\\
where I have written the bridges which are crossed between the
corresponding capital letters.
\end{description}
\end{quote}}
%Project Questions
\bigskip
\begin{enumerate}
\item[5.] Apply Euler's procedure to
determine whether the graph representing the `bridge-crossing' problem in Project Question 1 above contains an
Euler path. If so, find one.
\end{enumerate}
\vspace{10pt}
In paragraphs 16 and 17, Euler makes some observations
intended to simplify the procedure for determining whether a
given bridge-crossing problem has a solution. As you read these paragraphs, consider how to reformulate these
observations in terms of degree.
\bigskip
%Back to Euler
\textsf{
\begin{quote}
\begin{description}
\item[16\hspace{10pt}]In this way it will be easy, even in the most complicated cases, to
determine whether or not a journey can be made crossing each bridge once and once only. I shall, however,
describe a much simpler method for determining this which is not difficult to derive from the present method,
after I have first made a few preliminary observations. First, I observe that the numbers of bridges written
next to the letters A, B, C, etc.\ together add up to twice the total number of bridges. The reason for this is
that, in the calculation where every bridge leading to a given area is counted, each bridge is counted twice,
once for each of the two areas which it joins.
%
\vspace{5pt}
%
\item[17\hspace{10pt}]It follows that the total of the numbers of bridges
leading to each area must be an even number, since half of it is equal to the number
of bridges. This is impossible if only one of these numbers is odd, or if three are odd, or five, and so on.
Hence if some of the numbers of bridges attached to the letters A, B, C, etc.\ are odd, then there must be an
even number of these. Thus, in the K\"onigsberg problem, there were odd numbers attached to the letters A, B, C
and D, as can be seen from Paragraph 14, and in the last example (in Paragraph 15), only two numbers were odd,
namely those attached to D and E.
\end{description}
\end{quote}}
%Project Questions
\bigskip
\begin{enumerate}
\item[6.] The result described in Paragraph
16 is sometimes referred to as `The Handshake Theorem,' based on the equivalent problem of counting the number
of handshakes that occur during a social gathering at which every person present shakes hands with every other
person present exactly once. A modern statement of the Handshake Theorem would be: \emph{The sum of the degree
of all vertices in a finite graph equals twice the number of edges in the graph.} Locate this theorem in a
modern textbook, and comment on how the proof given there compares to Euler's discussion in paragraph 16.
\vspace{5pt}
\item[7.] The result described in Paragraph
17 can be re-stated as follows: \emph{Every finite graph contains an even number of vertices with odd degree.}
Locate this theorem in a modern textbook, and comment on how the proof given there compares to Euler's
discussion in paragraph 17.
\end{enumerate}
\vspace{10pt}
Euler now uses the above observations to develop
simplified rules for determining whether a given bridge-crossing problem has a solution. Again, consider how
you might reformulate this argument in modern graph theoretic terms; we will consider a modern proof of the main
results below.
\bigskip
%Back to Euler
\textsf{
\begin{quote}
\begin{description}
\item[18\hspace{9pt}]Since the total of the numbers attached to the letters A, B, C,
etc.\ is equal to twice the number of bridges, it is clear that if this sum is increased by 2 and then divided
by 2, then it will give the number which is written above the working. If, therefore, all of the numbers
attached to the letters A, B, C, D, etc.\ are even, and half of each of them is taken to obtain the numbers in
the third column, then the sum of these numbers will be one less than the number written above. Whatever area
marks the beginning of the journey, it will have an even number of bridges leading to it, as required. This will
happen in the K\"onigsberg problem if the traveller crosses each bridge twice, since each bridge can be treated
as if it were split in two, and the number of bridges leading into each area will therefore be even.
%
\vspace{5pt}
%
\item[19\hspace{9pt}]Furthermore, if only
two of the numbers attached to the letters A, B, C, etc.\ are odd, and the rest are even, then the journey
specified will always be possible if the journey starts from an area with an odd number of bridges leading to
it. For, if the even numbers are halved, and the odd ones are increased by one, as required, the sum of their
halves will be one greater than the number of bridges, and hence equal to the number written above. It can
further be seen from this that if four, or six, or eight. . . odd numbers appear in the second column, then the
sum of the numbers in the third column will be greater by one, two, three. . . than the number written above,
and the journey will be impossible.
%
\vspace{5pt}
%
\item[20\hspace{10pt}]So whatever arrangement may be proposed, one can easily
determine whether or not a journey can be made, crossing each bridge once, by the following rules:
\begin{description}
\item[\hspace{20pt}]\emph{\hspace{10pt} If there are more than two areas to which an odd number
of bridges lead, then such a journey is impossible.}
\item[\hspace{20pt}]\emph{\hspace{10pt} If, however, the number of bridges is odd for exactly two
areas, then the journey is possible if it starts in either of these
areas.}
\item[\hspace{20pt}] \emph{\hspace{10pt} If, finally, there are no areas to which an odd number of bridges leads, then the
required journey can be accomplished starting from any area.}
\end{description}
With these rules, the given problem can always be solved.
%
\vspace{5pt}
%
\item[21\hspace{10pt}]When it has
been determined that such a journey can be made, one still has to find how it should be arranged. For this I use
the following rule: let those pairs of bridges which lead from one area to another be mentally removed, thereby
considerably reducing the number of bridges; it is then an easy task to construct the required route across the
remaining bridges, and the bridges which have been removed will not significantly alter the route found, as will
become clear after a little thought. I do not therefore think it worthwhile to give any further details
concerning the finding of the routes.
\end{description}
\end{quote}}
\bigskip
%Project Questions
A complete modern statement of Euler's main result requires one final definition: a graph is said to be
\emph{connected} if for every pair of vertices $u,v$ in the graph, there is a walk from $u$ to $v$. Notice that
a graph which is not connected will consist of several components, or subgraphs, each of which is connected.
With this definition in hand, the main results of Euler's paper can be stated as follow:
\vspace{5pt}
\begin{quote}
\textbf{Theorem}: A finite graph $G$ contains an Euler circuit if and only if $G$ is connected and contains no
vertices of odd degree.
\vspace{5pt}
\textbf{Corollary}: A finite graph $G$ contains an Euler path if and only if $G$ is connected and contains at
most two
vertices of odd degree.
\end{quote}
\vspace{5pt}
\begin{enumerate}
\item[8.] Illustrate why the modern statement specifies
that $G$ is connected by giving an example of a disconnected graph which has vertices of even degree only and
contains no Euler circuit. Explain how you know that your example contains no Euler circuit.
\vspace{5pt}
\item[9.] Comment on Euler's proof of this theorem and corollary
as they appear in paragraphs 16 - 19. How convincing do you find his proof? Where and how does he make use of
the assumption that the graph is connected in his proof?
\vspace{5pt}
\item[10.] Below is the sketch of a modern proof of the `if' direction of
the main theorem. The first published proof of this direction is due to the German mathematician Carl
Hierholzer (1840 - 1871); following Hierholzer's premature death, this proof was prepared for publication by a
colleague and appeared in 1873 [\cite{JBHierholzer}]. \textbf{Complete the proof sketch below} by filling in the
missing details. \emph{(Specific questions that you will need to address in your completed proof are indicated
in italics.)}
\vspace{10pt}
Note: You may make use of the lemmas that are provided (with proofs) in the appendix of this project to do so.
\vspace{10pt}
CLAIM:
If $G$ is connected and has no vertices of odd degree, then $G$ contains an Euler circuit.
\vspace{5pt}
PROOF:
Suppose $G$ is connected and has no vertices of odd degree.
We show that $G$ contains an Euler circuit as follows:
\textbf{CASE I} Consider the case where every edge in $G$ is a loop.
\vspace*{-5pt}
\begin{itemize}
\item Since every edge in $G$ is a loop, $G$ must contain only one vertex.
\emph{How do we know a connected graph in which every edge in $G$ is a loop contains only one vertex?}
\item Since every edge in $G$ is a loop on the single vertex $v$,
the graph $G$ must contain an Euler circuit.
\emph{What will an Euler circuit in a connected graph on the single
vertex $v$ look like as a sequence of alternating vertices and edges?}
\end{itemize}
\textbf{CASE II} Consider the case where at least one edge in $G$ is not a loop.
\vspace*{-5pt}
\begin{itemize}
\item Choose any vertex $v$ in $G$ that is incident on at least one edge
that is not a loop.
\item Let $\{vu\}$ and $\{vw\}$ be two distinct edges on which $v$ is incident which are not loops, where the vertices
$u$ and $w$ may be
equal.
\emph{How do we know two such edges exist?}
\item Let $W$ be a \texttt{simple path} (i.e., a path with no repeated edges and no repeated vertices) from $v$ to $w$ that does not use
the edge $\{vw\}$.
\begin{itemize}
\item \emph{How do we know there is a walk from $v$ to $w$ that does not use this edge?}
\emph{(You may wish to consider what happens in the case where every walk from $v$ to $w$ uses the edge
$\{vw\}$; what happens to the graph when the edge $\{vw\}$ is removed? The graph property discussed above in
Project Question 7 of this project may be useful here.)}
\item \emph{Why can we assume that this walk is, in fact, a simple
path?}
\end{itemize}
\item Use $W$ to obtain a circuit $C$ starting and ending at $v$.
\emph{How is this done?}
\item Consider the two cases:
\begin{itemize}
\item $C$ uses every edge of $G$.
\emph{Why are we now done?}
\item $C$ does not use every edge in $G$.
\begin{itemize}
\item Consider the graph $G'$ obtained by removing the
edges of $C$ from the graph $G$ along with any vertices that
become isolated when these edges are removed. Note that $G'$ consists of finitely many connected components and that each
of these connected components has vertices of even degree only.
\emph{How do we that each connected component of $G'$ has only vertices of even
degree?}
\item Select a vertex $v'$ in $G'$ which appears in $C$.
\emph{How do we know that such a vertex exists?}
\item Apply the process outlined above (beginning with CASE I) to the connected component of $G'$ that contains $v'$
in order to obtain a circuit $C'$ in $G'$ with no repeated edges, and combine $C$ with $C'$ to obtain a new
circuit $C_1$ in $G$ that does not repeat any edges.
\begin{itemize}
\item \emph{How do we know that we can apply this process to the connected component in question? }
\item \emph{How do we combine the circuits $C$ and $C'$ from our construction
into a single circuit? How do we know that the combined walk $C_1$ is a circuit?
How do we know that the combined circuit $C_1$ does not contain any repeated edges? }
\end{itemize}
\item Repeat this process as required until a circuit is
obtained that includes every edge of $G$.
\emph{How do we know this process will eventually terminate?}
\end{itemize}
\end{itemize}
\end{itemize}
\item[11] Now write a careful (modern)
proof of the `only if' direction. Begin by assuming that $G$ is a connected graph which contains an Euler
circuit. Then prove that $G$ has no vertices of odd degree.
\item[12] Finally, give a careful (modern)
proof of the corollary.
\end{enumerate}
\section*{Notes to the Instructor}
The project is suitable for a beginning-level discrete mathematics course, or for a `transition to proof'
course. It could be assigned independently or in conjunction with one or both of the projects ``Early Writings
on Graph Theory: Hamiltonian Circuits and The Icosian Game'' and ``Early Writings on Graph Theory:Topological
Connections'' which also appear in this volume. By introducing modern graph theory terminology alongside
Euler's original writing, the project assumes no prior background in graph theory. Thus, the project can be
assigned prior to, concurrently with, or immediately following the introduction of basic graph theory concepts.
The first part of the project in which students are required to read and understand Euler's analysis of the
`bridge problem' is well suited for small group discussion. Project Questions 6 and 7 ask students to compare
Euler's treatment of key results to the treatment of these same results in a modern textbook, with the objective
of drawing students' attention to current standards regarding formal proof. The instructor may wish to provide
access to several different modern textbooks for students to reference on these questions. The project
culminates with exercises
which require students to `fill in the gaps' in a modern proof of Euler's main theorem (Project Questions 10 - 12). These
questions are ideally suited for individual practice in proof writing, but could also be completed in small groups.
\vspace{15pt}
\begin{thebibliography}{99}
\bibitem{JBBiggs} Biggs, N., Lloyd, E., Wilson, R.,
\emph{Graph Theory: 1736--1936}, Clarendon Press, Oxford, 1976.
\bibitem{JBEuler1758} Euler, L., ''Solutio Problematis ad Geometriam Situs Pertinentis,'' {\em Novi Commentarii Academiae Scientarium Imperialis Petropolitanque} {\bf{7}} (1758--59), p. 9--28.
\bibitem{JBHierholzer} Hierholzer, C. , ``\"{U}ber die M\"{o}glichkeit,
einen Linienzug ohne Wiederholung und ohne Unterbrechnung zu umfahren,'' {\em Math. Ann.} {\bf 6} (1873),
30--32.
\bibitem{JBJames} James, I., {\em Remarkable Mathematicians: From Euler
to von Neumann}, Cambridge University Press, Cambridge, 2002.
\bibitem{JBKatz} Katz, V., {\em A History of Mathematics: An
Introduction}, Second Edition, Addison-Wesley, New York, 1998.
\end{thebibliography}
\newpage
\centerline{{\bf APPENDIX: Lemmas Used in Proving Euler's Theorem}}
\vspace{40pt}
\noindent \textbf{LEMMA I}
\vspace{5pt}
\noindent \emph{For every graph $G$, if $W$ is a walk in $G$ that has repeated edges, then $W$ has repeated
vertices.}
\vspace{15pt}
\noindent \textbf{PROOF}
Let $G$ be a graph and $W$ a walk in $G$ that has a
repeated edge $e$. Let $v$ and $w$ be the endpoint vertices of $e$.
\noindent If $e$ is a loop, note that $v=w$, and $v$ is a repeated vertex of $W$ since the sequence `$vev$'
must appear somewhere in $W$.
\noindent Thus, we need only consider the case where $e$ is not a loop and $v\neq w$. In this case, one of
following must occur:
\vspace{2pt}
\begin{enumerate}
\item The edge $e$ is immediately repeated in the walk $W$
That is, $W$ includes a segment of the form `$vewev$' a segment of the form `$wevew$'.
\vspace{2pt}
\item The edge $e$ is not immediately repeated, but occurs later
in the walk $W$ and in the same order
That is, either $W$ includes a segment of the form `$vew \ldots vew$' or $W$ includes a segment of the form `$
wev \ldots wev$'.
\vspace{2pt}
\item The edge $e$ is not immediately repeated, but
occurs later in the walk $W$ in the reverse order
That is, either $W$ includes a segment of the form `$vew \ldots wev$' or $W$ includes a segment of the form `$
wev \ldots vew$'.
\vspace{2pt}
\end{enumerate}
\noindent Since one of the vertices $v$ or $w$ is repeated in the first case, while both the vertices $v$ and
$w$ are repeated in the latter two cases, this completes the proof.
\vspace{30pt}
\noindent\textbf{COROLLARY}
\vspace{5pt}
\noindent\emph{For every graph $G$, if $W$ is a walk in $G$ that has no repeated vertices, then $W$ has no
repeated edges.}
\vspace{5pt}
\noindent \textbf{PROOF}
\vspace{5pt} This is the contrapositive of Lemma I.
\vspace{10pt}
\newpage
\noindent\textbf{LEMMA II}
\vspace{5pt}
\noindent\emph{ If $G$ is a connected graph, then every pair of vertices of $G$ is connected by a `simple path'
which repeats neither edges nor vertices.}
\vspace{10pt}
\noindent \textbf{PROOF}
\vspace{2pt}Let $G$ be a connected graph. Let $u$ and $w$ be any arbitrary vertices in $G$. Since $G$ is
connected, we know $G$ contains a walk $W$ from $u$ to $w$. Denote this walk by the sequence `$ v_0 e_0 v_1
e_1 \ldots v_n e_n v_{n+1} $', where $ e_0 , e_1 , \ldots e_n$ denote edges, $v_0 , \ldots, v_{n+1}$ denote
vertices with $v_0 = u$ the starting vertex and $v_{n+1} = w$ the ending vertex.
Note that $W$ may include repeated vertices. If so, construct a new walk $W'$ from $u$ to $w$ as follows:
\begin{itemize}
\item Let $v$ be the first repeated vertex in the walk $W$. Then
$v = v_i$ and $v = v_j$ for some $i < j$. To construct the new walk $W'$, delete the segment of the original
walk between the first occurrence of $v$ and its next occurrence, including the second occurrence of $v$. That
is, replace
\[\underbrace{v_0}_u e_1 v_1 e_2 \ldots v_{i-1} e_{i-1} \overbrace{v_i}^v \underbrace{ e_i v_{i+1} e_{i+1} \ldots e_{j-1} v_{j-1} e_{j}
\overbrace{ v_j}^v }_{\mbox{delete}} e_{j+1} v_{j+1}\ldots v_{n-1} e_{n-1} v_n e_n \underbrace{v_{n+1} }_w \]
by
\[u e_1 v_1 e_2 \ldots v_{i-1} e_{i-1} \overbrace{v_i}^v e_{j+1} v_{j+1} \ldots v_{n-1} e_{n-1} v_n e_n w \]
Since `$v e_{j+1}$' appeared in the original walk $W$, we know the edge $e_{j+1}$ is incident on the vertex $v=
v_i$. Thus, the new sequence of alternating edges and vertices is also a walk from $u = v_0$ to $w= v_{n+1}$.
\vspace{5pt}
\emph{(Also note that if $j = n+1$, then the repeated
vertex was $w=v_{n+1}$ and the walk now ends at $v_i$, where we know that $v_i = v_j = v_{n+1}= w$; thus, the
new walk also ends at $w$.)}
\item If the new walk $W'$ contains a repeated vertex,
we repeat the above process. Since the sequence is finite, we know that we will obtain a walk with no repeated
vertices after a finite number of deletions.
\end{itemize}
\noindent In this way, we obtain a new walk $S$ from $u$ to $w$ that contains no repeated vertices. By the
corollary to Lemma I, it follows that $S$ contains no repeated edges. Thus, by definition of simple path, $S$
is a simple path from $u$ to $w$. Since $u$ and $w$ were arbitrary, this completes the proof.
\end{document}