Định lý Dirac

Trong lý thuyết đồ thị, có hai định lý được gọi là định lý Dirac (tiếng Anh: Dirac's theorem), cả hai đều được đặt theo tên nhà toán học Gabriel Andrew Dirac:

1. Cho G là một đồ thị k-liên thông (tiếng Anh: k-connected graph). Ta có thể khẳng định với mỗi tập k đỉnh bất kì trong G, thì tồn tại ít nhất một chu trình đơn trong G đi qua k đỉnh này.

2. Dirac, 1952: Cho G là một đồ thị đơn có n ≥ 3 đỉnh. Nếu mỗi đỉnh đều có bậc không nhỏ hơn ${\displaystyle {\frac {n}{2}}}$ thì G có đường đi Hamilton^[1].

Chứng minh

Định lý 2

Ký hiệu n đỉnh của G là ${\displaystyle v_{1},v_{2},v_{3},...,v_{n}}$.

Không mất tính tổng quát giả sử đường đi H dài nhất của G là ${\displaystyle v_{1}v_{2}v_{3}...v_{l}}$. H có độ dài là l. Như vậy mọi đường đi đơn của G có độ dài nhỏ hơn l+1.

Nếu ${\displaystyle l=n}$ thì suy ra luôn điều phải chứng minh.

Xét trường hợp ${\displaystyle l<n}$.

Gọi tất cả các đỉnh liền kề với ${\displaystyle v_{l}}$ là ${\displaystyle v_{i_{1}},v_{i_{2}},...,v_{i_{t}}}$ (với ${\displaystyle 0<i_{1}<i_{2}<...<i_{t}<n+1}$ và ${\displaystyle t}$≥${\displaystyle {\frac {n}{2}}}$). Dễ thấy ${\displaystyle {i_{j}}<l}$ với mọi j chạy từ 1 tới t, vì nếu tồn tại ${\displaystyle {i_{j}}>l}$, thì suy ra tồn tại đường đi có độ dài l+1:

${\displaystyle v_{1}v_{2}v_{3}...v_{l}v_{i_{j}}}$.

Nếu đỉnh ${\displaystyle v_{l+1}}$ mà liền kề với đỉnh ${\displaystyle v_{i_{j}+1}}$ thì ta sẽ tạo được đường đi có độ dài l+1:

${\displaystyle v_{1}v_{2}...v_{i_{j}-1}v_{i_{j}}v_{l}v_{l-1}...v_{i_{j}+1}v_{l+1}}$

(vô lý).

Vậy ${\displaystyle v_{l+1}}$ không liền kề với các đỉnh ${\displaystyle v_{i_{j}+1}}$, với j chạy từ 1 đến t. Mà ${\displaystyle t}$≥${\displaystyle {\frac {n}{2}}}$, nên suy ra bậc của ${\displaystyle v_{l+1}}$ nhỏ hơn ${\displaystyle {\frac {n}{2}}}$ (vô lý).

Vậy trường hợp l<n là không tồn tại.

Suy ra điều phải chứng minh.

Chú thích

1. Graham, p. 20.

Tham khảo