2.13. Với giá trị nào của n thì đồ thị đầy đủ $K_{n}$ có một chu trình Euler? Có một đường đi Euler?
Bài Làm:
Ta có đồ thị đầy đủ $K_{n}$ có n đỉnh và bậc của mọi đỉnh là n - 1
- Theo Định lí 1, đồ thị G có chu trình Euler khi và chỉ khi đồ thị liên thông và mọi đỉnh của đồ thị đều có bậc chẵn.
Do đó để đồ thị đầy đủ $K_{n}$ có một chu trình Euler khi và chỉ khi n - 1 phải là số chẵn. Suy ra n là số lẻ.
- Theo Định lí 2, đồ thị G có đường đi Euler từ A đến B khi và chỉ khi G liên thông và mọi đỉnh của G đều có bậc chẵn, chỉ trừ A và B có bậc lẻ.
Tuy nhiên, với đồ thị đầy đủ $K_{n}$, bậc của mọi đỉnh đều là n - 1 nên nếu có hai đỉnh có bậc lẻ thì các đỉnh còn lại đều có bậc lẻ.
Do đó, đồ thị đầy đủ $K_{n}$ không có đường đi Euler với mọi n.
