Câu hỏi 7
Cho đồ thị đơn $G$ có $3n^2$ đỉnh, với số nguyên $n\ge2$. Bậc mỗi đỉnh không quá $4n$, có ít nhất một đỉnh bậc 1, và giữa hai đỉnh bất kỳ có một đường đi độ dài không quá 3. Chứng minh số cạnh nhỏ nhất của $G$ bằng $\frac72n^2-\frac32n$.
Chú thích. Một đường đi độ dài $k$ giữa hai đỉnh phân biệt $u,v$ là dãy $u=v_0,v_1,\dots,v_k=v$, trong đó $v_i,v_{i+1}$ kề nhau với $i=0,1,\dots,k-1$. (Đề của Leng Gangsong)
Chú thích. Một đường đi độ dài $k$ giữa hai đỉnh phân biệt $u,v$ là dãy $u=v_0,v_1,\dots,v_k=v$, trong đó $v_i,v_{i+1}$ kề nhau với $i=0,1,\dots,k-1$. (Đề của Leng Gangsong)