Translated from “Das Labyrinthenproblem”, Theorie der endlichen und unendlichen Graphen (Leipzig, 1936), Chapter III, pp. 35–46.

In his commentary on the English translation of König’s book, W. T. Tutte writes: “To most graph theorists there are two outstanding landmarks in the history of their subject. One is Euler’s solution of the Königsberg Bridges Problem, dated 1736, and the other is the appearance of Dénes König’s textbook in 1936.” In Chapter III of this book, König discusses in detail the maze-solving algorithms of Wiener, Trémaux, and Tarry.

In the course of the chapter, König refers to theorems from Chapters I and II and items from the bibliography. These have been added at the end of this web page.

{35}

Theorem II 5
is closely related to the *labyrinth problem*^{1}),
which will be treated in this chapter.
Since the width of the alleys need not be considered, a labyrinth can be *identified* with a graph,
more precisely a *finite* and *connected* graph; the vertices of this graph correspond in the labyrinth
to the branch points and the endpoints of the blind alleys. So for instance the labyrinth of
Fig. 18 corresponds to the graph of Fig. 19 (or also the graph of Fig. 20).
It is now required to give a method for reaching a specified point, which is usually treated as the centre
of the labyrinth. Since it is entirely arbitrary which point
is treated as the centre, the problem is only to be solved by specifying a way to reach every point
of the labyrinth. If the plan of the whole
{36}
labyrinth is known, there is of course, since there are only finitely many possibilities, no difficulty.
We do not however wish to assume that we know the plan of the labyrinth.
Instead, all that will be assumed is that, if while walking in the labyrinth one reaches any branch point *X*
(or the endpoint *X* of a blind alley), the labyrinth (the graph) is known
“in the neighbourhood of *X* ”,
i.e. the alleys (edges) ending at *X* are known, as are also certain properties of the path already covered,
insofar as these relate to the point *X* just reached.

^{1})
Almost all works on recreational mathematics give some attention to labyrinths. Apart from the already-mentioned
passages in the books by Lucas, Rouse Ball, and Ahrens, we may also mention: H. E. Dudeney,
Amusements in Mathematics, London 1917, where many labyrinths can be found (pp. 127–137).

We will first assume that if during the journey one arrives at a vertex *P*, it is known for every edge ending at *P*
whether it has already been traversed; besides this we assume that (like Theseus with the aid of Ariadne’s thread)
*one can at any moment retrace in the opposite direction the whole of the path already covered*
(with the same repetitions). Under these assumptions the problem was solved by
Wiener, [1]^{1})
who was the first ever to treat the age-old problem of the labyrinth as a mathematical one.
– Wiener’s instructions (in a somewhat specialized form) run as follows:

^{1})
Here we are concerned with the second part of this note. The first part (where Wiener tacitly
restricts himself to *plane* labyrinths) has no real mathematical content,
since the problem solved there, that of specifying a method for finding one’s way
back to the starting-point, has a trivial solution: stay where you are.

*Starting at an (arbitrary) vertex A, choose entirely at random the edges AB, BC, CD, … until you arrive
at an endpoint (dead end) Q of the graph or at a vertex Q that has already been visited.
Having arrived at Q, retreat and follow in reverse the route already covered, until you first arrive at
a vertex R at which there is an edge that has not yet been traversed.
Having arrived at this R, deviate and follow any as yet untraversed edge RS, then continue the journey
over untraversed edges in an arbitrary way, until you arrive at an endpoint or a vertex
that has already been visited; here retreat, etc.
*

We prove that the sequence of edges *ABC*…*Q*…*RS*… (i) leads back to *A* and (ii) then
contains every edge of the graph.

If there is no deviation at all, one will naturally arrive back at *A*.
But if there is a deviation, then since at every deviation a new edge is added [to those already covered]
and the graph has only finitely many edges, there must
{37}
be a final deviation.
Since the number of vertices is also finite, one must after this deviation reach an endpoint
or an already-visited vertex *Z*. According to our instructions one must then, since no further deviation is possible,
traverse this whole sequence of edges
*F*=*AB*…*Z*
in the reverse direction, so that one does indeed arrive back at *A*.

