如何证明任意一个有偶数个顶点的图，一定存在两个点拥有偶数个共同邻居？ 第1页
1
constantine-85-33 网友的相关建议:
反设任意两点公共邻居奇数，考虑下图，A点的邻居集合为紫色部分，注意到由反证假设紫色子图内每点度数为奇数，故有紫色子图共偶数个点(否则度数求和非偶)，于是这实际推出任意点的度数都是偶数
那么再考虑任意B点到余下蓝色区域的边，必为偶数条，而我们考虑蓝色区域中任意C点到紫色区域的边数，必为奇数（由于C与A的公共邻居奇数），再考虑蓝色区域中的点数，为（偶数-偶数-1）是奇数。
于是从两方面考虑蓝色与紫色区域之间的边数的奇偶性即得
yifanjing 网友的相关建议:
写一下看到这个问题时我的第一反应的解法。
我们假设图 有偶数个顶点，任意两个顶点都有奇数个共同邻居。我们不妨假设图 的每个顶点都有偶数个邻居（否则我们可以将这个点的邻居和非邻居交换，可以验证图的其他性质不变）。
假设 是这个图的邻接矩阵。于是在 中， ，其中 是全 矩阵， 是单位矩阵。特别的， 是满秩的。
计 为包含每个点的邻居集的集合。对任意某个点的邻居集 ，记 为其indicator向量（即 中对应这个点的一行）。由于满秩，存在不全为零的 使得 其中 是全 向量。
对于任意 ，我们有
,
根据 的任意性且 不全为零，这与 为偶数矛盾。
ch-nick-15 网友的相关建议:
这题碰巧刚遇到过
1
相关话题
怎么样通俗易懂地向小学生介绍群论的思想？如何证明负无穷等于正无穷？
数学的所有内容都是基于一些无法证明的公理和无法定义的概念（比如集合、直线），那么数学有没有可能是假的？
老师说链式法则里某个 dy/dx 不能理解为 dy 除以 dx，为什么？
数学学科的很多内容无法和实际联系在一起，学这些的意义就只是培养思维逻辑吗？
若零向量没有方向，那它还是向量吗？
等比数列的任意连续三项的中间一项都是另外两项的等比中项吗？
天赋一般是不是不适合学数学？
如何评价数学家张益唐？
王茂泽宣称其破解世界著名难题「冰雹猜想」，他的证明正确吗？
前一个讨论
为什么说哲学是学科之母？
相关的话题
内测度的缺陷是什么？下列数字方块移动得到一定排列顺序的问题有解吗？
想买报纸，走了很久没有找到报亭，该换一条路还是走到底？
如何求数列sin nθ大于零的个数？
求大佬指教一道新定义数列问题如何做？
概率论和实变函数（测度论）有什么联系？
学数学的人都有哪些特有的习惯？
数学中，f'(x) 和 (f(x))' 到底有什么区别？
如何证明树的树叶个数比度数不少于3的顶点数多？
C语言指针难吗？如何看待数学大v认为指针比范畴论还难？
数学中的错误有大错和小错的区别吗？
数论问题困难性的根源是什么？
如何看待上海一城管为全球数学竞赛出题？你身边有哪些隐藏的「数学大神」？
什么样的数能同时满足「＞0」且「＜0」？
一个无向图的邻接矩阵也是个实对称矩阵，它能否运用实对称矩阵的某些特有性质实现某些运用呢？
为什么多项数学杯赛被叫停？
什么是半微分（semi-differential）？有什么几何意义吗？
请问为什么无穷个无穷小量的乘积不一定是无穷小量？
中学阶段解出一道很难的数学题和在数学研究领域做出重大突破的区别在哪？
如何看待国际数学联盟发表声明，取消在俄罗斯圣彼得堡线下举办国际数学家大会？其它国际组织会跟进吗？
如何看待靠指责别人来发泄自己的喷子？
这个数列问你证明收敛呀？
什么具体的理论／问题／让你对数学（本科以上）提起了真正的兴趣（motivation）？
相关系数和R方的关系是什么？
这里面有哪些思路算是民科思路？
研究数学是不是必须有天赋？
是否存在将中国大陆部分一分为二的铁路路线？
现代理论物理的新成果中，有没有因为使用不严格的数学最后被证明因此导致错误结果的案例？
为什么 lnx 求导是 1/x？
普通外国人算术真的很差吗？