如何证明任意一个有偶数个顶点的图，一定存在两个点拥有偶数个共同邻居？ 第1页
1
constantine-85-33 网友的相关建议:
反设任意两点公共邻居奇数，考虑下图，A点的邻居集合为紫色部分，注意到由反证假设紫色子图内每点度数为奇数，故有紫色子图共偶数个点(否则度数求和非偶)，于是这实际推出任意点的度数都是偶数
那么再考虑任意B点到余下蓝色区域的边，必为偶数条，而我们考虑蓝色区域中任意C点到紫色区域的边数，必为奇数（由于C与A的公共邻居奇数），再考虑蓝色区域中的点数，为（偶数-偶数-1）是奇数。
于是从两方面考虑蓝色与紫色区域之间的边数的奇偶性即得
yifanjing 网友的相关建议:
写一下看到这个问题时我的第一反应的解法。
我们假设图 有偶数个顶点，任意两个顶点都有奇数个共同邻居。我们不妨假设图 的每个顶点都有偶数个邻居（否则我们可以将这个点的邻居和非邻居交换，可以验证图的其他性质不变）。
假设 是这个图的邻接矩阵。于是在 中， ，其中 是全 矩阵， 是单位矩阵。特别的， 是满秩的。
计 为包含每个点的邻居集的集合。对任意某个点的邻居集 ，记 为其indicator向量（即 中对应这个点的一行）。由于满秩，存在不全为零的 使得 其中 是全 向量。
对于任意 ，我们有
,
根据 的任意性且 不全为零，这与 为偶数矛盾。
ch-nick-15 网友的相关建议:
这题碰巧刚遇到过
1
相关话题
数学符号是不是在一定程度上阻碍了数学的发展？一元微分理论中，为什么 d(dy/dx)/dx=d^2y/(dx)^2 ？
数学是中国人擅长的学科吗？为什么？
若1+1=2，则雪是白色的，这是真命题吗？
财险精算师如何为男士开发出一款“早泄险”？
卡尔曼滤波器是如何运用于多传感器融合的？
如果一个圆的半径无限大，那它还是一个圆吗？
数学是人类独有的吗?
x^4+y^4+z^4+w^4=a^4有正整数解吗？
家人们，帮我看看这个极限?
前一个讨论
为什么说哲学是学科之母？
相关的话题
(a+b)!/(a!b!) 的结果一定是整数吗？如果是，如何证明？数学究竟是真实存在的，亦或是人类精神的产物？
数学好的人是如何找解题思路的？
请问扩展欧拉定理（扩展欧拉定理！不是欧拉定理！）有什么比较简洁易懂的证明方式吗？
勾股定理：x²＋y²=R²，是不是可以认为直角三角形是特殊的圆？
一个合格的理工大学毕业生回到三个世纪前，能对当时的数学物理等方面的水平产生多大的影响？
如何评价一些数学大佬在推导过程中的「我们不难发现…」、「显然有…」、「易得…」等语言?
数列 2，4，6，7，8…… 后面的数字是什么？
如何直观地理解群论？
数学系学渣怎么写毕业论文呢？
哪些数学命题可以用复数优雅地证明？
世界上是不是不存在完美的圆？
本人高中生，对数学很感兴趣，求推荐一下大学数学应该看的书和方法？
如何在理论上解释「四色定理」？
莱布尼兹发明的微积分符号比牛顿的好在啥地方？
如何评价 2021 年「华为杯」中国研究生数学建模竞赛？
数学中，f'(x) 和 (f(x))' 到底有什么区别？
身份证号不会用完吗？
勾股定理：x²＋y²=R²，是不是可以认为直角三角形是特殊的圆？
黎曼猜想和哥德巴赫猜想有什么联系？
123456789怎样运算等于1？
数学中，有哪些方程和思想让你体会到了美感？
如何证明内积形式的施瓦茨不等式？
如何评价丘成桐表态「重视基础科学别停留在口头」？那应该怎么重视呢？
如何证明这个关于ζ(5)的等式？
几乎处处收敛和依测度收敛的区别是什么呢？
关于传染病的数学模型有哪些？
请问数学里组合数的对称性不用公式推导应怎样理解？
古中国对比西方古典时期在数学、冶金、哲学、建筑学、自然科学等方面真的全面落后吗？
能解释下怎么从这个有向图生成如图的集合链？（数字电路并行全入度拓扑排序优化算法）？