That every edge of the original graph *G* has been traversed, is proved as follows.
Let us assume that this is not the case: then the untraversed edges form a proper subgraph
*G*″ of *G*, while the traversed edges form the (connected) subgraph
*G*′ of *G*. *G*′ and *G*″ have no common edge; they have however at least one
common vertex *P*, for otherwise *G*=*G*′+*G*″
(Theorem I 24)
would not be connected. Since *P* belongs to *G*′, *P* is a vertex of the edge sequence
*F*=*AB*…*Z*. Since *P* also belongs to *G*″,
there is an untraversed edge ending in *P*. During the above-mentioned traversal of *G* in the direction of *A*
we must therefore deviate at *P*. And this contradicts the fact that the last deviation has already taken place.

The above-described method of Wiener cannot be called economical, since in general the edges have to be walked through a great many times. This is the more noticeable in that – by Theorem II 5 – there is a journey through all the edges of the graph in which no edge is traversed more than twice. We shall show that such a solution can still be found under the assumption, not that the entire graph is known beforehand, but only that certain local properties are known at any moment after starting the journey.

We will, however, no longer suppose that the route already covered can always be retraced in the reverse direction,
but instead of this supposition of Wiener’s we make the (partly stronger and partly weaker)
assumption that, on arrival during the journey at any vertex *P*, it is known for every edge
ending at *P* whether it has already been walked, and if so how many times (the directions in which
the edges have been walked are *not* assumed to be known here). Under this assumption, the labyrinth problem
has been solved in an elegant way by Trémaux^{1}. His procedure is as follows:

^{1} See Lucas [1, vol. I, pp. 47–51].
{38}
*
If, after starting at an arbitrary vertex A_{1},
you arrive via an edge PQ at a vertex Q
which is not an endpoint (dead end) of the graph and which you are visiting for the first time, then
continue the journey with any other edge QR. But if Q has either been visited before or is an endpoint
and PQ has just been walked for the first time, then retreat, i.e. continue the journey with the same edge PQ
(in the reverse direction QP). If both Q and PQ have been visited before, proceed along any unused edge QR
or, if no such edge is available, along an edge QR that has been used only once.
*

If these rules are followed, then every edge is travesred at most twice; since the number of edges is finite
the journey must therefore come to an end, i.e. you must sometime arrive at a vertex *K* such that
all edges ending at *K* have already been traversed twice. Moreover, we must have
*K*=*A*_{1}, for otherwise we should have (for the endpoint *K* of an *open*
sequence of edges) a contradiction to
Theorem I 2.
We shall now prove *Trémaux’s theorem*, which states that when the procedure is broken off
on some^{1} arrival at *A*_{1} *every edge has been traversed twice,
that is, once in each direction.* We wish to set out our rather complicated proof in full detail,
the more so since we are not aware of any complete proof of Trémaux’s theorem in the literature.^{2}

^{1}The journey must not broken off merely because you have arrived back at *A*_{1} for the *first* time.

^{2}Trémaux did not, it seems, publish his proof.
The proof by
Lucas [1, vol. I, pp. 47–51]
is – so he says – a slight modification of Trémaux’s.
This proof by Lucas is not complete, for firstly the case that the edges denoted there by *ZA* and *ZY* are identical
(a case that can actually happen) is left out of consideration, and secondly an essential statement at the end of the
proof is dealt with by the brief remark “on demontrera de même”. – In
Ahrens [2, vol. II, pp. 192–194]
both these critical points are treated in more detail, but even his
proof contains an important omission, to which we shall shortly return (see following footnote). – It may
be remarked here that neither Lucas nor Ahrens mentions the corollary that the edges are walked twice
in *opposite* directions.

Let

*A*_{1}*A*_{2},*A*_{2}*A*_{3},…,*A*_{ρ−1}*A*_{ρ},*A*_{ρ}*A*_{ρ+1},…,*A _{n}A*

