Câu hỏi 27
Cho $G$ là một đồ thị đơn liên thông với các đỉnh $v_1, v_2, \dots, v_{11}$ sao cho $v_1$ có bậc $2$ và các đỉnh còn lại đều có bậc $3$. Giả sử với mọi tập con $A$ gồm không quá $4$ đỉnh, tập các đỉnh không thuộc $A$ nhưng có cạnh nối với ít nhất một phần tử của $A$ có số phần tử không ít hơn số phần tử của $A$. Tìm đường kính nhỏ nhất có thể của đồ thị $G$.
*(Chú ý. Một đồ thị được gọi là liên thông nếu giữa hai đỉnh bất kỳ luôn có một đường đi. Đường kính của một đồ thị là độ dài đường đi ngắn nhất giữa hai đỉnh xa nhau nhất.)*
*(Chú ý. Một đồ thị được gọi là liên thông nếu giữa hai đỉnh bất kỳ luôn có một đường đi. Đường kính của một đồ thị là độ dài đường đi ngắn nhất giữa hai đỉnh xa nhau nhất.)*