The Bug River runs through the downtown area of Konigsberg. It has two tributaries, one is called the new river, and the other is called the old river. After the two rivers meet in the city center, they become a mainstream, called the big river. Between the old and new rivers and the big river, there is an island area, which is the bustling area of the city. The whole city is divided into four areas: north, east, south and island, which are connected by seven bridges.
People have lived on rivers and islands for a long time and traveled between seven bridges. Someone asked this question: can you walk seven bridges at a time, and each bridge is only allowed to cross once? After the question was put forward, many people were very interested and tried it one after another, but for a long time, it was never solved. Finally, people had to throw this problem to Euler, an academician of the Russian Academy of Sciences, and ask him to help solve it.
In A.D. 1737, Euler received the "Seven Bridges Problem", when he was thirty years old. He thought, let's try it first. He started from the middle island area, arrived at the north area through the 1 bridge, returned to the island area from the No.2 bridge, entered the east area through the No.4 bridge, reached the south area through the No.5 bridge, and then returned to the island area through the No.6 bridge ... Now only the No.3 and No.7 bridges have not passed. Obviously, the only way to cross the third bridge from the island area is to cross the first bridge, the second bridge or the fourth bridge, but all three bridges have passed. This move failed. Euler again at a side:
Island northeast island south island north
This way of walking still doesn't work, because Bridge 5 hasn't crossed yet.
Euler can't even try a few tricks. This question is really not simple! He calculated that there were many moves, including * * *.
7×6×5×4×3×2× 1=5040 (species)
Boy, if we try this method and this method, when will we get the answer? He thought: you can't just try, you have to think of other ways.
Clever Euler finally came up with a clever way. He used A to represent the island area, B, C and D to represent the north, east and west areas respectively, and the seven bridges were represented by arcs or straight lines. In this way, the problem of seven bridges has been transformed into a problem in several branches of graph theory, that is, whether the above graphics can be drawn without a repetition.
Euler concentrated on studying this figure and found that at every point in the middle, there was always a line drawn to that point and another line drawn from that point. That is, except the starting point and the ending point, the line passing through the middle point must be even. Like the picture above, because it is a closed curve, the lines passing through all points must be even. In this picture, there are five lines passing through point A, three lines passing through point B, point C and point D, and none of them are even, which means that no matter from that point, there is always a line that has not been drawn, that is, a bridge has not arrived. Euler finally proved that it was impossible not to walk seven bridges at a time.
The talented Euler summed up 5040 different moves with only one step of proof, which shows the power of mathematics!