百科问答小站 logo
百科问答小站 font logo



如何证明这个图的染色问题? 第1页

  

user avatar    网友的相关建议: 
      

(反证)

如果存在一种颜色 ,使任意染成该颜色的点 ,它的邻域 至多有其他 种颜色,不妨记未出现的,与 不同的颜色为 。

注意到,对每个 ,将 的颜色由 改为 ,仍是一种合理的染色,此时只使用 种颜色,与 矛盾。


user avatar   timosky 网友的相关建议: 
      

如果某个颜色(比如颜色a)的一个点(比如点A)邻域里不包含其他所有颜色的点,也就是说至少还有一个其他颜色(比如颜色b)不与它相邻,那就把点A改成颜色b。

如果颜色a不存在“邻域里包含所有其他颜色的点”,那么如此操作,每个颜色a的点都将被改为其他颜色……而且依旧满足相邻点颜色不同。于是点色数--,矛盾了。


换句话来说就是:用最少颜色使得相邻两点颜色不同的染法,就是你所要求的这个染法……否则我们将可以使用更少的颜色实现相邻两点不同,从而导致矛盾。




  

相关话题

  给定正整数 n,将 1 拆分为 n 个互不相同的单位分数之和,不计次序,有几种拆法? 
  2018年,如何规划一条最新的《中国铁道大纪行》路线? 
  下面这个组合恒等式如何证明? 
  等比数列的任意连续三项的中间一项都是另外两项的等比中项吗? 
  如何估计这个级数? 
  如何证明以下式子? 
  学习数论图论有必要先学抽代和高代吗? 
  为什么规定 0 的阶乘为 1? 
  到底是奇数多还是偶数多? 
  数学论文的作者会意识到自己发表的结果实际上已经有人做出来过吗? 

前一个讨论
数学的所有内容都是基于一些无法证明的公理和无法定义的概念(比如集合、直线),那么数学有没有可能是假的?
下一个讨论
如何证明子集族上界?





© 2025-06-22 - tinynew.org. All Rights Reserved.
© 2025-06-22 - tinynew.org. 保留所有权利