Ta mô hình hóa bài toán bằng một đồ thị đơn G=(V,E), trong đó mỗi đỉnh tương ứng với một hòn đảo và mỗi cạnh tương ứng với một cây cầu. Khi đó ∣V∣=300 và ∣E∣=m.
(1) Trước hết ta sẽ chứng minh bổ đề (định lí Euler):
Bổ đề 0.1. Một đồ thị vô hướng liên thông có chu trình Euler, tức là đi qua tất cả các cạnh đúng một lần và quay về đỉnh xuất phát khi và chỉ khi mọi đỉnh của đồ thị đều có bậc chẵn.
Chứng minh. Trước hết, giả sử tồn tại một đường đi khép kín đi qua mỗi cạnh đúng một lần. Mỗi lần đường đi đi đến một đỉnh thì nó cũng rời đỉnh đó bằng một cạnh khác; đồng thời điểm đầu cũng là điểm cuối. Vì mỗi cạnh được dùng đúng một lần nên số cạnh kề với mỗi đỉnh là chẵn. Do đó mọi đỉnh đều có bậc chẵn.
Ngược lại, giả sử mọi đỉnh có bậc chẵn và tất cả các đỉnh có bậc dương thuộc cùng một thành phần liên thông. Chọn một đỉnh v0 có bậc dương và bắt đầu đi từ v0, tại mỗi bước chọn một cạnh chưa dùng kề với đỉnh hiện tại.
Để ý ta không thể dừng tại một đỉnh v=v0. Thật vậy, mỗi lần đã đến rồi rời v thì có hai cạnh kề với v được dùng. Nếu hiện tại vừa đến v mà không còn cạnh chưa dùng để đi tiếp thì số cạnh đã dùng kề với v là lẻ, trong khi degv chẵn, vô lí. Tiếp tục đi cho đến khi không thể đi tiếp. Vì E hữu hạn nên quá trình phải dừng, và theo lập luận trên, đỉnh dừng phải là v0. Do đó ta thu được một đường đi khép kín C không lặp cạnh.
Nếu C đã chứa tất cả các cạnh thì ta có điều phải chứng minh. Nếu chưa, vì tất cả các đỉnh có bậc dương thuộc cùng một thành phần liên thông nên tồn tại một đỉnh u của C kề với một cạnh chưa dùng. Bắt đầu từ u và chỉ đi qua các cạnh chưa dùng; lập luận như trên cho ta một đường đi khép kín C′ bắt đầu và kết thúc tại u. Bổ sung thêm C′ vào C tại u, ta được một đường đi khép kín dài hơn và vẫn không lặp cạnh. Lặp lại quá trình này; vì E hữu hạn nên sau hữu hạn bước ta thu được một đường đi khép kín đi qua tất cả các cạnh đúng một lần.
Trở lại bài toán ban đầu: Vì tồn tại một đường đi khép kín đi qua mỗi cạnh đúng một lần nên theo chiều thuận của định lí Euler, mỗi đỉnh của G đều có bậc chẵn.
Vì G là đồ thị đơn có 300 đỉnh nên degv≤299 với mọi v∈V. Do degv chẵn nên degv≤298.
Theo bổ đề bắt tay, ta có 2m=∑v∈Vdegv≤300⋅298, suy ra m≤44700.
Giờ ta chỉ ra cách xây dựng thỏa mãn m=44700.
Đặt V={1,2,…,300} và lấy tất cả các cạnh của đồ thị đầy đủ trên V, ngoại trừ 150 cạnh
{i,i+150},i=1,2,…,150.
Khi đó mỗi đỉnh có bậc 298. Hơn nữa, đồ thị này liên thông. Thật vậy, nếu hai đỉnh u,v không kề nhau thì chúng là hai đầu mút của một trong 150 cạnh đã bỏ. Lấy bất kì w∈/{u,v}, khi đó cả uw và wv đều là cạnh của đồ thị, nên ta có đường đi u−w−v.
Vì mọi đỉnh đều có bậc chẵn và đồ thị liên thông nên theo định lí Euler, tồn tại một đường đi khép kín đi qua mỗi cạnh đúng một lần, và số cạnh của đồ thị là
2300⋅299−150=44700.
Vậy mmax=44700.
(2) Trước hết ta có bổ đề sau:
Bổ đề 0.2. Nếu một đồ thị G=(V,E) không chứa chu trình thì ∣E∣≤∣V∣−1.
Chứng minh. Ta quy nạp theo ∣V∣. Với ∣V∣=1 thì hiển nhiên.
Giả sử ∣V∣≥2. Ta chứng minh rằng G có một đỉnh bậc không quá 1. Thật vậy, giả sử ngược lại mọi đỉnh đều có bậc ít nhất 2. Chọn một đường đi đơn
v0v1⋯vk
có số cạnh lớn nhất. Vì degv0≥2, ngoài v1 còn có một đỉnh u kề với v0.
Nếu u∈/{v0,v1,…,vk} thì uv0v1⋯vk là đường đi đơn dài hơn, mâu thuẫn cách chọn đường đi.
Do đó u=vj với một j≥2. Khi ấy v0v1⋯vjv0 là một chu trình, cũng mâu thuẫn.
Vậy tồn tại một đỉnh v∈V có degv≤1.
Xóa đỉnh v cùng các cạnh kề với v. Đồ thị còn lại không chứa chu trình và có ∣V∣−1 đỉnh, nên theo giả thiết quy nạp có nhiều nhất ∣V∣−2 cạnh. Vì degv≤1, ta có
∣E∣≤(∣V∣−2)+1=∣V∣−1.
Bổ đề được chứng minh theo nguyên lý quy nạp.
Trở lại bài toán ban đầu: Gọi Ai là tập các đỉnh thuộc vương quốc thứ i với i∈{1,2,3,4,5}. Trước hết, nếu có một vương quốc không quản lí hòn đảo nào thì G không thể chứa chu trình nào, bởi một chu trình như vậy không đi qua hòn đảo thuộc vương quốc đó. Khi ấy theo bổ đề trên, m≤299<398, nên kết luận hiển nhiên.
Vì vậy, ta chỉ cần xét trường hợp cả 5 vương quốc đều quản lí ít nhất một hòn đảo.
Đặt ni=∣Ai∣. Khi đó ni≥1 với mọi i và n1+n2+n3+n4+n5=300.
Với mỗi i∈{1,2,3,4,5}, ta bỏ khỏi G tất cả các đỉnh thuộc Ai cùng các cạnh kề với các đỉnh đó. Gọi đồ thị còn lại là Gi và gọi mi là số cạnh của Gi.
Theo giả thiết, Gi không chứa chu trình. Thật vậy, nếu Gi chứa một chu trình thì chu trình đó cũng là một chu trình của G và không đi qua bất kì đỉnh nào thuộc Ai, tức là không đi qua hòn đảo nào của vương quốc thứ i, trái với giả thiết.
Đồ thị Gi có 300−ni đỉnh nên theo bổ đề, mi≤300−ni−1=299−ni. Cộng lại ta được
m1+m2+m3+m4+m5≤5⋅299−(n1+n2+n3+n4+n5)=1195
Xét một cạnh uv của G.
- Nếu u,v thuộc hai vương quốc khác nhau, chẳng hạn u∈Ai, v∈Aj với i=j, thì cạnh uv bị xóa khỏi Gi và Gj, còn xuất hiện trong đúng ba đồ thị Gk với k∈/{i,j}.
- Nếu u,v cùng thuộc một vương quốc Ai thì cạnh uv chỉ bị xóa khỏi Gi, nên xuất hiện trong bốn đồ thị Gk với k=i.
Vì vậy mỗi cạnh của G được tính ít nhất ba lần trong tổng m1+m2+m3+m4+m5.
Do đó 3m≤m1+m2+m3+m4+m5≤1195 hay m≤398.
Vậy tổng số cây cầu không thể vượt quá 398.
Hướng dẫn viên dẫn đoàn xuất phát từ địa điểm 
Một trò chơi được quy định như sau: xuất phát từ một điểm bất kỳ trong bảy điểm trên đi qua hết tất cả các cạnh trên hình vẽ mỗi cạnh ít nhất một lần rồi quay lại điểm xuất phát. Người chơi là người thắng cuộc nếu tổng độ dài đường đi là ngắn nhất. Tính tổng độ dài đường đi đó.
