如何证明任意一个有偶数个顶点的图，一定存在两个点拥有偶数个共同邻居？ 第1页
1
constantine-85-33 网友的相关建议:
反设任意两点公共邻居奇数，考虑下图，A点的邻居集合为紫色部分，注意到由反证假设紫色子图内每点度数为奇数，故有紫色子图共偶数个点(否则度数求和非偶)，于是这实际推出任意点的度数都是偶数
那么再考虑任意B点到余下蓝色区域的边，必为偶数条，而我们考虑蓝色区域中任意C点到紫色区域的边数，必为奇数（由于C与A的公共邻居奇数），再考虑蓝色区域中的点数，为（偶数-偶数-1）是奇数。
于是从两方面考虑蓝色与紫色区域之间的边数的奇偶性即得
yifanjing 网友的相关建议:
写一下看到这个问题时我的第一反应的解法。
我们假设图 有偶数个顶点，任意两个顶点都有奇数个共同邻居。我们不妨假设图 的每个顶点都有偶数个邻居（否则我们可以将这个点的邻居和非邻居交换，可以验证图的其他性质不变）。
假设 是这个图的邻接矩阵。于是在 中， ，其中 是全 矩阵， 是单位矩阵。特别的， 是满秩的。
计 为包含每个点的邻居集的集合。对任意某个点的邻居集 ，记 为其indicator向量（即 中对应这个点的一行）。由于满秩，存在不全为零的 使得 其中 是全 向量。
对于任意 ，我们有
,
根据 的任意性且 不全为零，这与 为偶数矛盾。
ch-nick-15 网友的相关建议:
这题碰巧刚遇到过
1
相关话题
X[X]=10，其中[]表示取整，如何求解？语言和数学，哪个产生早？
财险精算师如何为男士开发出一款“早泄险”？
数学中为什么要定义各种空间？
如何从数学角度证明魔方复原存在必可解策略？
数学中有哪些条件看似很弱却能推出很强的定理的例子？
数学需要回归简美贴近大众吗？
收敛的序列是否存在单调的子序列（不要求严格单调）？
三进制为何比二进制更好？
天赋一般是不是不适合学数学？
前一个讨论
为什么说哲学是学科之母？
相关的话题
数学是中国人擅长的学科吗？为什么？如何证明存在 1000 个连续的正整数中恰好有五个素数？
中国的物理学、数学在未来一段时间内有望跻身世界领先水平，或者说能够成为世界的一个重要数学或物理中心吗？
有哪些美丽或神奇的理科公式？
人是如何做黑盒优化的？
在一个小城市怎么在没有接受过竞赛培训的前提下竞赛数学〔已解决〕？
求助！有木有大神可以教一下我，这种高次幂如何快速简便运算，谢谢！？
为何诺贝尔奖得主大多白发苍苍，但规定得主年龄必须在四十岁以下的菲尔兹奖是数学界的最高荣誉之一？
如何编程判断一个数是否是质数？
高考数学最后一题可以有多难？
｛mr+n！ | m∈Z，n∈N｝是否在R上稠密？
数学思维与工程思维的区别与联系是什么？
比较高深的数学在经济学有哪些运用相当漂亮？
让数学家来做高考数学试卷，他们能考满分吗？
如何计算一局三国杀所进行的回合数的数学期望？
数学家和物理学家思考方式是什么？
三角函数到底是怎么发展来的？
有什么免费软件可以替代几何画板？
这张图中能数出多少个三角形？
如何评价2021年第三届阿里巴巴全球数学竞赛？
高中数学学那么多三角函数公式到底有什么用？
如何求出图中数列的通项公式？
为什么数列可以用不动点法，到底表示什么意思啊？
为什么n维欧式空间中的单位球面（n-1 sphere）的表面积和体积，在 n 趋于 ∞ 时，都趋于0？
为什么 1-1+1-1+1-1…=0.5？
你见过哪些让你叹为观止的物理和数学问题的证明或计算方法（包括简单粗暴的数量级估算）？
如何从傅里叶逆变换推出下面这个公式？
为什么有的人长时间学习也没有取到效果？
不知道想下面描述的一样理解数列极限和收敛对不对，有什么需要改进的地方吗？
如何证明下面这个式子 ?