如何证明任意一个有偶数个顶点的图，一定存在两个点拥有偶数个共同邻居？ 第1页
1
constantine-85-33 网友的相关建议:
反设任意两点公共邻居奇数，考虑下图，A点的邻居集合为紫色部分，注意到由反证假设紫色子图内每点度数为奇数，故有紫色子图共偶数个点(否则度数求和非偶)，于是这实际推出任意点的度数都是偶数
那么再考虑任意B点到余下蓝色区域的边，必为偶数条，而我们考虑蓝色区域中任意C点到紫色区域的边数，必为奇数（由于C与A的公共邻居奇数），再考虑蓝色区域中的点数，为（偶数-偶数-1）是奇数。
于是从两方面考虑蓝色与紫色区域之间的边数的奇偶性即得
yifanjing 网友的相关建议:
写一下看到这个问题时我的第一反应的解法。
我们假设图 有偶数个顶点，任意两个顶点都有奇数个共同邻居。我们不妨假设图 的每个顶点都有偶数个邻居（否则我们可以将这个点的邻居和非邻居交换，可以验证图的其他性质不变）。
假设 是这个图的邻接矩阵。于是在 中， ，其中 是全 矩阵， 是单位矩阵。特别的， 是满秩的。
计 为包含每个点的邻居集的集合。对任意某个点的邻居集 ，记 为其indicator向量（即 中对应这个点的一行）。由于满秩，存在不全为零的 使得 其中 是全 向量。
对于任意 ，我们有
,
根据 的任意性且 不全为零，这与 为偶数矛盾。
ch-nick-15 网友的相关建议:
这题碰巧刚遇到过
1
相关话题
非常硬核的数学题，大家能否解出？数学上那些根本没有任何线索提示的配凑构造技巧到底是怎样被发现的？
哪些线性代数（指一般意义上的本科一年级的课程）的难题可以用李群李代数的知识简便、优雅地做出来？
无法理解高等数学怎么办？
有没有什么可以让自己对数学感兴趣的书?
国内的数学系本科是不是代数的训练不够？
如果黎曼猜想被证否了，将会产生什么后果？
为什么我用欧拉公式得出了i=0？
负数有没有阶乘，0 的阶乘为什么是 1？
卓里奇的《数学分析》怎么样？
前一个讨论
为什么说哲学是学科之母？
相关的话题
拓扑学能解决哪些分析学无法解决的问题？n趋近于无穷时1/2 + 1/3 +...+ 1/n+1等于多少?
李煌的阶乘计算小技巧，与斯特林公式有什么区别？
1+2+4+8+16+32+64+128+256+...=-1 错在哪里？
这个级数应该怎么计算呢?求解答?
为什么井盖不做成莱洛三角形？
你对贝叶斯统计都有怎样的理解？
英国人真的连乘法口诀都不熟悉么？
正方体的体对角线垂直吗？
一条假设出来的辅助线，为什么能证明真实的结论？
学数学学到自卑怎么办？
一天做完一百道积分题是一种什么感觉？
两个相邻的质数之和（除了2与3）除二得到的值是合数，有数学证明吗？
小时候想到的一个数学问题，现在还没有想明白，可能以后会越来越不明白，有哪位大牛可以帮我解答吗？
一个凸五边形中，已知五条边边长，如何求其最大面积？
这个用什么方法呢？
以数学史的观点来看，集合论是如何成为数学基础的？
为什么不是所有函数都能用解析式表达？
图论里的图用什么软件画比较好？
小学生有必要上数奥班吗？
矩阵乘法的本质是什么？
能否彻底从代数角度定义微分和积分？
数学系为什么有那么多编程课程任务?
能否构造一个含有自己哈希或MD5等的文件？
请问这道数竞题怎么做？请大神不吝赐教？
站在一个无穷大的围棋/五子棋盘上的任意格点上，能够看到的格点都放上黑棋，黑棋占格点比例多少？
如何解释「线性回归」的含义？
如何通俗理解矩阵的秩？
莱布尼兹发明的微积分符号比牛顿的好在啥地方？
这道题怎么做?不懂？