Đị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 ${\frac {n}{2}}$ thì G có đường đi Hamilton.

Chứng minh

Định lý 2

Ký hiệu n đỉnh của G là $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à $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 $l=n$ thì suy ra luôn điều phải chứng minh.

Xét trường hợp $l<n$.

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

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

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

$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 $v_{l+1}$ không liền kề với các đỉnh $v_{i_{j}+1}$, với j chạy từ 1 đến t. Mà $t$≥${\frac {n}{2}}$, nên suy ra bậc của $v_{l+1}$ nhỏ hơn ${\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.