Định lí 8 (Định lý (Dirac, 1952) ) Nếu G là một đơn đồ thị có $n$ đỉnh và mọi đỉnh của $G$ đều có bậc không nhỏ hơn $\frac{n}{2}$ thì $G$ là một đồ thị Hamilton.
Chứng minh Chứng minh: Định lý được chứng minh bằng phản chứng. Giả sử $G$ không có chu trình Hamilton. Ta thêm vào $G$ một số đỉnh mới và nối mỗi đỉnh mới này với mọi đỉnh của G, ta được đồ thị G’. Giả sử $k >0)$ là số tối thiểu các đỉnh cần thiết để $G’$ chứa một chu trình Hamilton. Như vậy, $G’$ có $n+k$ đỉnh.
Gọi $P$ là chu trình Hamilton $aeb ...a$ trong $G’$, trong đó $a$ và $b$ là các đỉnh của $G$, còn $y$ là một trong các đỉnh mới. Khi đó $b$ không kề với $a$, vì nếu trái lại thì ta có thể bỏ đỉnh $e$ và được chu trình $ab ...a$, mâu thuẩn với giả thiết về tính chất nhỏ nhất của $k$.
Ngoài ra, nếu $a’$ là một đỉnh kề nào đó của $a$ (khác với $e$) và $b’$ là đỉnh nối tiếp ngay $a’$ trong chu trình $P$ thì $b’$ không thể là đỉnh kề với $b$, vì nếu trái lại thì ta có thể thay $P$ bởi chu trình $aa’ ...bb’ ... a$, trong đó không có $e$, mâu thuẩn với giả thiết về tính chất nhỏ nhất của $k$.
Như vậy, với mỗi đỉnh kề với $a$, ta có một đỉnh không kề với $b$, tức là số đỉnh không kề với $b$ không thể ít hơn số đỉnh kề với $a$ (số đỉnh kề với $a$ không nhỏ hơn $\frac{n}{2} +k$). Mặt khác, theo giả thiết số đỉnh kề với $b$ cũng không nhỏ hơn $\frac{n}{2} +k$. Vì không có đỉnh nào vừa kề với b lại vừa không kề với b, nên số đỉnh của $G’$ không ít hơn $2(\frac{n}{2} +k)=n+2k$, mâu thuẫn với giả thiết là số đỉnh của G’ bằng $n+k (k>0)$. Định lý được chứng minh.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]