The degree of a vertex

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$

Một đường đi là một đồ thị khác rỗng $\displaystyle P=(V,E)$ với tập đỉnh $\displaystyle V$ và tập cạnh $\displaystyle E$ có dạng $\displaystyle V=\{x_0,x_1,\ldots,x_k\}\quad\quad E=\{x_0x_1,x_1,x_2,\ldots,x_{k-1}x_k\}.$ Ta nói các đỉnh $\displaystyle x_0$ và $\displaystyle x_k$ được nối với nhau bởi $\displaystyle P$ và gọi là các đầu mút của nó. Các đỉnh $\displaystyle x_1,x_2,\ldots,x_{k-1}$ được gọi là đỉnh trong của $\displaystyle P.$ Số cạnh của một đường đi được gọi là độ dài của nó. Ta thường ký hiệu đường đi bởi dãy tự nhiên các đỉnh của nó, chẳng hạn với đường đi $\displaystyle P$ như trên ta viết $\displaystyle P=x_0x_1\ldots x_k$ và nói $\displaystyle P$ là một đường đi từ $\displaystyle x_0$ đến $\displaystyle x_k.$

Nếu $\displaystyle P=x_0x_1\ldots x_k$ là một đường đi và $\displaystyle k\geq 2$ thì đồ thị với tập đỉnh $\displaystyle V=\{x_0,x_1,\ldots,x_k\}$ và tập cạnh $\displaystyle E=\{x_0x_1,x_1,x_2,\ldots,x_{k-1}x_k,x_kx_0\}$ được gọi là một chu trình. Ta thường ký hiệu chu trình này bởi dãy đỉnh $\displaystyle x_0x_1\ldots x_kx_0.$ Độ dài của một chu trình là số cạnh của nó, một chu trình độ dài $\displaystyle k$ sẽ được gọi là $\displaystyle k-$ chu trình. Một cạnh nối hai đỉnh của một chu trình nhưng không phải là một cạnh của chu trình được gọi là dây của chu trình đó.

Với một đồ thị $\displaystyle G,$ ký hiệu $\displaystyle\delta (G)=\min_{v\in G} \deg_G(v),$ và gọi nó là bậc nhỏ nhất của $\displaystyle G.$ Bằng trực giác ta thấy một đồ thị có bậc nhỏ nhất lớn thì nó có đường đi dài và chu trình dài.

Định lý 4. Cho $\displaystyle G$ là một đồ thị với $\displaystyle \delta (G)>1.$ Khi đó $\displaystyle G$ chứa một đường đi dài $\displaystyle \delta (G),$ và một chu trình có độ dài không nhỏ hơn $\displaystyle \delta (G)+1.$

Chứng minh. Gọi $\displaystyle x_0x_1\ldots x_k$ là một đường đi dài nhất của $\displaystyle G.$ Khi đó tất cả các láng giềng của $\displaystyle x_k$ phải thuộc đường đi này, suy ra $\displaystyle k\geq \deg (x_k)\geq\delta (G),$ và ta có một đường đi với độ dài $\displaystyle \delta (G).$ Lấy $\displaystyle i<k$ nhỏ nhất sao cho $\displaystyle x_i$ và $\displaystyle x_k$ kề nhau, khi đó $\displaystyle x_ix_{i+1}\ldots x_kx_i$ là một chu trình với độ dài không nhỏ hơn $\displaystyle \delta (G)+1$ . $\Box$