如何证明任意一个有偶数个顶点的图，一定存在两个点拥有偶数个共同邻居？ 第1页
1
constantine-85-33 网友的相关建议:
反设任意两点公共邻居奇数，考虑下图，A点的邻居集合为紫色部分，注意到由反证假设紫色子图内每点度数为奇数，故有紫色子图共偶数个点(否则度数求和非偶)，于是这实际推出任意点的度数都是偶数
那么再考虑任意B点到余下蓝色区域的边，必为偶数条，而我们考虑蓝色区域中任意C点到紫色区域的边数，必为奇数（由于C与A的公共邻居奇数），再考虑蓝色区域中的点数，为（偶数-偶数-1）是奇数。
于是从两方面考虑蓝色与紫色区域之间的边数的奇偶性即得
yifanjing 网友的相关建议:
写一下看到这个问题时我的第一反应的解法。
我们假设图 有偶数个顶点，任意两个顶点都有奇数个共同邻居。我们不妨假设图 的每个顶点都有偶数个邻居（否则我们可以将这个点的邻居和非邻居交换，可以验证图的其他性质不变）。
假设 是这个图的邻接矩阵。于是在 中， ，其中 是全 矩阵， 是单位矩阵。特别的， 是满秩的。
计 为包含每个点的邻居集的集合。对任意某个点的邻居集 ，记 为其indicator向量（即 中对应这个点的一行）。由于满秩，存在不全为零的 使得 其中 是全 向量。
对于任意 ，我们有
,
根据 的任意性且 不全为零，这与 为偶数矛盾。
ch-nick-15 网友的相关建议:
这题碰巧刚遇到过
1
相关话题
逻辑学中，前提为假而命题为真的推论如何解释？有没有办法从数学上定义脸蛋的光滑性？
理想情況下，对于任意一种台球布局，是否存在一个击球方案，一杆就能使所有球进洞？
如果历史上没有牛顿、莱布尼茨、欧拉、高斯、阿贝尔……等人，我们的科学、技术和文明还有这么强大吗？
平面几何中圆与直线的统一性如何体现？
如何证明一个无理数的整数倍数的小数部分在（0，1）上均匀分布？
工作、学习累了做道数学题放松一下的大神究竟是怎样一种体验，为何我做题都累死了？
请问这第一道三阶常微分方程怎么解啊，不用特征方程解法怎么做？
数学分析究竟在讲些什么？
数学能力是不是会退化？
前一个讨论
为什么说哲学是学科之母？
相关的话题
a=b则b=a，这是真理吗？有没有例外？10000⁴ 和 4¹⁰⁰⁰⁰，怎样比较大小？
请问这第一道三阶常微分方程怎么解啊，不用特征方程解法怎么做？
数学中，f'(x) 和 (f(x))' 到底有什么区别？
除了黎曼猜想，数学界还有哪些至今尚未得到证实的猜想？
在高中，数学不好的人物理一定也不好吗？
请问泰勒公式的几何意义是什么？
图论里的图用什么软件画比较好？
中国象棋的走法是有限的吗？如果有限，有没有先走或者后走的人必赢的可能？
这个积分问题怎么做？
下面这个题该如何做？
正项级数∑xn收敛，数列xn单调减少，如何证明limnXn＝0？
请问这道数学分析题目应该怎么做呢？
为什么∫x²/（√1-x²）dx用分部积分求不出来不定积分?
1，2，3，…，n。去掉1，将2挪在n后；去掉3，将4挪在2后，按此规律进行下去，最后留下的数字是？
什么情况下被积函数的原函数不能用初等函数表示？怎么判断呢？
为什么感觉群论学起来比数学分析之类难好多？
数学系的学生有哪些口头禅？
抽五张牌，选择并依次展示其中四张，能否猜出第五张牌？
有关大学物理推导的微分运算是否合理？
数学中，有哪些方程和思想让你体会到了美感？
为什么该图形红蓝面积相等?
你见过哪些美妙的函数图像？
已知正数a、b、c满足a+b+c=1，如何证明a²+b²+c²+2abc的范围是[11/27,1)？
代数好的人但立体几何不好的男生是智商低吗？
如何理解数学证明中的容易验证？
我发现有个积分很接近e^π+π^e，有大佬能解释下原因吗？
如何证明这个关于ζ(5)的等式？
哪些生活问题可以用数学理论来解释？
高四了，数学只有七八十分，距离高考就剩一百多天了，真的很迷茫。该怎么提分啊?