in that order, be the edges that are covered in a *regular* (i.e. conforming to Trémaux’s rules) journey
on a finite connected graph *G*. We first prove
{39}
that *there must be in *(1)* an edge such that immediately after walking it the same edge is walked again
(in the opposite direction)*, i.e. that you must retreat at least once.
For let *A*_{μ} be the first member of the sequence *A*_{1},*A*_{2},*A*_{3},…
that has been visited before, say as *A*_{ν} (ν<μ). Two cases are now possible.
(α) The edge *A*_{μ−1}*A*_{μ} has not been walked before; then, since *A*_{μ} has already been visited
as *A*_{ν}, you must retreat, i.e. *A*_{μ−1}*A*_{μ} has the required property.
(β) *A*_{μ−1}*A*_{μ} has been walked before, i.e. for some ρ<μ we must have
*A*_{μ−1}*A*_{μ}=*A*_{ρ−1}*A*_{ρ}; but now *A*_{μ−1} has not been visited before, and can thus because of
ρ−1<μ−1 not be = *A*_{ρ−1}, whence *A*_{μ−1}=*A*_{ρ};
but, since for ρ<μ−1 we certainly have *A*_{μ−1}≠*A*_{ρ}, this can happen only in the case
ρ=μ−1. Substituting this value of ρ [into the above], we obtain
*A*_{μ−1}*A*_{μ}=*A*_{μ−2}*A*_{μ−1}, whence now *A*_{μ−2}*A*_{μ−1} has the required property.
(It can easily be shown that case (β) occurs if and only if *A*_{μ−1} is an endpoint of *G*.)

Let therefore *A*_{ρ}*A*_{ρ+1} be an edge that is identical with the immediately preceding edge *A*_{ρ−1}*A*_{ρ};
thus *A*_{ρ+1}=*A*_{ρ−1}.
If this edge *A*_{ρ}*A*_{ρ+1} (=*A*_{ρ−1}*A*_{ρ}) is removed from *G*, then the remaining edges form
a subgraph *G*′ of *G*. We prove that *the graph* *G*′ *is also connected*.
If *A*_{ρ} is an endpoint of *G*, this follows from
Theorem I 14.
If *A*_{ρ} is not an endpoint, then the retreat at *A*_{ρ} can be regular only if *A*_{ρ} has
already been visited, and then some subsequence of the sequence (1) yields an open sequence of edges,
not containing the edge *A*_{ρ−1}*A*_{ρ}, and joining *A*_{ρ−1} to *A*_{ρ}. According to
Theorem I 3
there then exists also in *G* a route not containing the edge *A*_{ρ−1}*A*_{ρ} and joining these two points. But then
Theorem I 13
implies that *G*′ is indeed connected.

If in (1) *A*_{ρ−1}*A*_{ρ} and *A*_{ρ}*A*_{ρ+1} are deleted, there results likewise,
since *A*_{ρ−1}=*A*_{ρ+1}, a sequence of edges:

*A*_{1}*A*_{2},*A*_{2}*A*_{3},…,*A*_{ρ−2}*A*_{ρ−1},*A*_{ρ+1}*A*_{ρ+2},…,*A*_{μ}*A*_{1}.(2)

This represents a journey on *G*′, since *A*_{ρ−1}*A*_{ρ} (like every edge in general)
can occur at most twice in (1), so that *A*_{ρ−1}*A*_{ρ} is not contained in (2).
We prove that (2) *gives a regular journey on* *G*′, i.e. that if you arrive via
any edge *A*_{σ−1}*A*_{σ} (where σ is distinct from both ρ and ρ+1) at *A*_{σ},
then by choosing the edge that immediately follows *A*_{σ−1}*A*_{σ} according to (2)
you conform to Trémaux’s rules.^{1}

^{1} In the above-mentioned proof by Ahrens of Trémaux’s theorem,
this theorem, without being proved or formally stated, is implicitly used (on p. 193 and on p. 194)
in an essential way.

{40}
This is clear, if *A*_{σ} is distinct from both *A*_{ρ} and
*A*_{ρ+1} (=*A*_{ρ−1}),
and again if σ<ρ−1, for in this case
Trémaux’s rules permit the same possibilities for *G*′ as for *G*.
Since σ=ρ and σ=ρ+1 are excluded, only the following three cases need to be dealt with:
(α) σ=ρ−1;
(β) σ>ρ+1 and *A*_{σ}=*A*_{ρ};
(γ) σ>ρ+1 and *A*_{σ}=*A*_{ρ−1} (=*A*_{ρ+1}).

