MathNet 2008-part-03 — 165 bài (EN–VI) Câu hỏi 127

Cho một đồ thị (vô hướng, không có khuyên) có $2n$ đỉnh và $2n(n-1)$ cạnh, $n \gt 1$. Chứng minh rằng có thể tô đỏ một số đỉnh và cạnh của đồ thị sao cho mỗi cạnh đỏ nối các đỉnh đỏ và mỗi đỉnh đỏ thuộc đúng $n$ cạnh đỏ.