June 4, 2024 – T's Lab

Bài này là phần tiếp theo của bài https://nttuan.org/2023/09/01/graph02/

Cho đồ thị $\displaystyle G=(V,E).$ Bậc của một đỉnh $\displaystyle v\in G,$ ký hiệu $\displaystyle \deg_G(v)$ hoặc $\displaystyle \deg (v),$ là số đỉnh của $\displaystyle G$ kề với $\displaystyle v.$ Đỉnh có bậc bằng $\displaystyle 0$ được gọi là đỉnh cô lập. Đỉnh có bậc bằng $1$ được gọi là lá. Nếu mọi đỉnh của $\displaystyle G$ đều có bậc $\displaystyle k$ thì ta nói $\displaystyle G$ là $\displaystyle k-$ đều.

Định lý 1. Trong mỗi đồ thị có cấp lớn hơn $\displaystyle 1$ , tồn tại ít nhất hai đỉnh có cùng bậc.

Chứng minh. Gọi $\displaystyle n$ là cấp của đồ thị. Bậc của mỗi đỉnh của đồ thị là một số tự nhiên bé hơn $\displaystyle n$ . Vì vậy, nếu các đỉnh của đồ thị có bậc đôi một khác nhau thì có đỉnh cô lập và có đỉnh kề với mọi đỉnh khác, vô lý. $\Box$

Định lý 2. Với mỗi đồ thị $\displaystyle G=(V,E),$ ta có

$\displaystyle \displaystyle \sum_{v\in V}\deg (v)=2\mid E\mid.$

Chứng minh. Khi ta cộng tất cả bậc của các đỉnh, ta đã đếm mỗi cạnh đúng hai lần, một cho mỗi đầu mút của nó. $\Box$

Hệ quả. Số đỉnh bậc lẻ trong một đồ thị là số chẵn.

Ví dụ 1. Có đồ thị với dãy bậc của đỉnh như sau hay không?

(a) $\displaystyle 3,2,2,2.$

(b) $\displaystyle 3,3,2,2.$

Hướng dẫn. Ý đầu là không vì tổng bậc phải chẵn, ý thứ hai là có. Ý thứ ba là không, vì nếu có thì khi xét hai đỉnh bậc $\displaystyle 4,$ có ít nhất $\displaystyle 6$ cạnh đến các đỉnh bậc $\displaystyle 1,$ vô lý. $\Box$

Vào năm 1960, Paul Erdos và Tibor Gallai đã tìm được kết quả sau:

Định lý 3 (Erdos-Gallai). Dãy số nguyên không âm $\displaystyle d_1\geq d_2\geq\ldots \geq d_n$ là dãy bậc của một đồ thị trên $\displaystyle n$ đỉnh khi và chỉ khi $\displaystyle \sum d_i$ chẵn và

$\displaystyle \sum_{i=1}^kd_i\leq k(k-1)+\sum_{i=k+1}^n\min\{d_i,k\},\quad \forall k=\overline{1,n}.$

Ví dụ 2. Cho một tập hợp $\displaystyle S$ gồm $\displaystyle 100$ điểm trong mặt phẳng sao cho khoảng cách giữa hai điểm bất kỳ trong $\displaystyle S$ không bé hơn $\displaystyle 1.$ Chứng minh rằng có không nhiều hơn $\displaystyle 300$ cặp điểm (không kể thứ tự) mà khoảng cách giữa hai điểm trong mỗi cặp bằng $\displaystyle 1.$

Hướng dẫn. Xét đồ thị $\displaystyle G$ trên $\displaystyle S$ được xác định như sau: Tập con $\displaystyle \{A,B\}$ của $\displaystyle S$ là một cạnh của $\displaystyle G$ khi và chỉ khi $\displaystyle AB=1.$ Vì $\displaystyle \deg (v)\leq 6$ với mọi $\displaystyle v\in S$ , nên $\displaystyle \mid E(G)\mid \leq 1/2\times 6\times 100=300$ . $\Box$

Ví dụ 3. Cho một lớp học có số học sinh là số chẵn. Chứng minh rằng tồn tại hai học sinh trong lớp có số người quen chung trong lớp là số chẵn.

Lời giải. Xét đồ thị $\displaystyle G$ trên tập hợp $\displaystyle V$ các học sinh trong lớp được xác định như sau: với hai đỉnh $\displaystyle a$ và $\displaystyle b$ của $\displaystyle G,$ có một cạnh nối $\displaystyle a$ và $\displaystyle b$ khi $\displaystyle a$ và $\displaystyle b$ quen nhau. Giả sử ngược lại rằng với mỗi $\displaystyle a$ và $\displaystyle b$ phân biệt thuộc $\displaystyle V,$ $\displaystyle \mid N(a)\cap N(b)\mid$ là số lẻ. Nói riêng, mỗi hai đỉnh có ít nhất một láng giềng chung.

Nhận xét. Mọi đỉnh của $\displaystyle G$ đều có bậc chẵn.

Chứng minh. Xét một đỉnh $\displaystyle x$ bất kỳ và xem $\displaystyle N(x)$ như đồ thị con cảm sinh của $\displaystyle G.$ Ta thấy $\displaystyle \sum_{y\in N(x)}\deg_{N(x)}(y)$ là số chẵn và mỗi số hạng là lẻ, suy ra $\mid N(x)\mid$ là số chẵn. $\Box$

Bây giờ cố định một đỉnh $\displaystyle x$ bất kỳ của $\displaystyle G.$ Đặt $\displaystyle X=V\setminus (N(x)\cup \{x\}).$ Khi đó $\displaystyle X$ có số phần tử lẻ. Ta quan tâm đến số $\displaystyle \alpha$ các cạnh có một đầu mút thuộc $\displaystyle X$ đầu mút kia thuộc $\displaystyle N(x)$ theo hai cách. Nếu chọn đầu mút thuộc $\displaystyle X$ trước thì ta thấy $\displaystyle \alpha$ là số lẻ, trong khi nếu chọn đầu mút thuộc $\displaystyle N(x)$ trước thì ta thấy $\displaystyle \alpha$ là số chẵn (theo nhận xét), vô lý. $\Box$