如何证明任意一个有偶数个顶点的图，一定存在两个点拥有偶数个共同邻居？ 第1页
1
constantine-85-33 网友的相关建议:
反设任意两点公共邻居奇数，考虑下图，A点的邻居集合为紫色部分，注意到由反证假设紫色子图内每点度数为奇数，故有紫色子图共偶数个点(否则度数求和非偶)，于是这实际推出任意点的度数都是偶数
那么再考虑任意B点到余下蓝色区域的边，必为偶数条，而我们考虑蓝色区域中任意C点到紫色区域的边数，必为奇数（由于C与A的公共邻居奇数），再考虑蓝色区域中的点数，为（偶数-偶数-1）是奇数。
于是从两方面考虑蓝色与紫色区域之间的边数的奇偶性即得
yifanjing 网友的相关建议:
写一下看到这个问题时我的第一反应的解法。
我们假设图 有偶数个顶点，任意两个顶点都有奇数个共同邻居。我们不妨假设图 的每个顶点都有偶数个邻居（否则我们可以将这个点的邻居和非邻居交换，可以验证图的其他性质不变）。
假设 是这个图的邻接矩阵。于是在 中， ，其中 是全 矩阵， 是单位矩阵。特别的， 是满秩的。
计 为包含每个点的邻居集的集合。对任意某个点的邻居集 ，记 为其indicator向量（即 中对应这个点的一行）。由于满秩，存在不全为零的 使得 其中 是全 向量。
对于任意 ，我们有
,
根据 的任意性且 不全为零，这与 为偶数矛盾。
ch-nick-15 网友的相关建议:
这题碰巧刚遇到过
1
相关话题
这个有关斐波那契数的求和怎么证明？如何证明方程 x³＋y³＝2020 没有整数解？
怎么积∫[0, 1] ln(1＋x²)/(1＋x) dx？
为什么世界上最顶尖的科学家很多是单身汉？
有没有休闲级别、能读懂的讲「群论」的书籍？
人类是否能想象出多维空间的形态？
学习数学时你能保持多长时间集中注意力？
如何理解「数学是研究数量关系与空间形式的科学」这句话里「空间形式」的含义？
正在读数学 Ph.D. 的你对想读数学 Ph.D. 的本科生有什么建议吗？
数列极限的四则运算中条件需有限次是什么意思？
前一个讨论
为什么说哲学是学科之母？
相关的话题
如何快速判断一个人的数学水平？如何证明负无穷等于正无穷？
n 座桥，连通 n+1 个岛，有多少种连法？
中国古代数学有什么成就？
n! 和 n²，哪个更大呢？
可以只控制单刀双掷开关（电键）就改变串并混联的电路最少要多少个开关？
综合除法的数学依据是什么？
假如我每次连续攻击目标所造伤害是上次次攻击的105%，我连续出拳一千次，能不能打穿坦克护甲？
如何能够快速恢复脑力？
数学本科生学一门课（比如代数几何2）到一半时失去动机不感兴趣了，应该如何决定是继续肝还是放弃掉学别的？
A 和 B 在 100 × 100 的平面空间内移动，两种情况下哪一种相遇的概率更大？
有哪些玩游戏时能使用的高等数学知识？
身份证号不会用完吗？
世界上是不是不存在完美的圆？
为什么总有一些人推荐计算机学生把重点放在高数和线代？
为什么有理数 1/49 看起来这么像是个无限不循环小数？循环节在哪里？
如何理解 Van-Kampen 定理？
将一个大于等于3的数分成三个正整数相加有多少种分法？
如何评价上海交通大学数学系不提供就业辅导&要学生走纯数学之路？
是否存在一不等于0的完全平方数，使得它成为连续质数个整数之积？
在数学中，如果推翻了一条很基础的公理，那么会造成什么后果？
矩阵乘法的本质是什么？
为什么费马大定理在数学史上的地位如此重要？
怎么看待「学数学没啥用，买菜难道还用得上微积分」的理论？
被剑桥大学 deferred entry 应该接受吗？
任意 ε＞0，a≤b＋ε 是否可推出 a≤b？
什么是动态规划（Dynamic Programming）？动态规划的意义是什么？
为什么宇宙当中的温度会有上下限？
最难的数学有多难？
关于凑微分上下限的一个小小疑问？