Mathematics 11.

Let us try the tour corresponding to the example. The failure of the many trials does not mean that the example cannot be solved; it only means that we have not managed yet with these methods. In order to be able to say that the example does not have a solution we should check all the possible tours, which in general means very many cases, therefore it is practical to search for another method.

Let the parts of the city denoted by \latex{ A,\, B,\, C,\, D } be represented by a point each, and a bridge between two parts of the city be represented by an edge connecting the corresponding points. If the suitable path exists, then the following should hold:

Based on these only such a path network can be toured – so that we walk along every edge exactly once and we get back to the starting point in which even number of edges start from every point, i.e. the degree of every point is even. We wrote the degrees of the points next to them,so it can be seen that there are even four points the degree of which is odd, thus the bridges cannot be toured so that we walk through every bridge exactly once and we get back to the starting point. (Figure 26)

Let us consider the part of the city where we start from and the one where we will arrive in the end. If these are not the same, then the number of the bridges starting from them needs to be odd, since leaving and arriving mean one bridge each, and on top of that every leaving and arriving can happen through even number of bridges. So the degree of the points corresponding to these two parts of the city (the one we start from and the one where we arrive in the end) is odd.

The degrees of the other points of the path are even just like before, since as many times we arrive at a point on an edge we also have to leave that point on another edge.

So if we were able to tour the bridges so that we walked through every bridge exactly once but we did not get back to the part of the city where we had started from, then there would be two parts of the city with odd number of bridges starting from and even number of bridges would start from the other parts of the city. As now there are four parts of the city with odd number of bridges starting from, the bridges cannot be toured so that we walk through each of them exactly once even if we do not have to get back to the starting place.

So the degrees of the starting point and the end-point being odd and the degrees of all the other points being even are necessary conditions of a graph being able to be toured so that we walk along every edge exactly once and the starting point and the end-point of the path are distinct.

One bridge should definitely be built so that the necessary condition found in the previous part is satisfied. It can be built between any two parts of the city with odd number of bridges starting from.

Two possibilities and suitable tours belonging to each of them can be seen in Figures 27 to 28. One bridge is actually enough, and we verified it by showing a possible tour for each.

Two bridges should definitely be built so that the necessary condition found in part a) is satisfied, since a pair of two parts of the city should be connected with a bridge from which only odd number of bridges started from at the beginning. Two possibilities and suitable tours belonging to each of them are shown in Figures 29 to 30. So two bridges are actually enough, and we verified it by showing a possible tour for each.

Example: We can see trails leading from part \latex{ A } to part \latex{ D } of the city of Königsberg in the Figures 31 to 32.

Example: We can see trails leading from part \latex{ A } to part \latex{ D } of the city of Königsberg in the Figures 33 to 34.

Example: We can see paths leading from part \latex{ A } to part \latex{ B } of the city of Königsberg in the Figures 35 to 36.

Example: We can see cycles in the city of Königsberg in the Figures 37 to 38.

Example: A connected graph can be seen in Figure 39. Figure 40 shows a non-connected graph consisting of three components.

Based on example \latex{ 1 } we can formulate the following theorem:

The theorem can be proven based on part a) and b) of example \latex{ 1 }.
Another necessary condition for the existence of an Eulerian trail is that we can get from the end-points of any edge to the end-points of any edge along edges in the graph.

It is satisfied if the graph is connected, or if it is not connected, then besides one component all the other components are isolated points (Figure 41). So the graph being connected and the degree of every point being even are necessary conditions for the existence of a closed Eulerian trail in a graph not containing any isolated points.

The graph being connected and the degrees of two points being odd and the degrees of all the other points being even are necessary conditions for the existence of an open Eulerian trail in a graph not containing any isolated points.
These conditions are also sufficient.

Let us consider a connected graph in which the degree of every point is even. Weare going to show that there is a closed Eulerian trail in it. The proof is constructive; it also gives a method for finding an Eulerian trail.

