如何证明任意一个有偶数个顶点的图，一定存在两个点拥有偶数个共同邻居？ 第1页
1
constantine-85-33 网友的相关建议:
反设任意两点公共邻居奇数，考虑下图，A点的邻居集合为紫色部分，注意到由反证假设紫色子图内每点度数为奇数，故有紫色子图共偶数个点(否则度数求和非偶)，于是这实际推出任意点的度数都是偶数
那么再考虑任意B点到余下蓝色区域的边，必为偶数条，而我们考虑蓝色区域中任意C点到紫色区域的边数，必为奇数（由于C与A的公共邻居奇数），再考虑蓝色区域中的点数，为（偶数-偶数-1）是奇数。
于是从两方面考虑蓝色与紫色区域之间的边数的奇偶性即得
yifanjing 网友的相关建议:
写一下看到这个问题时我的第一反应的解法。
我们假设图 有偶数个顶点，任意两个顶点都有奇数个共同邻居。我们不妨假设图 的每个顶点都有偶数个邻居（否则我们可以将这个点的邻居和非邻居交换，可以验证图的其他性质不变）。
假设 是这个图的邻接矩阵。于是在 中， ，其中 是全 矩阵， 是单位矩阵。特别的， 是满秩的。
计 为包含每个点的邻居集的集合。对任意某个点的邻居集 ，记 为其indicator向量（即 中对应这个点的一行）。由于满秩，存在不全为零的 使得 其中 是全 向量。
对于任意 ，我们有
,
根据 的任意性且 不全为零，这与 为偶数矛盾。
ch-nick-15 网友的相关建议:
这题碰巧刚遇到过
1
相关话题
自然科学和唯心主义是矛盾的吗？已知映射f：N→N（其中N是正整数集），问以下三条是否可以相容？
如何高贵冷艳地写数学分析证明题？
e 是怎么算的？
为什么许多人建议本科学数学，研究生阶段转金融或者计算机？学数学的发展方向只有纯数学计算机以及金融吗？
算子代数是一门怎样的数学分支？学习算子代数需要怎样的基础？
为什么数学每次考完自己在想就能把不会的想出来?
1×0=0是因为0乘任何数都是0还是因为1乘任何数都是等于那个数？
图论里的图用什么软件画比较好？
为什么 Mathematica 不能显示积分过程，即使它能算出最终结果？
前一个讨论
为什么说哲学是学科之母？
相关的话题
以「维数」为自变量的函数怎样表示和画图象？有没有可能把 π 或 e 等无理数当成 1，这样就能使许多定理显而易见？
如何评价微信朋友圈文章：记者调查：疯狂的学而思，疯狂的校外培训！？
三位物理学家与陶哲轩发现的特征向量全新求解公式，会给机器学习领域带来怎样的变化？
微分符号 dx、dy 表示什么含义？
十个人赛跑第一名和一百人赛跑的第十名，谁厉害？
为什么数量级"皮可"很少使用？
沃罗诺伊图（Voronoi Diagram，也称作Dirichlet tessellation，狄利克雷镶嵌 ）是怎样的？
怎么求x的x次方n阶导？
圆锥曲线中过任一顶点作相垂直的直线，过直线与曲线交点的直线过定点，这有什么射影几何的背景吗？
高次韦达定理是什么？如何证明？
确定不做学术，应不应该读纯数学的博士？
Γ（i）怎么算？
下面圆周率的这3个无穷级数公式怎么证明？
如何计算投掷多个骰子得到某个给定总点数的概率？
为什么「函数」叫做「函数」？
如何评价 2021 阿里巴巴数学竞赛决赛试题？
若 f(f(x))=x²+1，则 f(1) 为多少？
七个小朋友，只能切四刀，怎么把三个苹果均分？
为什么对球的体积公式求导就是球的面积公式?
如何更深入理解物理意义或概念？
人们专门弄了一个自然对数函数的底数 e，是为什么？
一段文字的包含的信息量能不能衡量？
是否存在仅在一点可导且该点导数不为0的函数？
若 π 被证明是有理数会对世界有何影响？
为什么不能计算两次哈希，以及在什么情况下不能计算两次哈希？
直线可不可以看做是半径无限大的圆？
北大数学系田刚的学问到底怎么样？
并非所有数学硕博都能从事科研，那么多数人继续读数学的理由为何？
不规则四边形内如何获得面积最大的椭圆？