/kloc-In the 8th century, there were seven bridges on the Pledgel River in Konigsberg (now Kaliningrad, Russia), connecting the two islands in the river with the riverbank, as shown in figure 1. Residents in the city often cross the bridge by the river, so they asked a question: Can you cross seven bridges at a time, each bridge can only cross once, and finally return to the starting point? This is the seven-bridge problem, a famous graph theory problem.

This question seems not difficult, but people still can't find the answer. Finally, this problem was mentioned by the great mathematician Euler. Euler quickly proved with profound insight that such a way of walking did not exist. Euler solved the problem in this way: since land is the joint of bridges, it is better to regard land separated by rivers as points A, B, C and D4, and express seven bridges as seven lines connecting these four points, as shown in Figure 2.

So the "Seven Bridges Problem" is equivalent to a problem of the graph drawn in Figure 3. Euler noticed that if a point has an inner edge, it must have an outer edge, so every point must have an even number of connected edges.

It takes one person to finish a stroke. Every point in Figure 3 is connected by an odd number of edges, so it is impossible to draw it with one stroke, that is to say, there is no way to cross seven bridges at once, and each bridge can only cross once.

Euler's research on "Seven Bridges" is the beginning of graph theory research, and also provides an elementary example for topology research.