Có một vùng biển gồm 300 hòn đảo. Người ta xây dựng $m$ cây cầu; mỗi cây cầu nối trực tiếp hai hòn đảo với nhau, và giữa hai hòn đảo có không quá một cây cầu.
(1) Tìm số lượng cây cầu $m$ lớn nhất có thể xây dựng, biết rằng tồn tại ít nhất một tuyến du lịch khép kín đi qua tất cả các cây cầu, mỗi cây cầu đúng một lần; một hòn đảo có thể được đi qua nhiều lần.
(2) Các hòn đảo được phân cho 5 vương quốc khác nhau quản lí, mỗi hòn đảo do đúng một vương quốc quản lí. Hệ thống cầu có tính chất: mọi tuyến du lịch khép kín đều phải đi qua các hòn đảo thuộc đủ cả 5 vương quốc. Hỏi tổng số cây cầu có thể vượt quá 398 hay không?

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 $v_0$ có bậc dương và bắt đầu đi từ $v_0$, 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\ne v_0$. 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 $\mathrm{deg}v$ 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à $v_0$. 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^{\prime }$ bắt đầu và kết thúc tại $u$. Bổ sung thêm $C^{\prime }$ 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 $\mathrm{deg}v\le 299$ với mọi $v\in V$. Do $\mathrm{deg}v$ chẵn nên $\mathrm{deg}v\le 298$.
Theo bổ đề bắt tay, ta có $2m={\sum }_{v\in V}\mathrm{deg}v\le 300\cdot 298$, suy ra $m\le 44700$.
Giờ ta chỉ ra cách xây dựng thỏa mãn $m=44700$.
Đặt $V=\{1,2,\dots ,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,\dots ,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\notin \{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à
$$\frac{300\cdot 299}{2}-150=44700.$$
Vậy $m_{\max }=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|\le |V|-1$.

Chứng minh. Ta quy nạp theo $|V|$. Với $|V|=1$ thì hiển nhiên.
Giả sử $|V|\ge 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
$$v_0{v}_1\cdots v_k$$
có số cạnh lớn nhất. Vì $\mathrm{deg}{v}_0\ge 2$, ngoài $v_1$ còn có một đỉnh $u$ kề với $v_0$.
Nếu $u\notin \{v_0,v_1,\dots ,v_k\}$ thì $u{v}_0{v}_1\cdots v_k$ là đường đi đơn dài hơn, mâu thuẫn cách chọn đường đi.
Do đó $u=v_j$ với một $j\ge 2$. Khi ấy $v_0{v}_1\cdots v_j{v}_0$ là một chu trình, cũng mâu thuẫn.
Vậy tồn tại một đỉnh $v\in V$ có $\mathrm{deg}v\le 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ì $\mathrm{deg}v\le 1$, ta có
$$|E|\le (|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 $A_i$ là tập các đỉnh thuộc vương quốc thứ $i$ với $i\in \{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\le 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 $n_i=|A_i|$. Khi đó $n_i\ge 1$ với mọi $i$ và $n_1+n_2+n_3+n_4+n_5=300$.
Với mỗi $i\in \{1,2,3,4,5\}$, ta bỏ khỏi $G$ tất cả các đỉnh thuộc $A_i$ cùng các cạnh kề với các đỉnh đó. Gọi đồ thị còn lại là $G_i$ và gọi $m_i$ là số cạnh của $G_i$.
Theo giả thiết, $G_i$ không chứa chu trình. Thật vậy, nếu $G_i$ 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 $A_i$, 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ị $G_i$ có $300-n_i$ đỉnh nên theo bổ đề, $m_i\le 300-n_i-1=299-n_i$. Cộng lại ta được
$$m_1+m_2+m_3+m_4+m_5\le 5\cdot 299-(n_1+n_2+n_3+n_4+n_5)=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\in A_i$, $v\in A_j$ với $i\ne j$, thì cạnh $uv$ bị xóa khỏi $G_i$ và $G_j$, còn xuất hiện trong đúng ba đồ thị $G_k$ với $k\notin \{i,j\}$.
- Nếu $u,v$ cùng thuộc một vương quốc $A_i$ thì cạnh $uv$ chỉ bị xóa khỏi $G_i$, nên xuất hiện trong bốn đồ thị $G_k$ với $k\ne i$.
Vì vậy mỗi cạnh của $G$ được tính ít nhất ba lần trong tổng $m_1+m_2+m_3+m_4+m_5$.
Do đó $3m\le m_1+m_2+m_3+m_4+m_5\le 1195$ hay $m\le 398$.
Vậy tổng số cây cầu không thể vượt quá 398.