如何证明任意一个有偶数个顶点的图，一定存在两个点拥有偶数个共同邻居？ 第1页
1
constantine-85-33 网友的相关建议:
反设任意两点公共邻居奇数，考虑下图，A点的邻居集合为紫色部分，注意到由反证假设紫色子图内每点度数为奇数，故有紫色子图共偶数个点(否则度数求和非偶)，于是这实际推出任意点的度数都是偶数
那么再考虑任意B点到余下蓝色区域的边，必为偶数条，而我们考虑蓝色区域中任意C点到紫色区域的边数，必为奇数（由于C与A的公共邻居奇数），再考虑蓝色区域中的点数，为（偶数-偶数-1）是奇数。
于是从两方面考虑蓝色与紫色区域之间的边数的奇偶性即得
yifanjing 网友的相关建议:
写一下看到这个问题时我的第一反应的解法。
我们假设图 有偶数个顶点，任意两个顶点都有奇数个共同邻居。我们不妨假设图 的每个顶点都有偶数个邻居（否则我们可以将这个点的邻居和非邻居交换，可以验证图的其他性质不变）。
假设 是这个图的邻接矩阵。于是在 中， ，其中 是全 矩阵， 是单位矩阵。特别的， 是满秩的。
计 为包含每个点的邻居集的集合。对任意某个点的邻居集 ，记 为其indicator向量（即 中对应这个点的一行）。由于满秩，存在不全为零的 使得 其中 是全 向量。
对于任意 ，我们有
,
根据 的任意性且 不全为零，这与 为偶数矛盾。
ch-nick-15 网友的相关建议:
这题碰巧刚遇到过
1
相关话题
如何看待中科大 26 岁教授陈杲攻克数学复微分几何领域世界难题？如何用简单易懂的例子解释隐马尔可夫模型？
为什么不能说 20℃ 是 10℃ 的两倍？
你无意中发现过哪些图灵完全的系统？
负数有没有阶乘，0 的阶乘为什么是 1？
物理学常量（例如光速）把量纲去除（如果有的话）都是有理数还是无理数？
有哪些美丽或神奇的理科公式？
牛顿在数学方面有多牛？
数学只有初二水平的大学生如何回头补基础？
五年级孩子过于喜欢数学怎么办？
前一个讨论
为什么说哲学是学科之母？
相关的话题
蜈蚣博弈（Centipede Game）在现实中都有哪些应用？从1分钟图上起笔递归至月线级别走势，这个工作量有多大吗？
N个互异数随机组成的数组的逆序数的分布公式是什么？
你认为一个游戏的黄金游玩时长有多久？
如何用数学知识解答「在进行社区大规模核酸检测时，分成几人一组进行混检效率最高」？
如何算出这个求和式子结果等于 (2n)!!/(2n+1)!! ？
为什么 e^(iπ) + 1 = 0？
在一块边长为a的大正方形中，任意地挖掉一块各边平行或垂直于大正方形的边长为a/2的小正方形?
如何看待中国数学竞赛落败引网民狂欢？
有没有反三角函数的「和差角公式」？
Alice 和 Bob 各有一个 0-9 的数，他们怎样能在不暴露自己数的前提下知道双方数字是否相同？
Γ(x+1)在x=0处如何泰勒展开？
哪些伟大的数学家没有自己的传人或后代的？
数学能力是不是会退化？
如何判断这个习题中的数列是否收敛？
导数 dy/dx 是不是一个整体符号？
逃离丧尸包围的游戏，你能否逃生？
数学物理方程怎么那么难？
James Simons 退出数学学术界转从对冲基金是否为数学界的损失？
博弈论+图论，博士有哪些方向可以选择？
在一段高速公路上，30分钟之内见到汽车经过的概率是95%，那么，在10分钟内见到汽车经过的概率是多少？
同样是社会主义，为什么苏联能从20世纪后半叶至解体前培养出那么多数学大师，中国却不能？
这个世界到底是离散的还是连续的？
三个蛋挞，分别是紫薯的、提子的、黄桃的，有 80% 的把握第一个是紫薯的，有 80% 的把握最后一个是黄桃的，中间的那个是提子的概率是多大？
一个教授逻辑学的教授，有三个非常聪明的学生，怎么猜数字的？
如何理解主成分分析中的协方差矩阵的特征值的几何含义？
我希望中国举办一个更有分量的奥数天才赛，出一些很难的题目和各种猜想，可以花一年解题，吃住在考场可以吗？
小学2年级学生能掌握微积分吗？
高等数学到底有什么用，为什么大学要学？
负数与负数相乘为什么会得正？