如何证明任意一个有偶数个顶点的图，一定存在两个点拥有偶数个共同邻居？ 第1页
1
constantine-85-33 网友的相关建议:
反设任意两点公共邻居奇数，考虑下图，A点的邻居集合为紫色部分，注意到由反证假设紫色子图内每点度数为奇数，故有紫色子图共偶数个点(否则度数求和非偶)，于是这实际推出任意点的度数都是偶数
那么再考虑任意B点到余下蓝色区域的边，必为偶数条，而我们考虑蓝色区域中任意C点到紫色区域的边数，必为奇数（由于C与A的公共邻居奇数），再考虑蓝色区域中的点数，为（偶数-偶数-1）是奇数。
于是从两方面考虑蓝色与紫色区域之间的边数的奇偶性即得
yifanjing 网友的相关建议:
写一下看到这个问题时我的第一反应的解法。
我们假设图 有偶数个顶点，任意两个顶点都有奇数个共同邻居。我们不妨假设图 的每个顶点都有偶数个邻居（否则我们可以将这个点的邻居和非邻居交换，可以验证图的其他性质不变）。
假设 是这个图的邻接矩阵。于是在 中， ，其中 是全 矩阵， 是单位矩阵。特别的， 是满秩的。
计 为包含每个点的邻居集的集合。对任意某个点的邻居集 ，记 为其indicator向量（即 中对应这个点的一行）。由于满秩，存在不全为零的 使得 其中 是全 向量。
对于任意 ，我们有
,
根据 的任意性且 不全为零，这与 为偶数矛盾。
ch-nick-15 网友的相关建议:
这题碰巧刚遇到过
1
相关话题
想读数学系，南开大学、同济大学和南京大学哪所比较好？''余数定理''可以用什么简单通俗的语言解释吗?
初中数学考19分还有救吗？
计算 2 的 64 次方有什么特殊技巧？
概率论中，为什么XY独立，X²Y²也独立？
二维世界真的可能存在吗？如果存在，如何去理解它？
如果你有很多枚鸡蛋，和一个n层高的楼，你想知道鸡蛋的抗摔能力。如何在消耗蛋数与实验速度之间找到最优解？
高次韦达定理是什么？如何证明？
对于任意既约分数，都可以分解成有限个不同奇数的倒数和吗？
轮子为什么不设计成莱洛三角形?
前一个讨论
为什么说哲学是学科之母？
相关的话题
黎曼 ζ 函数为什么要那么解析延拓？为什么人类想象不出四维的空间？
怎么做2022贺年题？
如何证明下面的数学分析问题？
对 n × n 网格图，从左下角走到右上角的边不重复路径（即左下角到右上角的迹）有多少种？
蝴蝶定理有多少种证法？
有哪些数学竞赛生才听得懂的笑话?
数学系大二如何弥补大一的差基础？
如果可以从头重新翻译，你会换掉哪些不太好的科学名词译名？
不会数学情绪崩溃怎么办？
有哪些数学上的定理让你感觉「这不显然吗，这还用证明」？
为什么中国人数理化学科成绩似乎秒杀外国人，但世界相关的（出名的）顶级的科学家几乎全是外国的？
你有没有什么天赋逐渐丧失的经历？
数学角度看，按照电影《动物世界》的赌徒游戏规则，如何才能赢得游戏胜利？
为什么欧几里得在《几何原本》中的第四公设要设定所有的直角都相等？
复数范围内，一个数的整数次方是不是永远只有一个值？以及如何证明一个数的无理数次方对应无穷个值？
圆锥体的体积公式是怎么推导出来的？
你觉得文科和理科的本质区别是什么？
包含所有各项不大于n的n元正整数列且长度最小的序列有多少个？
数学的魅力是什么？
迹的几何意义是什么？
如果一个圆的度数是361°世界会有什么影响？
最大似然估计和最小二乘法怎么理解？
为什么不科学的东西，也能够解决问题？
「羊车门」经典概率题中不换门选中车的概率是多少？
如何简单清晰地解释哥德尔不完备定理？
James Simons 退出数学学术界转从对冲基金是否为数学界的损失？
能否把数学竞赛变得更有观赏性？
对于多元线性回归，如何证明任一自变量的系数等同于忽略其他变量后一元线性回归的系数？
公民身份号码有可能是素数吗？