(α) We must show that in the transition from *A*_{σ−1}*A*_{σ}=*A*_{ρ−2}*A*_{ρ−1} to *A*_{ρ+1}*A*_{ρ+2}
the rules are not broken. *First* (Fig. 21)
suppose *A*_{ρ−2}*A*_{ρ−1}=*A*_{ρ+2}*A*_{ρ+1} (so that *A*_{ρ−2}=*A*_{ρ+2}).
Then a transition to the identical edge (retreat) is certainly regular in *G*′, if
*A*_{ρ−1} is an endpoint of *G*′ or has already been visited. And one of the two is certainly the case,
for otherwise there would have to be a third and untraversed edge *A*_{ρ+1}*K* ending at *A*_{ρ+1},
and then during the journey on *G* you would have had to choose after *A*_{ρ}*A*_{ρ+1} not the edge
*A*_{ρ+1}*A*_{ρ+2}, which has already been walked, but rather this edge *A*_{ρ+1}*K*. – *Secondly*
suppose *A*_{ρ+1}*A*_{ρ+2}≠*A*_{ρ−2}*A*_{ρ−1} (Fig. 22).
After walking *A*_{ρ−2}*A*_{ρ−1} in *G*′ you must not retreat,
since *A*_{ρ−1} is not an endpoint of *G*′ and since you would otherwise have had to retreat
in the journey on *G*, so that *A*_{ρ−2}*A*_{ρ−1} could not have been continued by *A*_{ρ−1}*A*_{ρ}.
By passing from *A*_{ρ−2}*A*_{ρ−1} to *A*_{ρ+2}*A*_{ρ+1}
in *G*′ we should therefore have broken the rules only if
*A*_{ρ+1}*A*_{ρ+2} had already been visited and a third edge
*A*_{ρ+1}*K* had not been walked at all. But then in the journey on *G*
*A*_{ρ}*A*_{ρ+1} would have had to be followed not by *A*_{ρ+1}*A*_{ρ+2} but by *A*_{ρ+1}*K*.

(β) We prove that the rules are followed if during the journey on *G*′ the edge
*A*_{σ−1}*A*_{σ}=*A*_{σ−1}*A*_{ρ} is allowed to be followed by the edge
*A*_{σ}*A*_{σ+1}=*A*_{ρ}*A*_{σ+1}, provided that σ>ρ+1, so that the
double traverse of *A*_{ρ−1}*A*_{ρ} has already taken place.
Since *A*_{ρ} is not an endpoint of *G* (for there are at least two edges ending at *A*_{ρ}, namely
*A*_{ρ−1}*A*_{ρ} and *A*_{σ−1}*A*_{ρ}),
*A*_{ρ} must already have been traversed once, since otherwise this double traverse could not be regular.
Thus if *firstly*
*A*_{σ−1}*A*_{ρ}=*A*_{σ+1}*A*_{ρ} and thus *A*_{σ−1}=*A*_{σ+1},
then this retreat is also regular on *G*′. But if *secondly*
*A*_{σ−1}*A*_{ρ} and *A*_{ρ}*A*_{σ+1} are distinct (Fig. 23), then
*A*_{σ−1}*A*_{ρ} must have already been traversed for the second time
(for otherwise you would have had to retreat); thus we cannot have broken the rules
{41}
unless there was a fourth and still untraversed edge
*A*_{ρ}*K* and *A*_{ρ}*A*_{σ+1} had already been traversed once; but then we should have already broken the rules
by the same transition in the journey on *G*.

(γ) We show that the transition from
*A*_{σ−1}*A*_{ρ−1} to *A*_{ρ−1}*A*_{σ+1} during the journey on *G*′ is regular, provided that
this was the case for *G* and σ>ρ+1. *Firstly* suppose these two edges are identical, so that
*A*_{σ+1}=*A*_{σ−1}. This retreat is regular, since *A*_{ρ−1} has also been traversed during
the journey on *G*′. If *secondly*
*A*_{σ−1}*A*_{ρ−1}≠*A*_{ρ−1}*A*_{σ+1} (Fig. 24),
then *A*_{σ−1}*A*_{ρ−1} must already have been traversed once, and we can finish just as
in the second case of (β).

This concludes the proof that (2) represents a regular journey on *G*′.

Now we can prove Trémaux’s theorem by complete induction on the number of edges,
since the theorem holds for a graph with a single edge, as can be seen immediately.
If during the journey on *G* given by (1), which satisfies Trémaux’s rules, you did not traverse
every edge of *G* once in each direction, then of course not every edge of *G*′ would have been
traversed once in each direction. But since we have proved that *G*′ is connected and that the
journey (2) on *G*′ satisfies Trémaux’s rules, this is impossible; for we have assumed the truth
of the theorem for the connected finite graph *G*′, which has 1 less edge than *G*.

