作者joywilliamjo (joywilliamjoy)
看板Grad-ProbAsk
標題[理工] 台大 109電機丙 離散數學 第6題
時間Sun Jan 17 23:49:16 2021
https://imgur.com/AgO2PTe
題目在此，著色問題，雖然有看過別人的答案但還是看不太懂他寫的證明
想請問版上有比較好懂一點的證明嗎?
感恩
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.77.117.67 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1610898558.A.3FB.html
1F：→ bettyteng21: 雖然過了一年，但剛好複習到這邊就來回一下 11/28 17:01
2F：→ bettyteng21: 利用反證法，假設G中存在deg為k-2的點v，若去掉v的其 11/28 17:01
3F：→ bettyteng21: 中一邊e=(v,x)，則v的deg 變成k-3。即使和v相鄰的點 11/28 17:01
4F：→ bettyteng21: 都是不同顏色，加上v自己也只需要k-2色，和題目寫的k 11/28 17:01
5F：→ bettyteng21: 色矛盾，得證 11/28 17:01
6F：→ bettyteng21: 如果有不嚴謹的地方再麻煩大家指教 11/28 17:01