Diễn Đàn MathScope - Xem bài viết đơn

sieunhanbachtang · 09-04-2019, 01:21 AM

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

09-04-2019, 01:21 AM	#2
sieunhanbachtang +Thành Viên+ Tham gia ngày: Oct 2018 Bài gởi: 28 Thanks: 14 Thanked 2 Times in 2 Posts	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