Worked solution: Euler's degree argument (1736)

Step 2 of 6: Count the bridges meeting each landmass

In plain words

Now that each landmass is just a dot, count how many bridge-lines touch each dot — this count is called the dot's degree. If you imagine standing on a landmass and looking at every bridge leading away from it, the degree simply tells you how many choices you have for your next step.

\deg(A) = 5, \quad \deg(B) = \deg(C) = \deg(D) = 3

Detailed analysis

The degree of a vertex is the number of edges incident to it. Reading the degrees off the historical bridge layout: the central island $A$ (Kneiphof) has $5$ bridges, and each of the other three landmasses $B, C, D$ has $3$ .

Euler's own diagram, reproduced in Biggs, Lloyd & Wilson (1976, Ch. 1), labels the two riverbanks and two islands and lists the seven bridges one by one; adding up how many of those bridges touch each landmass gives exactly the degrees above, and the total $5 + 3 + 3 + 3 = 14$ will matter in the next step.

Terms in this step

Degree of a vertex: The number of edges attached to a vertex $v$ , written $\deg(v)$ ; in this graph it is simply the number of bridges touching a landmass.

Knowledge used in this step

Graphs, degree, and paths