Câu hỏi 56
Cho $G$ là một đồ thị có $n$ đỉnh. Một cạnh $e$ của $G$ được gọi là ngõ cụt nếu có thể phân hoạch (tập đỉnh của) $G$ thành hai tập $A$ và $B$ sao cho:
- Có nhiều nhất $2023$ cạnh của $G$ có một đầu mút thuộc $A$ và một đầu mút thuộc $B$.
- Cạnh $e$ có một đầu mút thuộc $A$ và đầu mút còn lại thuộc $B$.
Chứng minh rằng có nhiều nhất $2023(n-1)$ ngõ cụt.
- Có nhiều nhất $2023$ cạnh của $G$ có một đầu mút thuộc $A$ và một đầu mút thuộc $B$.
- Cạnh $e$ có một đầu mút thuộc $A$ và đầu mút còn lại thuộc $B$.
Chứng minh rằng có nhiều nhất $2023(n-1)$ ngõ cụt.