如何证明任意一个有偶数个顶点的图，一定存在两个点拥有偶数个共同邻居？ 第1页
1
constantine-85-33 网友的相关建议:
反设任意两点公共邻居奇数，考虑下图，A点的邻居集合为紫色部分，注意到由反证假设紫色子图内每点度数为奇数，故有紫色子图共偶数个点(否则度数求和非偶)，于是这实际推出任意点的度数都是偶数
那么再考虑任意B点到余下蓝色区域的边，必为偶数条，而我们考虑蓝色区域中任意C点到紫色区域的边数，必为奇数（由于C与A的公共邻居奇数），再考虑蓝色区域中的点数，为（偶数-偶数-1）是奇数。
于是从两方面考虑蓝色与紫色区域之间的边数的奇偶性即得
yifanjing 网友的相关建议:
写一下看到这个问题时我的第一反应的解法。
我们假设图 有偶数个顶点，任意两个顶点都有奇数个共同邻居。我们不妨假设图 的每个顶点都有偶数个邻居（否则我们可以将这个点的邻居和非邻居交换，可以验证图的其他性质不变）。
假设 是这个图的邻接矩阵。于是在 中， ，其中 是全 矩阵， 是单位矩阵。特别的， 是满秩的。
计 为包含每个点的邻居集的集合。对任意某个点的邻居集 ，记 为其indicator向量（即 中对应这个点的一行）。由于满秩，存在不全为零的 使得 其中 是全 向量。
对于任意 ，我们有
,
根据 的任意性且 不全为零，这与 为偶数矛盾。
ch-nick-15 网友的相关建议:
这题碰巧刚遇到过
1
相关话题
随机取牌算不出 24 点的概率是多少？如何看待京都大学的望月新一教授证明「ABC 猜想」，发表在其主编的期刊上？
勒让德倍量公式如何证明？
数学专业考研（数分高代）如何做笔记？
为什么数学专业要学计算机？
i 的 i 次方是实数吗？
如何解决这个数学问题?
各个学科内都有哪些「很美」的公式或者结论？它们是大自然的鬼斧神工还是人类的匠心独造？
抽五张牌，选择并依次展示其中四张，能否猜出第五张牌？
有没有什么数字的某个幂次方等于0？
前一个讨论
为什么说哲学是学科之母？
相关的话题
如何只使用折叠的方法十等分一个线段或者绳子？根据策梅洛定理，中国象棋是不是应该红方必胜或必和棋（看补充）？
如何解释「线性回归」的含义？
证明「哥德巴赫猜想」到底有多难？
有没有一套统一的办法处理非初等的原函数？
对这个图有什么看法？
怎么形象清晰地解释「周期 3 意味着混沌」?
f（x,y)->(x,y),是2维实数空间的 一一映射函数，f连续，f的反函数是否也连续，why？
2019新课标1数学概率大题中的一个递推公式如何的出？
为什么要把 mathematics 翻译成「数学」，导致中学生对「数字的学问」没兴趣？
为什么是数学而不是文学是“科学的皇后”？
如何通俗地解释什么是离散傅里叶变换？
素数的 Willans 公式是否正确？
如何用初等数学证明2的a次方（a大于零）大于1？
五岁孩子对数学感兴趣，想给她讲数学发展史的故事，请问有什么书推荐呢？
数学建模入门请问要学习什么?
大家知道的最长（复杂）的公式是什么？
若零向量没有方向，那它还是向量吗？
准高一学生想自学数学有什么建议吗？
已知映射f：N→N（其中N是正整数集），问以下三条是否可以相容？
如何看待π这个无理数？
1+0.1+0.01+0.001+0.0001... 一直下去会在实际中到达 2 吗？
向量奔驰定理有哪些证明?
历史上，近世代数中环和域的概念是怎样逐步建立的？
数学的应用到底有多广泛？
这道题该怎么解?
将无数个苯连接在一起会生成什么？
如何理解庞加莱对偶（Poincare Duality）?
求解决这道题目？
中国能否出现世界一流的数学研究机构？