如何证明任意一个有偶数个顶点的图，一定存在两个点拥有偶数个共同邻居？ 第1页
1
constantine-85-33 网友的相关建议:
反设任意两点公共邻居奇数，考虑下图，A点的邻居集合为紫色部分，注意到由反证假设紫色子图内每点度数为奇数，故有紫色子图共偶数个点(否则度数求和非偶)，于是这实际推出任意点的度数都是偶数
那么再考虑任意B点到余下蓝色区域的边，必为偶数条，而我们考虑蓝色区域中任意C点到紫色区域的边数，必为奇数（由于C与A的公共邻居奇数），再考虑蓝色区域中的点数，为（偶数-偶数-1）是奇数。
于是从两方面考虑蓝色与紫色区域之间的边数的奇偶性即得
yifanjing 网友的相关建议:
写一下看到这个问题时我的第一反应的解法。
我们假设图 有偶数个顶点，任意两个顶点都有奇数个共同邻居。我们不妨假设图 的每个顶点都有偶数个邻居（否则我们可以将这个点的邻居和非邻居交换，可以验证图的其他性质不变）。
假设 是这个图的邻接矩阵。于是在 中， ，其中 是全 矩阵， 是单位矩阵。特别的， 是满秩的。
计 为包含每个点的邻居集的集合。对任意某个点的邻居集 ，记 为其indicator向量（即 中对应这个点的一行）。由于满秩，存在不全为零的 使得 其中 是全 向量。
对于任意 ，我们有
,
根据 的任意性且 不全为零，这与 为偶数矛盾。
ch-nick-15 网友的相关建议:
这题碰巧刚遇到过
1
相关话题
如何直观地理解阿贝尔变换恒等式？数学理论上可不可以绝对识别ps过的照片（可以作为法律证据的）？
如何比较 √2与log3（5）的大小？
有哪些手算对数的方法？
勒让德倍量公式如何证明？
为什么学了大学物理可以秒杀全部中学物理，但是数学不能?
不同国家和制度的数学PhD成才率（永久学术职位）是多少？有多大差别？
如何证明这个图的染色问题？
千年后证明费马大定理会否变成高中数学课后习题？
做科研时，都遇到过哪些灵光乍现（Eureka Moment）？
前一个讨论
为什么说哲学是学科之母？
相关的话题
如何看待中科大 26 岁教授陈杲攻克数学复微分几何领域世界难题？如何通俗地解释 230 种晶体学空间群的分类依据及其记号的含义？
数学领域做不同分支的是否隔行如隔山？
如何评价姜新文老师提出的NP=P这篇文章？
怎样理解平面向量的数量积是一个实数呢？方向乘方向怎么会有意义？
如何看待 arXiv2111.02792 对黎曼猜想的证明？
请问这个不等式（微积分怎么证明?
1+2+4+8+16+32+64+128+256+...=-1 错在哪里？
印度数学家拉马努金于 2020 年 4 月 26 日逝世一百周年，如何评价他一生的经历与贡献?
为什么我国现在在数学IMO取得第一的成绩，但杰出数学家却几乎没有？
如何找到一个10项的非负整数数列，使该数列的任意不超过3项的和不重复，并使数列的最大项最小，并证明?
1²＋2²＋……＋1005² 是奇数还是偶数？
你所在的学科或专业领域中，有哪些方面被数学知识深刻地改变了？
看看题目?那个才是对的，为什么？
五个囚犯先后从100颗绿豆中抓绿豆。抓得最多和最少的人将被处死，不能交流，可以摸出剩下绿豆的数量，谁的存活几率最大？
怎么看待考研数学老师李林「神押题」？
2.什么是赫姆霍兹定理？
2004年11月25日是感恩节，在不看万年历的情况下，怎么知道2023年的感恩节是11月几日呢？
有数学问题在哪里请教？
学习质数理论有什么实用之处？
一个具有介值性的函数是否一定存在原函数？
Gram-Schmidt 正交化多项式？
(不用答了）这个证明中的这两个红圈中的结论是怎么得出来的？
如何评价IMO（国际奥数） 2019中国队团体总分与美国并列第一，重新夺回团体桂冠？
如何算出这个求和式子结果等于 (2n)!!/(2n+1)!! ？
为什么要构造出范德蒙行列式？
这张算数入门图（一只兔子加一只兔子）里的题在算什么？
数学上激波和稀疏波的区别是什么？
高中生物中讲存在单层和双层膜细胞器，那么单双层膜怎么区分？理论依据（数学和生物学的依据最好）有哪些？
n! 和 n²，哪个更大呢？