如何证明任意一个有偶数个顶点的图，一定存在两个点拥有偶数个共同邻居？ 第1页
1
constantine-85-33 网友的相关建议:
反设任意两点公共邻居奇数，考虑下图，A点的邻居集合为紫色部分，注意到由反证假设紫色子图内每点度数为奇数，故有紫色子图共偶数个点(否则度数求和非偶)，于是这实际推出任意点的度数都是偶数
那么再考虑任意B点到余下蓝色区域的边，必为偶数条，而我们考虑蓝色区域中任意C点到紫色区域的边数，必为奇数（由于C与A的公共邻居奇数），再考虑蓝色区域中的点数，为（偶数-偶数-1）是奇数。
于是从两方面考虑蓝色与紫色区域之间的边数的奇偶性即得
yifanjing 网友的相关建议:
写一下看到这个问题时我的第一反应的解法。
我们假设图 有偶数个顶点，任意两个顶点都有奇数个共同邻居。我们不妨假设图 的每个顶点都有偶数个邻居（否则我们可以将这个点的邻居和非邻居交换，可以验证图的其他性质不变）。
假设 是这个图的邻接矩阵。于是在 中， ，其中 是全 矩阵， 是单位矩阵。特别的， 是满秩的。
计 为包含每个点的邻居集的集合。对任意某个点的邻居集 ，记 为其indicator向量（即 中对应这个点的一行）。由于满秩，存在不全为零的 使得 其中 是全 向量。
对于任意 ，我们有
,
根据 的任意性且 不全为零，这与 为偶数矛盾。
ch-nick-15 网友的相关建议:
这题碰巧刚遇到过
1
相关话题
测度论（measure theory）和实变函数是什么关系？如何计算以下的积分？
你见过的最丑的函数曲线图形是什么？
图论和拓扑有什么区别？
如何入门 Yamabe 问题？
∑ (1/n) 为何不收敛？
能不能出一道很难的数学题，答案是 629，宿舍当门牌用？
考虑一个半径为 1 的圆，若「随机」选择圆上的弦，求弦长的概率分布？
既然10/3等于3.3333除不尽，那为什么一根10米的绳子却能分成三等份？
请问乘和乘以有区别吗？
前一个讨论
为什么说哲学是学科之母？
相关的话题
被剑桥大学 deferred entry 应该接受吗？能解释一下这些公式吗?
是否可以根据薛定谔的平行宇宙理论推翻概率学？
理论物理学家爱德华·威滕做了啥贡献，以致于他获得了数学界的菲尔兹奖？
高斯-博内定理和幅角原理的关系是什么？
如何尽可能精确地称量 π 斤肉？
如何评价动画《理科生坠入情网，故尝试证明》?
数学在战争中能起到什么样的作用？
有没有可能把 π 或 e 等无理数当成 1，这样就能使许多定理显而易见？
数学系大一学生学习数分时看一页书花 20~30 分钟合理吗？
是否存在这样一个初等函数：它的三阶导数是其本身，而一、二阶导数不是其本身？
物理学与数学在思维方式上有什么本质区别？
如何证明如下积分等式？
七个小朋友，只能切四刀，怎么把三个苹果均分？
高三毕业生想以后学数学，如何在填志愿之前判断自己是否适合?
有哪些指标可以描述两个图（graph）的相似度？
请问这个极限怎么算 谢谢?
常听人说「我吃的盐比你吃的米还多」，这真的有可能吗？
关于物理旋转体（甜甜圈）模型体积的计算？
根号 2 与根号 3 之和约等于 π，这是巧合，还是有什么特殊意义？
在高中，数学不好的人物理一定也不好吗？
自增运算这道题怎么解？
如何看待《中国科学报》刊文评论美女数学博士后获奥运冠军：其实没啥了不起？
△ABC中，tanA＋tanB＋tanC＝tanA·tanB·tanC有没有优美直观一点的几何证明？
现在的纯数学家们对于自然科学的关注大概是怎样的程度？
集合论与微积分？
有没有在高考数学中使用洛必达法则而不扣分的方法？
全体自然数的发散级数和等于负十二分之一代表了什么？隐藏了一个天大的秘密吗？
世界上存在周长为整数，半径也是整数的圆吗？
这个极限咋算？