如何证明任意一个有偶数个顶点的图，一定存在两个点拥有偶数个共同邻居？ 第1页
1
constantine-85-33 网友的相关建议:
反设任意两点公共邻居奇数，考虑下图，A点的邻居集合为紫色部分，注意到由反证假设紫色子图内每点度数为奇数，故有紫色子图共偶数个点(否则度数求和非偶)，于是这实际推出任意点的度数都是偶数
那么再考虑任意B点到余下蓝色区域的边，必为偶数条，而我们考虑蓝色区域中任意C点到紫色区域的边数，必为奇数（由于C与A的公共邻居奇数），再考虑蓝色区域中的点数，为（偶数-偶数-1）是奇数。
于是从两方面考虑蓝色与紫色区域之间的边数的奇偶性即得
yifanjing 网友的相关建议:
写一下看到这个问题时我的第一反应的解法。
我们假设图 有偶数个顶点，任意两个顶点都有奇数个共同邻居。我们不妨假设图 的每个顶点都有偶数个邻居（否则我们可以将这个点的邻居和非邻居交换，可以验证图的其他性质不变）。
假设 是这个图的邻接矩阵。于是在 中， ，其中 是全 矩阵， 是单位矩阵。特别的， 是满秩的。
计 为包含每个点的邻居集的集合。对任意某个点的邻居集 ，记 为其indicator向量（即 中对应这个点的一行）。由于满秩，存在不全为零的 使得 其中 是全 向量。
对于任意 ，我们有
,
根据 的任意性且 不全为零，这与 为偶数矛盾。
ch-nick-15 网友的相关建议:
这题碰巧刚遇到过
1
相关话题
穷人里出来的学霸和富人里出来的学霸有什么相同点和不同点？为什么中国小学数学教育要揪“除”和“除以”的区别？
为什么科技互联网公司越来越重视数学？
逃离丧尸包围的游戏，你能否逃生？
数学学习与数学科研有多大区别？
对于高数以及更加高深的数学学习者来说，你们是如何思考并想象数理问题的？
（纯）数学 phd 的你们和导师 meeting 的时候都聊些什么？
数学领域如今是否还会提出新的猜想?
英国人真的连乘法口诀都不熟悉么？
你知道哪些冷门但内容十分好的数学书？
前一个讨论
为什么说哲学是学科之母？
相关的话题
如何通俗易懂地解答双信封悖论？这道题做错在了哪里呢？
如图所示，如何回答五年级孩子的疑问：9除以9得到的结果为1，而不是0.99999……（9的循环）？
俄罗斯的数学教育为什么那么强大？
如何评价hEzo？
为何要引入同伦群，同伦群可以解决什么问题？
参加 2021 年丘成桐大学生数学竞赛是什么体验？如何评价今年的竞赛？
如何证明以下式子？
如何证明随机变量的中数一阶矩最小？
请试着论证下此问题是否条件充分，可解？
证明如果幂级数在收敛圆上一点收敛，那么从圆内沿任意不与圆周相切的方向逼近时有极限？
谜之代码是否存在？
圆周率 π 是否隐藏了本个宇宙的设计者留给这个宇宙的智慧文明的某种信息？
什么日常现象只能用意想不到的复杂科学或数学来解释？
大学数学具体学什么，以及相关的自学用书？
如果我的将来梦想是取消数学这门学科，我该怎么做，或者谁可以帮忙实现它？
虚数是负数的平方根，为什么是在三次方程中才出现的呢？
证明数学定理的意义是什么？
为什么感觉群论学起来比数学分析之类难好多？
除和除以到底为什么不一样？
复数范围内，一个数的整数次方是不是永远只有一个值？以及如何证明一个数的无理数次方对应无穷个值？
学了数学变秃了却没有变强，这正常吗？
学习什么知识可以更好地掌握线性代数、概率论与数理统计以及微积分这种较基础的数学工具？
整數分拆中的分拆函數能否延拓至非整數？
确定正弦函数图象需要几个点？
包含所有各项不大于n的n元正整数列且长度最小的序列有多少个？
真正喜欢数学的人是什么样的？
一个初中生，做数学作业老是偷偷地用 MATLAB 计算，如何让他知道用 MATLAB 做数学题的危害？
如何定义或描述数学的全貌？
为什么不能直接把哥德巴赫猜想作为一个公理？