证明一个自补图一定有4K或4K+1个结点

发布时间:2024-05-15 11:30 发布:上海旅游网

问题描述:

如题,谁知道啊?给个比较详细的证明过程,谢谢了

问题解答:

G和G补的和是n阶完全图,且G和G补同构,所以n阶完全图的边数n(n-1)/2是偶数
简单的数论就可以知道如果n=4k+2或4k+3的话n(n-1)/2是奇数.完全图如果边数是奇数就无法被分为两个完全同构的互补的图。(首先边数就不满足相等了)因此n=4k或者4k+1就是必要条件了。证毕。

热点新闻