Hai hòn đảo, hai bờ, bảy cây cầu. Đếm số cầu trên mỗi bờ cho 3, 3, 3 và 5, và các bậc cộng lại thành 3 + 3 + 3 + 5 = 14 (liên kết thứ nhất; liên kết thứ ba thu được cũng số 14 ấy dưới dạng 3 × 3 + 5, cách nhóm nhanh nhất). Một nửa tổng đó là số cây cầu — liên kết thứ hai chia cho 7 — và quan hệ này không riêng gì tấm bản đồ này: mỗi cây cầu đóng góp vào hai bờ, nên tổng các bậc phải bằng hai lần số cạnh. Liên kết thứ tư, 4 × 3/2 = 6, là số cặp mảnh đất có thể nối với nhau, và có bảy cây cầu để đặt vào sáu cặp; nghĩa là ít nhất một cặp mảnh đất được nối bằng hai cây cầu thay vì một.
Lập luận của Euler như sau: một chuyến đi qua mỗi cây cầu đúng một lần buộc phải ra vào theo từng cặp ở mỗi mảnh đất mà nó đi qua, nên mọi đỉnh được dùng làm điểm dừng đều có bậc chẵn; chỉ đỉnh đầu và đỉnh cuối của chuyến đi là được miễn, và chúng chỉ có hai. Königsberg có bốn đỉnh lẻ, nghĩa là không tồn tại chuyến đi thuộc loại đòi hỏi, và chứng minh đã hoàn tất trước khi bất kỳ ai đo đạc một con sông. Đó là lý do bài báo được xem là định lý đầu tiên của lý thuyết đồ thị chứ không phải lời giải một câu đố: khoảng cách, hình dạng các bờ sông và bề rộng của dòng Pregel đều không liên quan, và Euler nói điều đó bằng cách đặt bài toán vào hình học của vị trí thay vì hình học của độ lớn. Hai trong bảy cây cầu bị phá năm 1944 và không bao giờ được dựng lại, nên ngày nay chuyện chỉ còn là chuyện du lịch; số học ở đây liên quan tới tấm bản đồ được gửi cho Euler năm 1735.
Đáp án
14
Cách đọc
Tổng của bốn bậc. Liên kết thứ hai chia đôi nó thành bảy cây cầu, thứ ba cộng theo một cách khác, thứ tư đếm các cặp mảnh đất.
Nguồn
Leonhard Euler, 'Solutio problematis ad geometriam situs pertinentis', 1736, the founding paper of graph theory; the Königsberg bridges on the Pregel were seven in Euler's map, two of which were destroyed in 1944 and not rebuilt
Giải trong máy tính
Các liên kết này mở đúng máy tính với các con số của bài toán đã nhập sẵn. Dòng bên trên là những gì màn hình phải hiện — hãy tự kiểm tra.