This concludes the proof of Trémaux’s theorem.

We can solve the labyrinth problem in a rather simpler way if, instead of the assumptions that form the basis
of Trémaux’s solution, we adopt the following assumptions: *Every time we arrive at any vertex P
it is known for every edge PK ending at P whether it has been traversed in the direction of K;
and we can always determine the edge by which P was reached for the first time (the “entry edge” of P).
*

{42}
For this case the problem was solved by
Tarry [1]^{1}.
Tarry’s instructions are as follows:

^{1} Referring to this work,
Rouse Ball [1, p. 207]
gives a still simpler
“solution”, which however is wrong. Indeed, simple examples show that with Rouse Ball’s
procedure it is possible to come to a halt before traversing all the edges. In the same place Rouse Ball
restricts the treatment explicitly to *two-dimensional* labyrinths. This is quite unnecessary.
Everything remains valid for e.g. *catacombs*, where the alleys can run in an arbitrary way
under and over one another.

*
If you come via an edge PQ to a vertex Q, continue the journey along any edge QR that has not yet been traversed
in the direction of R; but do not choose QR to be the entry edge of Q unless all other edges QK
ending at Q have already been traversed in the direction of K.
*

By means of this rule it is guaranteed that every edge is traversed at most once in either direction,
and thus at most twice in all. Just as for the Trémaux journeys above, so it follows here that the
journey must break off sometime, and that this can happen only when you arrive back at the starting-point
*A*_{1} of the journey.
We shall now prove Tarry’s theorem, which states that *when the journey is broken off, every edge
has been traversed twice, once in each direction*^{2}.

^{2} The first part of the following proof is due to Tarry.

Let *A*_{1},*A*_{2},*A*_{3},… be the vertices of the journey, in the order in which they are [first] visited.
It is clear that all the edges *A*_{1}*K* ending at *A*_{1} have already been traversed in the direction of *K*,
for otherwise the journey could not have broken off at *A*_{1}. Since *A*_{1} has been reached as many times as it has been left,
every edge *A*_{1}*K* must also have been traversed in the direction of *A*_{1}. We show that the edges ending at the
remaining vertices *A _{n}* have also been traversed in both directions. If this were not the case, the sequence

It remains only to show that every point of the graph is one of the points *A _{i}*, and has thus been visited
during the journey. Let us assume that a vertex

This concludes the proof of Tarry’s theorem.

Between Trémaux journeys and Tarry journeys there is an interesting connection, which is expressed through the following theorem:

*Every Trémaux journey is also a Tarry journey*^{1}.

^{1} See the *Remarque* by
Tarry [1, p. 190].

In other words, we shall now prove the following:

*
If during a Trémaux journey you arrive at a vertex P, which is distinct from the starting-point of the journey,
then the journey will only be continued along the entry edge of P if all other edges PK ending at P
have already been walked in the direction of K.
*

This is clear, if *P* is reached for the first time, so that *P* is an endpoint of the graph; we can thus assume
that this is not the case. We shall denote by ρ* _{n}* the number of edges that end at

