6 . He then argued that, in general, in order to make a successful journey (i.e. crossing all bridges only once) a point should be connected to an even number of lines. This is because in the middle of a journey when the traveller passes through a land mass, he or she must enter via one bridge and then leave via a different bridge. There are only two exceptions to this rule â when a traveller either begins or ends the journey. At the start of the journey the traveller leaves a land mass and requires only a single bridge to exit, and at the end of the journey the traveller arrives at a land mass and requires only a single bridge to enter. If the journey begins and ends in different locations, then these two land massesare allowed to have an odd number of bridges. But if the journey begins and ends in the same place, then this point, like all the other points, must have an even number of bridges.
So, in general, Euler concluded that, for any network of bridges, it is only possible to make a complete journey crossing each bridge only once if all the landmasses have an even number of bridges, or exactly two land masses have an odd number of bridges. In the case of Königsberg there are four land masses in total and all of them are connected to an odd number of bridges â three points have three bridges, and one has five bridges. Euler had been able to explain why it was impossible to cross each one of Königsbergâs bridges once and only once, and furthermore he had generated a rule which could be applied to any network of bridges in any city in the world. The argument is beautifully simple, and was perhaps just the sort of logical problem that Euler dashed off before dinner.
The Königsberg bridge puzzle is a so-called network problem in applied mathematics, but it inspired Euler to consider more abstract networks. He went on to discover a fundamental truth about all networks, the so-called
network formula
, which he could prove with just a handful of logical steps. The network formula shows an eternal relationship between the three properties which describe any network:
where
V
= the number of vertices (intersections) in the network,
L
= the number of lines in the network,
R
= the number of regions (enclosed areas) in the network.
Euler claimed that for any network one could add the number of vertices and regions and subtract the number of lines and the total would always be 1. For example, all the networks in Figure 7 obey the rule.
Figure 7. All conceivable networks obey Eulerâs network formula.
It is possible to imagine testing this formula on a whole series of networks and if it turned out to be true on each occasion it would be tempting to assume that the formula is true for all networks. Although this might be enough evidence for a scientific theory, it is inadequate to justify a mathematical theorem. The only way to show that the formula works for every possible network is to construct a foolproof argument, which is exactly what Euler did.
Euler began by considering the simplest network of all, i.e. a single vertex as shown in Figure 8 . For this network the formula is clearly true: there is one vertex, and no lines or regions, and therefore
Euler then considered what would happen if he added something to this simplest of all networks. Any extension to the single vertex requires the addition of a line. The line can either connect the existing vertex to itself, or it can connect the existing vertex to a new vertex.
First, let us look at connecting the vertex to itself with this additional line. As shown in Figure 8 , when the line is added, this also results in a new region. Therefore the network formula remains true because the extra region (+1) cancels the extra line (â1). If further lines are added in this way the network formula will still remain true because each new line will create a new region.
Figure 8. Euler proved his network formula by showing that it was true for
So, in general, Euler concluded that, for any network of bridges, it is only possible to make a complete journey crossing each bridge only once if all the landmasses have an even number of bridges, or exactly two land masses have an odd number of bridges. In the case of Königsberg there are four land masses in total and all of them are connected to an odd number of bridges â three points have three bridges, and one has five bridges. Euler had been able to explain why it was impossible to cross each one of Königsbergâs bridges once and only once, and furthermore he had generated a rule which could be applied to any network of bridges in any city in the world. The argument is beautifully simple, and was perhaps just the sort of logical problem that Euler dashed off before dinner.
The Königsberg bridge puzzle is a so-called network problem in applied mathematics, but it inspired Euler to consider more abstract networks. He went on to discover a fundamental truth about all networks, the so-called
network formula
, which he could prove with just a handful of logical steps. The network formula shows an eternal relationship between the three properties which describe any network:
where
V
= the number of vertices (intersections) in the network,
L
= the number of lines in the network,
R
= the number of regions (enclosed areas) in the network.
Euler claimed that for any network one could add the number of vertices and regions and subtract the number of lines and the total would always be 1. For example, all the networks in Figure 7 obey the rule.
Figure 7. All conceivable networks obey Eulerâs network formula.
It is possible to imagine testing this formula on a whole series of networks and if it turned out to be true on each occasion it would be tempting to assume that the formula is true for all networks. Although this might be enough evidence for a scientific theory, it is inadequate to justify a mathematical theorem. The only way to show that the formula works for every possible network is to construct a foolproof argument, which is exactly what Euler did.
Euler began by considering the simplest network of all, i.e. a single vertex as shown in Figure 8 . For this network the formula is clearly true: there is one vertex, and no lines or regions, and therefore
Euler then considered what would happen if he added something to this simplest of all networks. Any extension to the single vertex requires the addition of a line. The line can either connect the existing vertex to itself, or it can connect the existing vertex to a new vertex.
First, let us look at connecting the vertex to itself with this additional line. As shown in Figure 8 , when the line is added, this also results in a new region. Therefore the network formula remains true because the extra region (+1) cancels the extra line (â1). If further lines are added in this way the network formula will still remain true because each new line will create a new region.
Figure 8. Euler proved his network formula by showing that it was true for
Similar Books
