Đồ thị đầy đủ có hướng 2 mà u

[chemthan]

Cho đồ thị $n$ đỉnh. Giữa $2$ đỉnh bất kỳ có $1$ cạnh có hướng được tô bởi $1$ trong $2$ màu xanh hoặc đỏ. Chứng minh rằng tồn tại $1$ đỉnh mà bất kỳ đỉnh nào khác cũng có thể đi tới đỉnh này bằng các con đường có cùng màu.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[sieunhanbachtang]

Ta sử dụng quy nạp theo số đỉnh $n$
Với $n=1,2$ hiển nhiên đúng
Giả sử đúng với $n$, ta chứng minh với $n+1$ đỉnh $A_1, A_2,...,A_{n+1}$ tồn tại đỉnh thỏa mãn.
Theo quy nạp trong $A_1,A_2,...,A_n$ tồn tại đỉnh mà $n-1$ đỉnh còn lại có đường đơn sắc tới nó, giả sử là $A_1$
Theo quy nạp trong $A_2,...,A_n,A_{n+1}$ tồn tại đỉnh mà $n-1$ đỉnh còn lại có đường đơn sắc tới nó, giả sử là $A_{n+1}$
Nếu $A_1\rightarrow A_{n+1}$ thì $A_{n+1}$ là đỉnh thỏa mãn, ngược lại thì $A_1$ là đỉnh thỏa mãn
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]