Câu hỏi 157
Tìm số dương nhỏ nhất $0 \lt c \lt 1$ thỏa mãn tính chất sau:
Mọi đồ thị đơn, không chứa tam giác, có $n \ge 3$ đỉnh, trong đó bậc của mọi đỉnh lớn hơn hẳn $cn$, đều là đồ thị hai phía.
**Giải thích:** Đồ thị đơn là đồ thị vô hướng không có khuyên và không có cạnh bội. Bậc của một đỉnh là số cạnh nối với đỉnh đó. Tam giác là một chu trình độ dài ba. Một đồ thị là đồ thị hai phía nếu có thể tô các đỉnh bằng hai màu sao cho không có cạnh nào nối hai đỉnh cùng màu.
Mọi đồ thị đơn, không chứa tam giác, có $n \ge 3$ đỉnh, trong đó bậc của mọi đỉnh lớn hơn hẳn $cn$, đều là đồ thị hai phía.
**Giải thích:** Đồ thị đơn là đồ thị vô hướng không có khuyên và không có cạnh bội. Bậc của một đỉnh là số cạnh nối với đỉnh đó. Tam giác là một chu trình độ dài ba. Một đồ thị là đồ thị hai phía nếu có thể tô các đỉnh bằng hai màu sao cho không có cạnh nào nối hai đỉnh cùng màu.