Đị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  thì G có đường đi Hamilton.

Chứng minh

Định lý 2 

Ký hiệu n đỉnh của G là .

Không mất tính tổng quát giả sử đường đi H dài nhất của G 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  thì suy ra luôn điều phải chứng minh.

Xét trường hợp .

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

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

(vô lý).

Vậy  không liền kề với các đỉnh , với j chạy từ 1 đến t. Mà ≥, nên suy ra bậc của  nhỏ hơn  (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

Tham khảo

Lý thuyết đồ thị
D