Let us start from an arbitrary point \latex{ A } of the graph on an arbitrary edge, and let us number the edges in the order corresponding to the tour. If we can get to a point, then we can surely carry on from there on an edge different from the previously toured ones, as its degree is even, thus the only point, where we can get stuck, is the point \latex{ A }. It can happen that we have not toured every edge yet; in this case the trail obtained can be expanded. As the graph is connected, among the edges not toured yet there must be one incident at a point toured; let us denote this point by \latex{ B }. Let us start from \latex{ B } on edges not toured yet, then the only point, where we can get stuck, is the point \latex{ B }. Let us renumber the edges toured so that we keep the previous numbering up to \latex{ B }, then we continue the numbering on the edges toured this time, until we get back to \latex{ B }, then on the edges toured previously to \latex{ A }. Thus an expanded trail is obtained that contains every edge at most once (Figure 42).

This expanding process can be continued as long as there is an edge not toured yet. The number of the edges is finite, thus a closed Eulerian trail is obtained with this process.

By connecting the two points with odd degree with an edge the degree of every point becomes even, thus we can find a closed Eulerian trail based on the previous. If we leave away the edge just drawn, an open Eulerian trail is obtained. Based on these the following are true:

The order of the points on a possible path is: \latex{ ADFGI }. (Figure 44)

The order of the points on a possible trail is: \latex{ ADBCEDFGI }. (Figure 45)

This trail is not a path, because the point \latex{ D } occurs several times on the trail. If we leave away the part of the trail between the first and the last occurrence of \latex{ D }, then the point \latex{ D } occurs on the trail only once. Thus the path \latex{ ADFGI } leading from \latex{ A } to \latex{ I } is obtained.

The order of the points in a possible walk is: \latex{ ADFECDFGI }. (Figure 46)

This walk is not a trail, because the edge \latex{ DF } occurs several times. If we leave away the part of the walk between the two occurrences of the edge \latex{ DF }, and the edge \latex{ FG } comes after the edge \latex{ DF }, then the edge \latex{ DF } occurs only once in the walk. After this there are no more edges that occurred several times, so the walk \latex{ ADFGI } is a trail.

A cycle in the graph is for example as follows: \latex{ ABCEFDA }. (Figure 47)

By leaving away any edge of the cycle (e.g. \latex{ AD }), the two end-points of the edge divide the cycle into two paths (paths \latex{ AD } and \latex{ ABCEFD }). Then we write the path \latex{ ABCEFD } instead of the edge \latex{ AD } in the path between two arbitrary points of the graph, thus a walk is obtained between the two points, and if there is a walk between two points, then there is also a path; so the graph stays connected, if we leave away an arbitrary edge of a cycle.

Two distinct paths between the points \latex{ A } and \latex{ I } are for example (Figure 48): \latex{ ADFGI } and \latex{ ADFEHGI }. By considering the two distinct paths it can be seen that there is a cycle in the graph.

The statements highlighted during the solution of the example can be proved with the help of the generalisation of the solution; these proofs are not detailed here.

It is possible that not everyone will have got the news before it gets back to someone who had heard of it already. It means that it is not sure that the cycle in the graph passes through every point. (Figure 49)

Everyone can pass along the news, as he has at least two acquaintances: he gets it from one of them and he passes it along to the other one.

As the number of the boys is finite, it will surely get back to someone who had heard of it already. It means that there is a cycle in the graph in which the points (vertices) represent the boys and the lines (edges) connecting the points represent the transmission of the news.

The second boy, who heard of the news, needs to pass it along to a third one, so three boys will surely know about it.

Figure 50 shows that it is possible that only three boys know about it.
The following theorem can be proven similarly to the solution of the example:

Consequence: If there is no cycle in a connected graph, then it has a point of degree one.

The graph is connected, thus it does not have a point of degree zero. If the graph did not have a point of degree one, then the degree of every point would be at least two, thus because of the theorem there would be a cycle in it. However there is no cycle in the graph, therefore it has a point of degree one.