Câu hỏi 65
Một đồ thị đơn $G$ được gọi là tô được kiểu "gần đúng" nếu ta có thể tô mỗi cạnh bằng một trong các màu xanh dương, đỏ, xanh lá và trắng sao cho
- với mỗi đỉnh $v$ bậc $3$ trong $G$, ba cạnh nhận $v$ làm đầu mút hoặc được tô bởi ba màu xanh dương, đỏ, xanh lá, hoặc cả ba cạnh đều màu trắng,
- không phải mọi cạnh đều màu trắng.
Một đồ thị liên thông $G$ có $a$ đỉnh bậc $4$, $b$ đỉnh bậc $3$ và không có đỉnh nào khác, trong đó $a$ và $b$ là các số nguyên dương. Tìm số thực $c$ nhỏ nhất sao cho mệnh đề sau đúng: "Nếu $a / b \gt c$ thì $G$ tô được kiểu gần đúng."
- với mỗi đỉnh $v$ bậc $3$ trong $G$, ba cạnh nhận $v$ làm đầu mút hoặc được tô bởi ba màu xanh dương, đỏ, xanh lá, hoặc cả ba cạnh đều màu trắng,
- không phải mọi cạnh đều màu trắng.
Một đồ thị liên thông $G$ có $a$ đỉnh bậc $4$, $b$ đỉnh bậc $3$ và không có đỉnh nào khác, trong đó $a$ và $b$ là các số nguyên dương. Tìm số thực $c$ nhỏ nhất sao cho mệnh đề sau đúng: "Nếu $a / b \gt c$ thì $G$ tô được kiểu gần đúng."