{44}
Let us now assume that after the *n*th arrival at *P*, via the edge *Q _{n}P* (

Here let us add a remark about Tarry’s solution. If one were to modify Tarry’s rule so that, instead of requiring that no edge should be walked twice in the same direction, nothing more was asked than that no edge should be walked three times, then the labyrinth problem would not be solved by the new rule. As the journey in Fig. 25 shows, it is then possible for edges to remain unwalked.

Even though, as has just been proved, Trémaux’s rules arise as a specialization of Tarry’s, the result attained through Trémaux’s solution of the labyrinth problem is in a sense more general than through Tarry’s, inasmuch as with Trémaux journeys the requirement of opposite directions is (so to speak) automatically fulfilled, and the direction in which an edge must be walked on returning to an endpoint of that edge need not be assumed known.

{45}

Finally, two further remarks will be made, concerning the reversal of a journey. For both of these I am indebted to the kind communication of J. Kürschák.

*If*

*A*_{1}*A*_{2} … *A*_{μ−1}*A*_{μ}*A*_{μ+1} … *A*_{1}(I)

*is a Tarry journey, so also is the reversed journey*

*A*_{1} … *A*_{μ+1}*A*_{μ}*A*_{μ−1} … *A*_{2}*A*_{1}.(II)

Indeed, it is clear that the (completed) Tarry journey is *characterized* by the following three properties:

1. No edge is traversed twice in the same direction.

2. The entry edge of any vertex *P* is identical with the *exit edge* of *P*, along which *P* is quitted
for the last time (otherwise, contary to Tarry’s theorem, this entry edge would be traversed only once).

3. All edges are traversed in both directions (this is Tarry’s theorem).

Now (II) obviously has every one of these three properties, provided that this is true of (I).

The correcponding result also holds for Trémaux journeys. Indeed, we prove the theorem:

*If *(I)* is a Trémaux journey, then so also is the reversed journey* (II).

We must show that in journey (II) the transition from
*A*_{μ+1}*A*_{μ} to *A*_{μ}*A*_{μ−1} satisfies Trémaux’s rules. –
If in this transition *A*_{μ} is visited for the first or last time, then this transition satisfies
Trémaux’s rules provided it satisfies Tarry’s (even when *A*_{μ} is an endpoint of the graph).
But this is certainly the case, since (I) – as a Trémaux journey – and thus also (II) – as
the reversal of a Tarry journey – are Tarry journeys.
We need therefore only take account of the case where in the transition from *A*_{μ+1}*A*_{μ} to *A*_{μ}*A*_{μ−1}
the point *A*_{μ} occurs neither for the first nor for the last time.
Here two cases are to be distinguished.
*Firstly* let *A*_{μ+1}*A*_{μ}=*A*_{μ}*A*_{μ−1}.
Then, since every edge is walked only twice, this edge has not been walked before. The retreat along this edge
therefore satisfies Trémaux’s rules.
*Secondly* let *A*_{μ+1}*A*_{μ}≠*A*_{μ}*A*_{μ−1}.
On the corresponding transition from *A*_{μ−1}*A*_{μ} to *A*_{μ}*A*_{μ+1} in (I) *A*_{μ} is then likewise
reached neither
{46}
for the first nor for the last time.
On this transition therefore (α) *A*_{μ−1}*A*_{μ} has already been walked for the second time
(for otherwise you would have to retreat at *A*_{μ}) and (β) *A*_{μ}*A*_{μ+1} only for the first time.
Indeed, if *A*_{μ}*A*_{μ+1} had been walked for the second time, then on this passage of *A*_{μ}
the number ρ of edges ending at *A*_{μ} and walked exactly once would be decreased,
and thus – as we saw above – be equal to zero, and this is impossible, since
– in view of the fact that the Trémaux journey is at the same time a Tarry journey –
the entry path of *A*_{μ} remains walked exactly once until the last passage through *A*_{μ}.
But now (α) and (β) imply that in (II) on the transition in question *A*_{μ+1}*A*_{μ}
is walked for the second time and *A*_{μ}*A*_{μ−1} for the first time.
And this accords with Trémaux’s rules.

From Chapter I

Let {*A*,*B*,*C*,…} be a set of “points”. If one joins certain pairs, each consisting of two distinct
points of this set, by one or more “lines”, the resulting system is called a **graph**.
Those of the points {*A*,*B*,*C*,…} that are joined to at least one point are called the **vertices**
[*Knotenpunkte*] or points [*Punkte*] of the graph (vertices that one might call “isolated”
are thus excluded). The inserted lines are called the **edges** [*Kanten*] of the graph^{1}).

^{1}) In this sense the word *graph* seems to have been first used by
Sylvester [3, p. 149]
in 1878.
As a short, suggestive term that can be used in all languages it seems to us the most appropriate.
In the same or similar sense the following expressions are also used: *Linearkomplexion*, *Liniensystem*,
*Streckenkomplex*, *Kantenkomplex*, *Netz*.
The French very often use *réseau*. For *Knotenpunkt* the following have become established in English:
*node*, *knot*, *vertex*; in French: *sommet*, *nœud*, *carrefour*; and for *Kante*
in English: *branch*, *edge*; in French: *chemin*, *arête*, *lien*.

In the definition of a graph we have assumed that every edge joins two *distinct* points with one another.
It is often convenient to treat graphs **in the broader sense**, i.e. to allow also those edges that join
a vertex to itself. Such an edge is called a **loop** [*Schlinge*] and can be denoted by PP.

