Mở rộng của định lý Dirac

Định lý Ore: Nếu đồ thị vô hướng G=(V,E) có số đỉnh là $n \ge 3$ và $deg(u)+deg(v) \ge n$ thỏa mãn cho mọi cặp đỉnh không kề nhau u và v của G, thì G là đồ thị Hamilton.

Chứng minh.

Giả sử định lý không đúng và G=(V, E) có cỡ cực đại cấp n thỏa mãn các điều kiện của Định lý nhưng không là đồ thị Hamilton. Dễ thấy rằng thêm một cạnh bất kỳ vào một đồ thị có những tính chất chỉ ra trong định lý sẽ tạo ra một đồ thị cũng có những tính chất ấy. Vì G là đồ thị không là Hamilton cấp n có cỡ cực đại thỏa mãn các điều kiện , nên đồ thị nhận được khi thêm vào G một cạnh bất kì nối hai đỉnh không kề nhau trong G là đồ thị có chu trình Hamilton cạnh thêm đó. Suy ra hai đỉnh bất kỳ không kề nhau trong G được nối với nhau bằng một đường Hamilton

Vì G không là đồ thị Hamilton nên G khác đồ thị đầy đủ $K_n$. Do đó tồn tại hai đỉnh không kề nhau trong G, chẳng hạn $v_1$ và $v_n$. Theo khẳng định vừa chứng minh ở đoạn trên tồn tại trong G đường Hamilton nối $v_1$ với $v_n$ chẳng hạn $v_1v_2..v_n$.

Kí hiệu các đỉnh kề với $v_1$ bằng $v_{i_1},v_{i_2},..v_{i_k}$ trong đó k là bậc của đỉnh $v_1$ và $2=i_1<i_2<..<i_k$. Hiền nhiên là $v_n$ không thể kề với một đỉnh nào của G dạng $v_{i_j-1}$ bởi vì khi đó G sẽ có chu trình Hamilton là $v_1v_2..v_{i_j-1}v_nv_{n-1}..v_{i_j}v_1$.

Do đó ký hiệu $N(v_1)=\begin{Bmatrix} v_{i_j} \in V|j=1,2,..k \end{Bmatrix}$ và $N*(v_n)=\begin{Bmatrix} v_{i+1} \in V | v_i \ne v_n, \begin{Bmatrix} v_i,v_n \end{Bmatrix} \in E \end{Bmatrix}$

Thì $N(v_1) \cap N^*(v_n)$ là rỗng.

Vì thế: $n \le deg(v_1)+deg(v_n) = k+(n-1-k)=n-1$ (mâu thuẫn)

Như vậy ta có điều phải chứng minh.

Có thể thấy rằng định lý Dirac  này là hệ quả của định lý Ore do:

nếu có hai đỉnh trong đồ thị không kề nhau bất kì u và v trong G ta có $deg(u)+deg(v) \ge n/2+n/2=n$ áp dụng định lý Ore ta có điều phải chứng minh.