如何证明任意一个有偶数个顶点的图，一定存在两个点拥有偶数个共同邻居？ 第1页
1
constantine-85-33 网友的相关建议:
反设任意两点公共邻居奇数，考虑下图，A点的邻居集合为紫色部分，注意到由反证假设紫色子图内每点度数为奇数，故有紫色子图共偶数个点(否则度数求和非偶)，于是这实际推出任意点的度数都是偶数
那么再考虑任意B点到余下蓝色区域的边，必为偶数条，而我们考虑蓝色区域中任意C点到紫色区域的边数，必为奇数（由于C与A的公共邻居奇数），再考虑蓝色区域中的点数，为（偶数-偶数-1）是奇数。
于是从两方面考虑蓝色与紫色区域之间的边数的奇偶性即得
yifanjing 网友的相关建议:
写一下看到这个问题时我的第一反应的解法。
我们假设图 有偶数个顶点，任意两个顶点都有奇数个共同邻居。我们不妨假设图 的每个顶点都有偶数个邻居（否则我们可以将这个点的邻居和非邻居交换，可以验证图的其他性质不变）。
假设 是这个图的邻接矩阵。于是在 中， ，其中 是全 矩阵， 是单位矩阵。特别的， 是满秩的。
计 为包含每个点的邻居集的集合。对任意某个点的邻居集 ，记 为其indicator向量（即 中对应这个点的一行）。由于满秩，存在不全为零的 使得 其中 是全 向量。
对于任意 ，我们有
,
根据 的任意性且 不全为零，这与 为偶数矛盾。
ch-nick-15 网友的相关建议:
这题碰巧刚遇到过
1
相关话题
如何能更好地理解（ε-δ）语言极限的定义？如何评价「Shut up and calculate」这句话？
下面这个关于质数的不等式如何证明？
5是一个已知数，设5＝x或者x＝5，这两个表达的意思在数学和语文表达正确吗？
怎么建立复数与实数的一一对应？
正方体的体对角线垂直吗？
证明数学定理的意义是什么？
数学 物理 化学三者在本质上的区别是什么?
有哪些不同的物体,他们沿所有轴的转动惯量都相同?
如何计算投掷多个骰子得到某个给定总点数的概率？
前一个讨论
为什么说哲学是学科之母？
相关的话题
外国人是不是也背诵乘法口诀？我是计算数学专业的学生，以后想向芯片制造方向，或者是航空发动机方向走，请问应该自学什么或者考什么博。？
如何看待有的物理学家说物理学就是几何学，以及物理学需要新的几何学注入活力？
数学/算法：正方形内有5个点，为什么最近点对的距离小于边长？
这个数列怎么求和，求数学大神？
这个式子对吗？若是，具体步骤是什么？
比较高深的数学在经济学有哪些运用相当漂亮？
如何看待初一学生因偏科，在数学卷上答语文？
为什么有些数学系学生会瞧不起 CS（计算机）系学生？
如何避免完美主义倾向，以应用的方式/目的学习各类理论？
我认为中国把英语太过重视 甚至超过了数学和我们的国语语文 你怎么看？
一个函数的不定积分存在有哪些必要条件或者充分条件？
能否把数学竞赛变得更有观赏性？
“太阳从西边或东边出来”是必然事件，随机事件还是不可能事件？
王茂泽宣称其破解世界著名难题「冰雹猜想」，他的证明正确吗？
博弈论+图论，博士有哪些方向可以选择？
假设我扔一枚硬币，60次有55次正面朝上，我有多大把握认为这枚硬币正面和反面出现概率不相同？
有关银河系搭车客指南的理解上的问题?
如何证明不等式 ln2>(2/5)^(2/5)?
为什么n为素数时，n能整除2^n - 2，怎么证明?
数学上有哪些丑陋的公式？
社会科学可以被形式化公理化吗？
如何计算此多重积分不等式？
哪个瞬间让你觉得学数学真有用？
逐渐丢失对数学的兴趣，怎么办？
如何评价数学家黎曼的成就与历史地位？
地球的圆是什么程度的圆？
丁小平到底是怎样的一个人？
编程是否存在终极问题？
高中数学有没有可能在往后的人生中几乎用不到，如果有，那我们学习的意义是什么？