✨Đị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 $\backslash 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\_1v\_2v\_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 .

Gọi tất cả các đỉnh liền kề với $v$l là $v${i1}, v{i2},..., v{i_t} (với và $t$≥$\backslash frac\{n\}\{2\}$). Dễ thấy 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\_1v\_2v\_3...v$lv{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\_1v$2...v{ij-1}v{i_j}vlv{l-1}...v_{ij+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$≥$\backslash frac\{n\}\{2\}$, nên suy ra bậc của $v\_\{l+1\}$ nhỏ hơn $\backslash 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.