题目

离散数学图论的一证明题：若n阶无向简单图是自补图,则n≡ 0(mod=4)或n≡ 1(mod4)

提问时间：2020-10-20

答案

n阶无向简单图有n(n-1)/2条边,它是自补图,则它与其补图的边数相同,所以n(n-1)/2是偶数,所以n(n-1)能够被4整除.
n除以4的余数只能是0,1,2,3.若余数为0,则n是4的倍数,n=4k,此时n(n-1)能够被4整除.若余数为1,则n=4k+1,n(n-1)也能被4整除.若余数为2,则n=4k+2,n(n-1)不能被4整除.若余数为3,则n=4k+3,n(n-1)也不能被4整除.
综上,n除以4的余数只能是0或1,即n≡ 0(mod=4)或n≡ 1(mod4).