作者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/cn.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