如何证明任意一个有偶数个顶点的图，一定存在两个点拥有偶数个共同邻居？ 第1页
1
constantine-85-33 网友的相关建议:
反设任意两点公共邻居奇数，考虑下图，A点的邻居集合为紫色部分，注意到由反证假设紫色子图内每点度数为奇数，故有紫色子图共偶数个点(否则度数求和非偶)，于是这实际推出任意点的度数都是偶数
那么再考虑任意B点到余下蓝色区域的边，必为偶数条，而我们考虑蓝色区域中任意C点到紫色区域的边数，必为奇数（由于C与A的公共邻居奇数），再考虑蓝色区域中的点数，为（偶数-偶数-1）是奇数。
于是从两方面考虑蓝色与紫色区域之间的边数的奇偶性即得
yifanjing 网友的相关建议:
写一下看到这个问题时我的第一反应的解法。
我们假设图 有偶数个顶点，任意两个顶点都有奇数个共同邻居。我们不妨假设图 的每个顶点都有偶数个邻居（否则我们可以将这个点的邻居和非邻居交换，可以验证图的其他性质不变）。
假设 是这个图的邻接矩阵。于是在 中， ，其中 是全 矩阵， 是单位矩阵。特别的， 是满秩的。
计 为包含每个点的邻居集的集合。对任意某个点的邻居集 ，记 为其indicator向量（即 中对应这个点的一行）。由于满秩，存在不全为零的 使得 其中 是全 向量。
对于任意 ，我们有
,
根据 的任意性且 不全为零，这与 为偶数矛盾。
ch-nick-15 网友的相关建议:
这题碰巧刚遇到过
1
相关话题
学了数学变秃了却没有变强，这正常吗？送数学系男生尺子合适吗？
工程数学四阶行列式有什么技巧算法吗？
是否可以用积分证明球面三角形的面积为 S＝A＋B＋C－π？
如何通俗易懂地解释遗传算法？有什么例子？
你做过的最难的题是什么？
数学家面对复杂的数学算式时，还能把它和直观的概念联系在一起吗？
怎么理解 Yang-Baxter 方程？
如何提升线性代数的计算（行列变换）能力？
为什么能够研究高维几何?
前一个讨论
为什么说哲学是学科之母？
相关的话题
学数学专业是一种什么体验？有什么途径可以补齐自己数学知识的短板?
如何看待人教版教材疑似出现低级错误，用爱因斯坦相对论证明勾股定理？
你认为一个游戏的黄金游玩时长有多久？
复几何和双曲几何有什么联系？
什么具体的理论／问题／让你对数学（本科以上）提起了真正的兴趣（motivation）？
数学方面的能力该怎么培养？
数学需要回归简美贴近大众吗？
如何看待乌克兰数学家康斯坦丁·奥尔梅佐夫自杀?
网上常能见到的一段 JS 随机数生成算法如下，为什么用 9301, 49297, 233280 这三个数字做基数？
2019新课标1数学概率大题中的一个递推公式如何的出？
高中生如何自学相对论和几何？
我自认为自己证明了0可以作为除数，若是如此将会有哪些改变？
已知映射f：N→N（其中N是正整数集），问以下三条是否可以相容？
计算根号下1+根号下1+根号下1......等于多少？
如何正确理解群论中的同态基本定理？
如果微积分是中国人发明的，那现在的数学符号会是什么样子？
怎样用非数学语言讲解贝叶斯定理（Bayes's theorem）？
连分式近似怎么操作？
该如何学好数学分析？
为什么部分大一学生认为线性代数听不懂？
该函数的最小值是多少?应该怎么解？思路是什么？
忽然不想做数学了，觉着自己智商很低。？
中国数学博士的基础课明明上得比美国的多，为什么学术水平和基础还是美国好呢？
数学课有江湖吗？
迹的几何意义是什么？
数学有什么意义？
如何反驳如下说法: 1不是无穷大，且若正整数n不是无穷大，则n+1不是无穷大，所以无穷大不存在？
该如何学好数学分析？
有理数域加减乘除都是封闭的，那为什么部分无理数可以表示为有理数加减后的无穷级数呢？