cobk54

Cho graph $G$ (link dưới) có $16$ đỉnh: $0$, $1$, $2$,..., $15$ được xếp theo thứ tự lần lượt trên đường tròn. Ta định nghĩa khoảng cách giữa $2$ đỉnh bất kỳ $x$, $y$ trên $G$ là $d(x,y) = \left | {x-y} \right|$, và $2$ đỉnh đó được nối với nhau bởi $1$ cạnh có độ dài $d(x,y)$ khi và chỉ khi $d(x,y)$ bằng $1$ hoặc $6$ hoặc là $8$.

Không mất tính tổng quát, ta xem đỉnh $0$ là gốc (root) của $G$. Hỏi $G$ có thể tồn tại $5$ cây bao trùm (spanning tree) đôi một độc lập hay ko? Ở đây $2$ cây bao trùm được gọi là độc lập nếu: Đối với một đỉnh $v$ bất kỳ khác $0$ của G, path $0-v$ trên $2$ cây đó là độc lập, $($$2$ path là độc lập nếu chúng ko có đỉnh nào chung ngoại trừ $0$ và $v$$)$.

Link to $G$: https://drive.google...dit?usp=sharing

P/s: mọi thắc mắc các bạn cứ comment nhiệt tình, mình đang cần ý tưởng để đi, bí quá