Đị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.