Theorem I 1: A set Π of points and a set Κ of edges form respectively the set of vertices and the set of edges of a (necessarily unique) graph, if and only if the endpoints of every edge in Κ belong to Π and every point of Π is the endpoint of an edge in Κ.

If all the edges of a (finite) graph can be enumerated in a sequence of the form

*AB*,*BC*,*CD*,…,*KL*,*LM*(1)

where every vertex and every edge can occur any (finite) number of times, then the graph is called a **chain**.
According as *A*≠*M* or *A*=*M*, the chain is called **open** or **closed**. In the first case we say that
it *joins* the vertices *A* and *M*, or again, that *A* and *M* are the **endpoints** of the open chain.
The remaining vertices, and all the vertices of a closed chain, are called **inner vertices**.
If an edge oocurs *n* times in (1), then *n* is called the **multiplicity** of this edge
w.r.t. the chain. We clearly have

Theorem I 2: The sum of the multiplicities of all edges of a chain that end in the same vertex *P* is even or odd,
according as *P* is an inner vertex or an endpoint of the chain.

If in (1) no edge occurs twice, i.e. if every multiplicity is 1, then the chain is called an (open or closed)
**walk**.

If further the points *A*,*B*,…,*L*,*M* are all distinct from one another, then the open walk
is called a **path**; if *A*=*M* but *A*,*B*,…,*L* are all distinct from one another, then the closed walk
is called a **cycle**.

Theorem I 3: If certain edges of a graph form an open chain that joins the vertices A_{1} and A_{2},
then certain edges of this chain form a path that likewise joins the vertices A_{1} and A_{2}.

Theorem I 13: If in a connected graph *G* there is a path *W* that joins the endpoints *A* and *B* of an edge *AB*
and does not contain this edge *AB*, then the graph *G*′ that results from the removal of the edge *AB* from *G*
is likewise connected.

Theorem I 14: If one removes from a connected graph *G* one of its end edges (dead ends) or an edge
of one of its cycles, then the remaining edges still form a connected graph *G*′.

Here it is convenient to introduce the notion of **graph addition**. Let {*G*_{α}} be any set of graphs.
By Theorem 1 the vertices and edges that are contained in at least one of the graphs
*G*_{α} form a graph *G*. If the graphs *G*_{α} are pairwise disjoint, then we call
*G* the **sum of the graphs** *G*_{α} and write *G*=Σ*G*_{α}. The assumption that the
*G*_{α} are disjoint is essential here; only in this case do we say that a graph separates into subgraphs
*G*_{α}, and only in this case do we write equations of the form *G*=Σ*G*_{α}.

Theorem I 24: A graph is connected if and only if it is not the sum of two proper (non-empty) graphs.

From Chapter II

Theorem II 5: Every finite connected graph G can be traversed as a closed chain such that every edge is traversed exactly twice.

From the Bibliography

(W.) [2] Mathematische Unterhaltungen und Spiele, Leipzig, 1st edn, 1901; latest edn: vol. I, 3rd edn, 1921; vol. II, 2nd edn, 1918.

(W. W. Rouse) [1] Mathematical Recreations and Problems, 1st edn London 1892.
Latest French edn:
Récréations mathématiques et problèmes des temps anciens et modernes, traduit par
J. Fitz-Patrick, vols I–III, Paris 1926/27.

[12th edn (W. W. R. Ball & H. S. M. Coxeter)
Mathematical Recreations and Essays, Toronto 1974. – MB]

(E.) [1] Récréations Mathématiques, I–IV, Paris 1892–1894.

[vol. I ch. 2 = “Le jeu des ponts et des îles”;
vol. I ch. 3 = “Le jeu des labyrinthes” – MB]

(J. J.) [3] “On an application of the new atomic theory to the graphical representation of the invariants and covariants of binary quantics”, American Journal of Mathematics, 1, 1878, 64–125 = Mathematical Papers, vol. III, pp. 148–206.

(G.) [1] “Le problème des Labyrinthes”, Nouvelles Annales de Mathématiques (3), 14, 1895, 187–190.

(Chr.) [1] “Ueber eine aufgabe aus der Geometria situs”, Mathematische Annalen, 6, 1873, 29–30