Định lý Dirac và ứng dụng

Định lý  (Dirac 1952)

Đơn đồ thị vô hướng G với n>2 đỉnh, mỗi đỉnh có bậc không nhỏ hơn n/2 là đồ thị Hamilton.

Chứng minh:

Ký hiệu n đỉnh của G là ${\displaystyle 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à ${\displaystyle 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 ${\displaystyle l=n}$ thì suy ra luôn điều phải chứng minh.

Xét trường hợp ${\displaystyle l<n}$.

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

${\displaystyle v_{1}v_{2}v_{3}...v_{l}v_{i_{j}}}$.

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

${\displaystyle 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 ${\displaystyle v_{l+1}}$ không liền kề với các đỉnh ${\displaystyle v_{i_{j}+1}}$, với j chạy từ 1 đến t. Mà ${\displaystyle t}$≥${\displaystyle {\frac {n}{2}}}$, nên suy ra bậc của ${\displaystyle v_{l+1}}$ nhỏ hơn ${\displaystyle {\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.

Ứng dụng của nó là bài toán nổi tiếng sau:

Bài toán: Tại một hội nghị có 2n quan khách.trong đó mỗi quan khách có nhiều nhất n-1 kẻ thù.chứng minh rằng có thể xếp 2n nguời đó trên 1 vòng tròn sao cho không ai ngồi cạnh kẻ thù của mình 

Lời giải:

Ta xây dựng đồ thị G như sau:

-Đỉnh: là các điểm trong mặt phẳng hay trong không gian tương ứng với các quan khách, dùng mã số của các quan khách để ghi trên các đỉnh tương ứng.

-Cạnh: hai đỉnh được nối với nhau bằng cạnh khi và chỉnh khi hai quan khác tương ứng thuộc hai đỉnh đó không là kẻ thù của nhau.

Khi đó ta được một đồ thị G mô tả toàn bộ quan hệ giữa các quan khách. Vì đồ thị G có đúng 2n đỉnh, và mỗi đỉnh có bậc không nhỏ hơn n nên theo định lý Dirac ta có G có chu trình Halminton. Dựa vào chu trình này ta có thể xếp tất cả các quan khách thỏa mãn yêu cầu đề bài

Ngoài ra còn một cách khác để chứng minh được trích trong 

Gary Chartrand/Introductory Graph Theory

Let $P = p_1 p_2 \ldots p_k$ be the longest path in G.
If $p_1$ is adjacent to some vertex v not in P, then the path $v p_1 p_2 \ldots p_k$ would be longer than P, contradicting the choice of P.
The same argument can be made for $p_k.$
So both $p_1$ and $p_k$ are adjacent only to vertices in P.
Since $\deg(p_1) \ge \dfrac n 2$ and $p_1$ cannot be adjacent to itself, $k \ge \dfrac n 2 +1.$
Claim: There is some value of $j (1 \le j \le k)$ such that:$p_j$ is adjacent to $p_k$, and$p_{j+1}$ is adjacent to $p_1.$
Suppose that the claim is not true.
Then since all vertices adjacent to $p_1$ or $p_k$ lie on P, there must be at least $\deg(p_1)$ vertices on P not adjacent to $p_k.$
Since all the vertices adjacent to p_k and p_k itself also lie on P, the path must have at least $\deg(p_1) + \deg(p_k) + 1 \ge n+1$ vertices.
But G has only n vertices: a contradiction.

This gives a cycle $C = p_{j+1} p_{j+2} \ldots p_{k} p_j p_{j-1} \ldots p_2 p_1 p_{j+1}.$
Suppose G - C is nonempty.
Then since G is connected, there must be a vertex $v \in G-C$ adjacent to some $p_i.$
So the path from v to $p_i$ and then around C to the vertex adjacent to $p_i$ is longer than P, contradicting the definition of P.

Therefore all vertices in G are contained in C, making C a Hamilton cycle.
$\blacksquare$