cạnh liên thuộc với hai đỉnh u và v, hoặc cũng nói là cạnh e nối đỉnh u và đỉnh v, đồng thời các đỉnh u và v sẽ được gọi là các đỉnh đầu của cạnh (u,v). Để có thể biết có bao nhiêu cạnh liên thuộc với một đỉnh , ta đưa vào định nghĩa sau : Định nghĩa 2. Ta gọi bậc của đỉnh v trong đồ thị vô hướnglà số cạnh liên thuộc với nó ta sẽ kí hiệu là deg(v). b c d a f e g Hình 1. Đồ thị vô hướng Thí dụ . Xét đồ thị cho trong hình 1,. | cạnh liên thuộc với hai đỉnh u và v hoặc cũng nói là cạnh e nối đỉnh u và đỉnh v đồng thời các đỉnh u và v sẽ được gọi là các đỉnh đầu của cạnh u v . Để có thể biết có bao nhiêu cạnh liên thuộc với một đỉnh ta đưa vào định nghĩa sau Định nghĩa 2. Ta gọi bậc của đỉnh v trong đồ thị vô hướnglà số cạnh liên thuộc với nó ta sẽ kí hiệu là deg v . d b c a f e g Hình 1. Đồ thị vô hướng Thí dụ . Xét đồ thị cho trong hình 1 ta có deg a 1 deg b 4 deg c 4 deg f 3 deg d 1 deg e 3 deg g 0. Đỉnh bậc 0 gọi là đỉnh cô lập đỉnh bậc 1 được gọi là đỉnh treo .Trong ví dụ trên đỉnh g là đỉnh cô lập a và d là các đỉnh treo. Bậc của đỉnh có tính chất sau SVTH Nguyễn Công Hiếu_SBD 0041 - Trang 9 - Định lý 1. Giả sử G V E là đồ thị vô hướng với m cạnh . Khi đó 2m ỵ deg v v e V Chứng minh. Rõ ràng trong mỗi cạnh e u v được tính một lần trong deg u và một lần trong deg v . Từ đó suy ra tổng tất cả các bậc của các đỉnh bằng hai lần số cạnh Thí dụ 2. Đồ thị với n đỉnh và mỗi đỉnh có bậc là 6 có bao nhiêu cạnh Giải Theo định lý 1 ta có 2m đó suy ra số cạnh của đồ thị là 3n. Hệ quả. Trong đồ thị vô hướng số đỉnh bậc lẻ nghĩa là có bậc là số lẻ là một số chẵn. Chứng minh. Thực vậy gọi O và U tương ứng là tập đỉnh bậc lẻ và tập đỉnh bậc chẵn của đồ thị ta có 2m deg v deg v deg v SVTH Nguyễn Công HiếuSBD 0041 - Trang 10 v e V v e O v e U Do deg v là chẵnvới v là đỉnh trong U nên tổng thứ hai trong vế phải ở trên là số đó suy ra tổng thứ nhất chính là tổng bậc của các đỉnh bậc lẻ cũng phải là số chẵn do tất cả các số hạng của nó là số lẻ nên tổng này phải gồm một số chẵn các số vậy số đỉnh bậclẻ phải là số chẵn. Ta xét các thuật ngữ tương tự cho đồ thị có hướng. Định nghĩa e u v là cung của đồ thị có hướng G thì ta nói hai đỉnh u và vlà kề nhau và nói cung u v nối đỉnh u với đỉnh v hoặc cũng nói cung này là đi ra khỏi đỉnh u và đi vào đỉnh v. Đinh u v sẽ được gọi là đỉnh đầu cuối của cung u v . Tương tự như khái niệm bậc đối với đồ thị có hướng ta có khái niệm bán bậc ra
