如何证明任意一个有偶数个顶点的图，一定存在两个点拥有偶数个共同邻居？ 第1页
1
constantine-85-33 网友的相关建议:
反设任意两点公共邻居奇数，考虑下图，A点的邻居集合为紫色部分，注意到由反证假设紫色子图内每点度数为奇数，故有紫色子图共偶数个点(否则度数求和非偶)，于是这实际推出任意点的度数都是偶数
那么再考虑任意B点到余下蓝色区域的边，必为偶数条，而我们考虑蓝色区域中任意C点到紫色区域的边数，必为奇数（由于C与A的公共邻居奇数），再考虑蓝色区域中的点数，为（偶数-偶数-1）是奇数。
于是从两方面考虑蓝色与紫色区域之间的边数的奇偶性即得
yifanjing 网友的相关建议:
写一下看到这个问题时我的第一反应的解法。
我们假设图 有偶数个顶点，任意两个顶点都有奇数个共同邻居。我们不妨假设图 的每个顶点都有偶数个邻居（否则我们可以将这个点的邻居和非邻居交换，可以验证图的其他性质不变）。
假设 是这个图的邻接矩阵。于是在 中， ，其中 是全 矩阵， 是单位矩阵。特别的， 是满秩的。
计 为包含每个点的邻居集的集合。对任意某个点的邻居集 ，记 为其indicator向量（即 中对应这个点的一行）。由于满秩，存在不全为零的 使得 其中 是全 向量。
对于任意 ，我们有
,
根据 的任意性且 不全为零，这与 为偶数矛盾。
ch-nick-15 网友的相关建议:
这题碰巧刚遇到过
1
相关话题
π 的数字排列中能否找到 e 的数字排列？《隐秘的角落》这道解析几何有哪些比较好的解法？
本科阶段数学系的你的一天是怎么度过的？
如何评价穿越古代以数分为实数、虚数为开头写一本数学书？
为什么n维欧式空间中的单位球面（n-1 sphere）的表面积和体积，在 n 趋于 ∞ 时，都趋于0？
请问能把一个正方形划分成有限个四边形， 每个四边形都是凹四边形吗？
今年复活节应该是3月28号，网上怎么都说是4月4号的呢？春分后第一月圆后的第一礼拜天，怎么是4月4号？
如何评价2021年第三届阿里巴巴全球数学竞赛？
大一数分高代需要努力才能学好是不是意味着天赋不够？
在日常生活中，数学真的能够帮到我们吗？
前一个讨论
为什么说哲学是学科之母？
相关的话题
什么具体的理论／问题／让你对数学（本科以上）提起了真正的兴趣（motivation）？一道初三数学几何题。目前用arctan和tan的无脑计算可以求出来，请问还有其他方法吗？向量？或其它？
极坐标下的二重积分，二次积分下每次积分的几何意义是什么？
数学中对于直线、平面的定义是什么？
既然两个分数理论上来说可以无限接近，那么为什么还会出现无理数？
有没有在高考数学中使用洛必达法则而不扣分的方法？
如何看待一山东14岁高中生高考数学149分、总分699分，考入中科大少年班？与前几天火的某位相比如何？
求解决这道题目？
如何正确理解小概率事件，以及概率和哲学的关系？
用十二进制替换十进制是不是更符合自然规律？
如何证明R^2上的不可数集至少在一点附近局部不可数啊？
数学的应用到底有多广泛？
哪些看似与图论无关的问题可用图论模型解决？
为什么 AI 理解不了逻辑问题？
有一个数学很好的男朋友是一种怎样的体验?
目前统计学在国内外的发展现状是怎样的？都有哪些分支？今后的研究方向大致是向哪里走？
有没有处处不可导的凸函数？
为什么 1-1+1-1+1-1…=0.5？
如何看待 15 岁女生谈方琳参加世界顶尖科学家大会？她的研究成果含金量有多高？
关于哥德巴赫猜想，有人从哥德尔定理考虑过可证性吗？
为什么数学期刊的 IF 普遍不高?
国内具有冲击 2022 年菲尔兹奖实力的数学家吗？
数学系的鄙视链是什么？
请问如何求下面这个连分数收敛到的值？
离散型随机变量有没有概率密度？
［代数学］矩阵的概念最多可以推广到什么代数结构上？
数学或者自然科学中有哪些理论技巧一经提出就大大化简了过去某些问题很困难繁琐的解答？
是否存在这样一个初等函数：它的三阶导数是其本身，而一、二阶导数不是其本身？
高代，中间这一步是怎么来的呀?
经济学中Ed=-(△Q/△P)/(P/Q)如何推导，麻烦有懂得大神给个解答，最好详细一点。？