Đề bài

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?

Lời giải chi tiết

Đồ thị đầy đủ \({K_n}\) có \(n{\rm{ }} \ge {\rm{ }}2,{\rm{ }}n\; \in \;\mathbb{N}.\)Đồ thị đầy đủ \({K_n}\)  là đồ thị liên thông.Mỗi đỉnh của \({K_n}\)  đều có bậc là n – 1.

+) Theo định lí Euler, K_n­ có chu trình Euler khi K_n liên thông (đã thỏa mãn) và mọi đỉnh của K_n đều có bậc chẵn, điều này có nghĩa để K_n­ có một chu trình Euler thì n – 1 phải là số chẵn hay n phải là số lẻ, tức là \(n{\rm{ }} = {\rm{ }}2k{\rm{ }} + {\rm{ }}1{\rm{ }}(k\; \in \;{\mathbb{N}^*}).\) Vậy với \(\;n{\rm{ }} = {\rm{ }}2k{\rm{ }} + {\rm{ }}1{\rm{ }}(k\; \in \;{\mathbb{N}^*})\) thì đồ thị đầy đủ K_n có một chu trình Euler.

+) Đồ thị K_n có một đường đi Euler từ A đến B khi và chỉ khi K_n liên thông và mọi đỉnh của K_n đều có bậc chẵn, chỉ trừ A và B có bậc lẻ. Mà mọi đỉnh của K_n đều có bậc là n – 1, nghĩa là mọi đỉnh của K_n đều có bậc chẵn hoặc đều có bậc lẻ.

- Với n = 2, ta có K₂🃏 có 2 đỉnh đều có bậc là 1 (là bậc lẻ) nên ta có đường đi Euler từ đỉnh này qua đỉnh còn lại.

- Với n > 2, n ∈ ℕ^* thì mọi đỉnh của K_n đều có bậc cùng chẵn hoặc cùng lẻ lớn hơn 2, do đó không thỏa mãn điều kiện để K_n có đường đi Euler.

Vậy đồ thị đầy đủ K_n­ có một đường đi Euler khi n = 2.