Lời giải: Lập luận về bậc của Euler (1736)

Euler thay mỗi vùng đất bằng một đỉnh và mỗi cây cầu bằng một cạnh nối hai vùng đất mà nó liên kết, biến bản đồ thành một đồ thị $G = (V, E)$ với $|V| = 4$ đỉnh và $|E| = 7$ cạnh. Một hành trình đi qua mỗi cầu đúng một lần trở thành một hành trình trong $G$ sử dụng mỗi cạnh đúng một lần — ngày nay gọi là đường đi Euler.

Thành phố Königsberg (nay là Kaliningrad, trên sông Pregel) gồm hai hòn đảo và hai bờ sông nối với nhau bằng bảy cây cầu. Cư dân thành phố tranh luận liệu có thể đi qua mỗi cầu đúng một lần hay không; Leonhard Euler nghe về câu đố này, và trong một bài báo ngắn trình bày trước Viện Hàn lâm Saint Petersburg năm 1736, ông nhận ra rằng hình dạng chính xác của đường phố và cầu không quan trọng — chỉ có kiểu liên kết giữa các vùng đất qua từng cầu mới quyết định câu trả lời (Biggs, Lloyd & Wilson 1976, Ch. 1).

Phép chuyển từ địa lý sang đồ thị $G$ này là bước đầu tiên thiết yếu: mọi bước sau đều làm việc với bức tranh trừu tượng gồm dấu chấm và đường thẳng, và lập luận tiếp theo sẽ áp dụng cho bất kỳ cách bố trí cầu nào theo kiểu này, không riêng gì Königsberg.