Nếu đề bài chỉ là tìm [imath]k[/imath] thì như sau:
Bài toán đưa về tìm [imath]k[/imath] là số cạnh nhỏ nhất của đồ thị [imath]n[/imath] đỉnh sao cho đồ thị liên thông.
Ta chứng minh bằng quy nạp rằng [imath]k=n-1[/imath]. (1)
Thật vậy với [imath]n=3[/imath] ta thấy [imath]k=2[/imath].
Giả sử (1) đúng tới [imath]n=i \geq 3[/imath], tức số cạnh nhỏ nhất để đồ thị [imath]i[/imath] đỉnh liên thông là [imath]i-1[/imath].
Giả sử [imath]k \leq i-1[/imath].
Khi đó xét đồ thị [imath]G[/imath] [imath]i+1[/imath] đỉnh và [imath]k[/imath] cạnh liên thông.
Ta có [imath]\sum _{v \in V} d(v)=2|E|=2k \leq 2i-2[/imath] nên [imath]\dfrac{\sum _{v \in V} d(v)}{|V|} \leq \dfrac{2i-2}{i+1}<2[/imath]
Từ đó tồn tại đỉnh [imath]a \in V[/imath] sao cho [imath]d(a)=1[/imath]. Xóa điểm [imath]a[/imath] và cạnh chứa đỉnh [imath]a[/imath] ta được đồ thị [imath]G'[/imath] mới có [imath]|V|=i[/imath] và [imath]|E|=k-1[/imath].
Khi đó [imath]k-1 \leq i-2<i-1[/imath] và [imath]G'[/imath] vẫn liên thông nên mâu thuẫn với giả thiết quy nạp.
Suy ra [imath]k \geq i[/imath]. Nhận thấy tồn tại đồ thị [imath]|V|=i+1,|E|=i[/imath] liên thông (đồ thị có 1 đường đi duy nhất)
Từ đó (1) đúng với [imath]n=i+1[/imath]. Theo giả thiết quy nạp ta có đpcm.
Nếu còn thắc mắc chỗ nào bạn hãy trả lời dưới topic này để được hỗ trợ nhé. Chúc bạn học tốt ^^
Ngoài ra, bạn tham khảo kiến thức tại topic này nha
Một số bài toán về phương trình hàm
[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
