如何证明任意一个有偶数个顶点的图，一定存在两个点拥有偶数个共同邻居？ 第1页
1
constantine-85-33 网友的相关建议:
反设任意两点公共邻居奇数，考虑下图，A点的邻居集合为紫色部分，注意到由反证假设紫色子图内每点度数为奇数，故有紫色子图共偶数个点(否则度数求和非偶)，于是这实际推出任意点的度数都是偶数
那么再考虑任意B点到余下蓝色区域的边，必为偶数条，而我们考虑蓝色区域中任意C点到紫色区域的边数，必为奇数（由于C与A的公共邻居奇数），再考虑蓝色区域中的点数，为（偶数-偶数-1）是奇数。
于是从两方面考虑蓝色与紫色区域之间的边数的奇偶性即得
yifanjing 网友的相关建议:
写一下看到这个问题时我的第一反应的解法。
我们假设图 有偶数个顶点，任意两个顶点都有奇数个共同邻居。我们不妨假设图 的每个顶点都有偶数个邻居（否则我们可以将这个点的邻居和非邻居交换，可以验证图的其他性质不变）。
假设 是这个图的邻接矩阵。于是在 中， ，其中 是全 矩阵， 是单位矩阵。特别的， 是满秩的。
计 为包含每个点的邻居集的集合。对任意某个点的邻居集 ，记 为其indicator向量（即 中对应这个点的一行）。由于满秩，存在不全为零的 使得 其中 是全 向量。
对于任意 ，我们有
,
根据 的任意性且 不全为零，这与 为偶数矛盾。
ch-nick-15 网友的相关建议:
这题碰巧刚遇到过
1
相关话题
你有没有推导过一个复杂的却「贴近生活」的公式？是否存在仅由1和2组成的长度为2^n的序列，可以做到在这个序列中取出所有含1和2的长度为n的序列？
一个关于数学归纳法的悖论问题：到底是第 N 天有 N 个红眼睛自杀，还是什么都不会发生？
这个有关斐波那契数的求和怎么证明？
有没有可能使数个单位体积的立方体在空间中实现准确定位从而模拟出各类有形物体？
如何理解香农第一定理?
你最喜欢的一句数学界的名言是什么？
一道难题求助大佬?
这个极限怎么做呢？
怎么做，求解?
前一个讨论
为什么说哲学是学科之母？
相关的话题
二次型惯性定理得名原因？数学不好能读理科吗?
杨小凯先生墓碑最下面的符号是什么意思？
一个袋子里有n个球，都是红球。现在拿一个球出来，放一个蓝的进去，重复n次过后红球占比？
为什么感觉群论学起来比数学分析之类难好多？
中学阶段解出一道很难的数学题和在数学研究领域做出重大突破的区别在哪？
这张图中能数出多少个三角形？
(lnx)'＝1/x，为什么 (ln3)'≠1/3？
数学史上有哪些比较著名的猜想因为有反例的存在而没有成为定理？
自然常数 e 从小数点后第二位开始的两个 1828 是巧合吗？
为何中国的中小学数学教育如此轻视统计和概率？
这个题的计算方法是什么？
勒让德猜想被证明了吗？
如何尽可能精确地称量 π 斤肉？
一道初三数学几何题。目前用arctan和tan的无脑计算可以求出来，请问还有其他方法吗？向量？或其它？
如何看待 Atiyah 宣布证明了黎曼猜想？
怎么在不公布证明的情况下让世人相信我证明了「哥猜」?
如何根据一张 A 楼照 B 楼的照片判断出这张照片是 A 楼的几层？
科学和数学的关系是什么?
为什么数学中一定要强调加法交换律？
爱因斯坦作为一个物理学家，他的数学水平有多高？
瞬间之中真的包含永远吗，瞬间之中怎么包含永远？
大学数学具体学什么，以及相关的自学用书？
中国古代数学有什么成就？
若 f(f(x))=x²+1，则 f(1) 为多少？
如何证明树的树叶个数比度数不少于3的顶点数多？
为什么俄罗斯的文学、数学、音乐都那么强，诞生了好多大牛？
这个荔枝弯曲的形状是否有曲线方程？
请问这个抽象代数题怎么证明？
数学家（数学专业）都是怎么搞研究的?