如何证明任意一个有偶数个顶点的图，一定存在两个点拥有偶数个共同邻居？ 第1页
1
constantine-85-33 网友的相关建议:
反设任意两点公共邻居奇数，考虑下图，A点的邻居集合为紫色部分，注意到由反证假设紫色子图内每点度数为奇数，故有紫色子图共偶数个点(否则度数求和非偶)，于是这实际推出任意点的度数都是偶数
那么再考虑任意B点到余下蓝色区域的边，必为偶数条，而我们考虑蓝色区域中任意C点到紫色区域的边数，必为奇数（由于C与A的公共邻居奇数），再考虑蓝色区域中的点数，为（偶数-偶数-1）是奇数。
于是从两方面考虑蓝色与紫色区域之间的边数的奇偶性即得
yifanjing 网友的相关建议:
写一下看到这个问题时我的第一反应的解法。
我们假设图 有偶数个顶点，任意两个顶点都有奇数个共同邻居。我们不妨假设图 的每个顶点都有偶数个邻居（否则我们可以将这个点的邻居和非邻居交换，可以验证图的其他性质不变）。
假设 是这个图的邻接矩阵。于是在 中， ，其中 是全 矩阵， 是单位矩阵。特别的， 是满秩的。
计 为包含每个点的邻居集的集合。对任意某个点的邻居集 ，记 为其indicator向量（即 中对应这个点的一行）。由于满秩，存在不全为零的 使得 其中 是全 向量。
对于任意 ，我们有
,
根据 的任意性且 不全为零，这与 为偶数矛盾。
ch-nick-15 网友的相关建议:
这题碰巧刚遇到过
1
相关话题
如何解决这个函数极限的证明问题？如何简明地解释曲率（curvature）？
一个无向图的邻接矩阵也是个实对称矩阵，它能否运用实对称矩阵的某些特有性质实现某些运用呢？
教育部将研究珠算文化进小学，珠算有无必要恢复？该怎样进行传承？
如何计算一局三国杀所进行的回合数的数学期望？
救命，现在我是考研阶段，在自习室看见一个男生?
无穷等于无穷吗？
如何证明这道有关叉乘的解析几何题？
有限个人，任意两个人有且只有1个公共朋友，那么一定存在1个人是所有人的朋友，这是什么数学问题?
请问该如何证明？
前一个讨论
为什么说哲学是学科之母？
相关的话题
站在一个无穷大的围棋/五子棋盘上的任意格点上，能够看到的格点都放上黑棋，黑棋占格点比例多少？人类可探索的数学会不会因为证明长过人类脑容量而穷尽？
如何理解分形的维度？
这道排列组合该如何思考？
代数几何是不是被神化了？
从零开始学数学，有谁知道从何处入手，谢谢？
现在的人工智能是否走上了数学的极端？
为什么有的数学定理看起来很显然，证明起来却很复杂？
数学系大二如何弥补大一的差基础？
如何评价安徽大学 2019~2020 第一学期高等数学期末考试？
如何用最短的距离走过北京所有线路的地铁？
0 的 0 次方等于 1 吗？怎么证明？
同样是社会主义，为什么苏联能从20世纪后半叶至解体前培养出那么多数学大师，中国却不能？
这个极限要如何计算？
怎么在不公布证明的情况下让世人相信我证明了「哥猜」?
如果一个圆的半径无限大，那它还是一个圆吗？
外国人怎么算乘法？外国没有九九乘法表吗？
高中生对哥德巴赫猜想的证明有哪些错误？
学数学有什么好处？我们为什么要学数学？
这个题有没有不用圆函数做的方法？
如何证明这个数列$$a_{n}=sum_{i=1}^{n}(-1)^{⌊ix⌋}$$无界？
如何证明如下积分等式？
如何证明任意一个有偶数个顶点的图，一定存在两个点拥有偶数个共同邻居？
怎样更好地理解并记忆泰勒展开式？
空间中有多于一个的同种（比如都是正电荷）点电荷，如何说明此时一定有一点电场强度为0？
Fabrice Bellard 是个什么水平的程序员？
实变、泛函、抽代、拓扑，哪几门对于非纯数专业更加有用？
高一怎么恶补数学？
请问贝祖定理（裴蜀定理）除了用辗转相除法还能怎么证?
这个积分问题怎么做？