如何证明任意一个有偶数个顶点的图，一定存在两个点拥有偶数个共同邻居？ 第1页
1
constantine-85-33 网友的相关建议:
反设任意两点公共邻居奇数，考虑下图，A点的邻居集合为紫色部分，注意到由反证假设紫色子图内每点度数为奇数，故有紫色子图共偶数个点(否则度数求和非偶)，于是这实际推出任意点的度数都是偶数
那么再考虑任意B点到余下蓝色区域的边，必为偶数条，而我们考虑蓝色区域中任意C点到紫色区域的边数，必为奇数（由于C与A的公共邻居奇数），再考虑蓝色区域中的点数，为（偶数-偶数-1）是奇数。
于是从两方面考虑蓝色与紫色区域之间的边数的奇偶性即得
yifanjing 网友的相关建议:
写一下看到这个问题时我的第一反应的解法。
我们假设图 有偶数个顶点，任意两个顶点都有奇数个共同邻居。我们不妨假设图 的每个顶点都有偶数个邻居（否则我们可以将这个点的邻居和非邻居交换，可以验证图的其他性质不变）。
假设 是这个图的邻接矩阵。于是在 中， ，其中 是全 矩阵， 是单位矩阵。特别的， 是满秩的。
计 为包含每个点的邻居集的集合。对任意某个点的邻居集 ，记 为其indicator向量（即 中对应这个点的一行）。由于满秩，存在不全为零的 使得 其中 是全 向量。
对于任意 ，我们有
,
根据 的任意性且 不全为零，这与 为偶数矛盾。
ch-nick-15 网友的相关建议:
这题碰巧刚遇到过
1
相关话题
欧氏空间到自身的局部同胚、连续、满映射，是否一定是单射？泊松分布和正态分布有什么内在联系？
如何证明树的树叶个数比度数不少于3的顶点数多？
在图像处理中，散度 div 具体的作用是什么？
圆周率是一个无理数，3.1415926…。问，能否用一个数学式子来准确表示圆周率，类似根号10？
如何证明这个Tauber定理？
有没有处处不可导的凸函数？
这道怎么求极限?
如果微积分是中国人发明的，那现在的数学符号会是什么样子？
如果1+1＝0你认为是什么原因？
前一个讨论
为什么说哲学是学科之母？
相关的话题
在微积分教材一开始直接引入 epsilon-delta 语言是否有利？勾股数有有限多组还是无限多组？
中国最难的理科高考题有哪些？
如何看待涉及悉尼大学数学系教授 Williamson 和美国国家科学基金会的学术不端事件？
什么是泊松过程？
如何看待问题「船上绵羊 26 只和山羊 10 只，问船长几岁？」？
如何将一张A4纸快速折出完美的五等份？
如下图，这个级数如何求出来呢？
你知道哪些让你怀疑智商的数学题？
数学从小就差的人在大学有机会翻身吗？
数学有什么意义？数学中的一切都是人类自己编造的吗？
你认为你所在学科最杰出的思想是什么？
三位物理学家与陶哲轩发现的特征向量全新求解公式，会给机器学习领域带来怎样的变化？
古希腊人是怎样判断根号二是无理数的？
该如何学好数学分析？
三次曲线 x³＋y³＝1 有什么几何性质？
两相邻素数的最大间距能够多大？
怎么推导或证明 e^x 的导数是自身？
虚数的现实、物理意义是什么？
图论里的图用什么软件画比较好？
√8-√2=√2，这是怎么得出来的？
有哪些看似简单却无人能解的数学猜想？
n! 和 n²，哪个更大呢？
为什么 sin(x²)+sin(y²)=1 的图像这么复杂？
欧洲有哪些统计机器学习比较强的大学或者研究院的？？
对于很多知乎大佬说的随便一个数学系的学生就能秒杀考研数学？
如何激怒一位数学爱好者？
如何用数学卖个萌？
连续的周期函数都有最小正周期吗？
怎样理解一个非常大的数？