離散數(shù)學圖論的一證明題：若n階無向簡單圖是自補圖,則n≡ 0(mod=4)或n≡ 1(mod4)

數(shù)學人氣：769 ℃時間：2019-11-12 22:59:51

優(yōu)質(zhì)解答

n階無向簡單圖有n(n-1)/2條邊,它是自補圖,則它與其補圖的邊數(shù)相同,所以n(n-1)/2是偶數(shù),所以n(n-1)能夠被4整除.
n除以4的余數(shù)只能是0,1,2,3.若余數(shù)為0,則n是4的倍數(shù),n=4k,此時n(n-1)能夠被4整除.若余數(shù)為1,則n=4k+1,n(n-1)也能被4整除.若余數(shù)為2,則n=4k+2,n(n-1)不能被4整除.若余數(shù)為3,則n=4k+3,n(n-1)也不能被4整除.
綜上,n除以4的余數(shù)只能是0或1,即n≡ 0(mod=4)或n≡ 1(mod4).