# Dénes König, “The labyrinth problem”

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}

## § 1. Statement of the problem. Wiener’s solution.

Theorem II 5 is closely related to the labyrinth problem1), 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 ABCQRS (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=ABZ 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=ABZ. 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.

## § 2. Trémaux’s solution.

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émaux1. His procedure is as follows:

1 See Lucas [1, vol. I, pp. 47–51]. {38} If, after starting at an arbitrary vertex A1, 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=A1, 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 some1 arrival at A1 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

1The journey must not broken off merely because you have arrived back at A1 for the first time.

2Tré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

A1A2,A2A3,,Aρ1Aρ,AρAρ+1,,AnA1,(1)

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 A1,A2,A3, that has been visited before, say as Aν (ν<μ). Two cases are now possible. (α) The edge Aμ1Aμ has not been walked before; then, since Aμ has already been visited as Aν, you must retreat, i.e. Aμ1Aμ has the required property. (β) Aμ1Aμ has been walked before, i.e. for some ρ<μ we must have Aμ1Aμ=Aρ1Aρ; 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μ1Aρ, this can happen only in the case ρ=μ1. Substituting this value of ρ [into the above], we obtain Aμ1Aμ=Aμ2Aμ1, whence now Aμ2Aμ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ρ1Aρ; thus Aρ+1=Aρ1. If this edge AρAρ+1 (=Aρ1Aρ) 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ρ1Aρ, and joining Aρ1 to Aρ. According to Theorem I 3 there then exists also in G a route not containing the edge Aρ1Aρ and joining these two points. But then Theorem I 13 implies that G is indeed connected.

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

A1A2,A2A3,,Aρ2Aρ1,Aρ+1Aρ+2,,AμA1.(2)

This represents a journey on G, since Aρ1Aρ (like every edge in general) can occur at most twice in (1), so that Aρ1Aρ 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σ1Aσ (where σ is distinct from both ρ and ρ+1) at Aσ, then by choosing the edge that immediately follows Aσ1Aσ 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σ1Aσ=Aρ2Aρ1 to Aρ+1Aρ+2 the rules are not broken. First (Fig. 21) suppose Aρ2Aρ1=Aρ+2Aρ+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ρ+1K 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ρ+1Aρ+2, which has already been walked, but rather this edge Aρ+1K. – Secondly suppose Aρ+1Aρ+2Aρ2Aρ1 (Fig. 22). After walking Aρ2Aρ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ρ2Aρ1 could not have been continued by Aρ1Aρ. By passing from Aρ2Aρ1 to Aρ+2Aρ+1 in G we should therefore have broken the rules only if Aρ+1Aρ+2 had already been visited and a third edge Aρ+1K 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ρ+1Aρ+2 but by Aρ+1K.

(β) We prove that the rules are followed if during the journey on G the edge Aσ1Aσ=Aσ1Aρ is allowed to be followed by the edge AσAσ+1=AρAσ+1, provided that σ>ρ+1, so that the double traverse of Aρ1Aρ has already taken place. Since Aρ is not an endpoint of G (for there are at least two edges ending at Aρ, namely Aρ1Aρ and Aσ1Aρ), Aρ must already have been traversed once, since otherwise this double traverse could not be regular. Thus if firstly Aσ1Aρ=Aσ+1Aρ and thus Aσ1=Aσ+1, then this retreat is also regular on G. But if secondly Aσ1Aρ and AρAσ+1 are distinct (Fig. 23), then Aσ1Aρ 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σ1Aρ1 to Aρ1Aσ+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σ1Aρ1Aρ1Aσ+1 (Fig. 24), then Aσ1Aρ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.

## § 3. Tarry’s solution.

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 A1 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 direction2.

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

Let A1,A2,A3, be the vertices of the journey, in the order in which they are [first] visited. It is clear that all the edges A1K ending at A1 have already been traversed in the direction of K, for otherwise the journey could not have broken off at A1. Since A1 has been reached as many times as it has been left, every edge A1K must also have been traversed in the direction of A1. We show that the edges ending at the remaining vertices An have also been traversed in both directions. If this were not the case, the sequence A1,A2,A3, would have a first point An such that some edge AnK had not been traversed twice. Since An has also been left as often as it has been reached, there must be both an edge AnK1 that has not been traversed in the direction of K1, and an edge AnK2 that has not been traversed in the direction of An. But now, for the entry edge AαAn of An, we certainly have α<n, so that AαAn (like all edges ending at Aα) has also been traversed in the direction of Aα. But, according to Tarry’s rule, this is regular only if all edges AnK ending at An have been traversed in the direction of K. And this {43} contradicts the fact that AnK1 has not been walked in the direction of K1.

It remains only to show that every point of the graph is one of the points Ai, and has thus been visited during the journey. Let us assume that a vertex B has not been visited. We join B to A1 though a path A1B1B2Bν (Bν=B). Let Bα be the first point in the sequence B1,B2, that has not been visited during the journey. Then Bα1 has been visited (if α=1 we set Bα1=A1), so that, as we have seen, Bα1Bα has been walked (indeed twice). Thus Bα has also been visited, contrary to our assumption.

This concludes the proof of Tarry’s theorem.

## § 4. Connection between Trémaux’s solution and Tarry’s solution.

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 journey1.

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 P and that, after P has been visited for the nth time (n=1,2,3,), have been walked exactly once. If you arrive for the nth time (n>1) at P via an edge that is being walked for the first time, you must retreat, and thus ρn=ρn1. But if this edge has already been traversed once, it now ceases to be an edge traversed exactly once. Thus ρn=ρn12 or ρn=ρn1, according as the edge along which we continue the journey – after arriving at P for the nth time – has also been walked once before or not. From ρ1=2 it thus follows that ρ2=0 or 2, and thus also ρ3=0 or 2, etc.:  every ρn is either 0 or 2 (if ρκ=0, then of course ρκ+1=ρκ+2==0).

{44} Let us now assume that after the nth arrival at P, via the edge QnP (n>1), the entry edge Q1P of P has been chosen as the continuation of the journey (we have QnPQ1P since otherwise, because of n>1, Q1P would be walked three times). After the (n1)th passage of P, both Q1P and QnP have already been walked. For Q1P this is clear, since n>1. For QnP it follows from the fact that otherwise, after the nth arrival at P, instead of choosing PQ1 you would have had to retreat via QnP. On the other hand, before the nth arrival at P these two edges have been walked only once, for otherwise the walking of these edges during the nth passage through P would not accord with Trémaux’s rules. Therefore, since ρn1 cannot exceed 2, ρn1=2. Thus, before the nth arrival at P, among all the edges KP only Q1P and QnP have been walked exactly once, while the other edges ending at P have been walked twice, since if one of them had not been walked the choice of the already-walked edge PQ1 after the nth arrival at P would not be regular. But according to Trémaux’s theorem no edge can be walked twice in the same direction; so that, with the exception of PQ1, all the edges PK have been walked in the direction of K. Thus on the nth arrival at P we have that PQ1 is indeed the only PK that has not been walked in the direction of K.

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}

## § 5. Reversed journeys.

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

A1A2 … Aμ1AμAμ+1 … A1(I)

is a Tarry journey, so also is the reversed journey

A1 … Aμ+1AμAμ1 … A2A1.(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μ+1Aμ 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μ+1Aμ 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μ+1Aμ=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μ+1AμAμAμ1. On the corresponding transition from Aμ1Aμ 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μ1Aμ 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μ+1Aμ 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 graph1).

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 AM 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 A1 and A2, then certain edges of this chain form a path that likewise joins the vertices A1 and A2.

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