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] |