如何证明任意一个有偶数个顶点的图，一定存在两个点拥有偶数个共同邻居？ 第1页
1
constantine-85-33 网友的相关建议:
反设任意两点公共邻居奇数，考虑下图，A点的邻居集合为紫色部分，注意到由反证假设紫色子图内每点度数为奇数，故有紫色子图共偶数个点(否则度数求和非偶)，于是这实际推出任意点的度数都是偶数
那么再考虑任意B点到余下蓝色区域的边，必为偶数条，而我们考虑蓝色区域中任意C点到紫色区域的边数，必为奇数（由于C与A的公共邻居奇数），再考虑蓝色区域中的点数，为（偶数-偶数-1）是奇数。
于是从两方面考虑蓝色与紫色区域之间的边数的奇偶性即得
yifanjing 网友的相关建议:
写一下看到这个问题时我的第一反应的解法。
我们假设图 有偶数个顶点，任意两个顶点都有奇数个共同邻居。我们不妨假设图 的每个顶点都有偶数个邻居（否则我们可以将这个点的邻居和非邻居交换，可以验证图的其他性质不变）。
假设 是这个图的邻接矩阵。于是在 中， ，其中 是全 矩阵， 是单位矩阵。特别的， 是满秩的。
计 为包含每个点的邻居集的集合。对任意某个点的邻居集 ，记 为其indicator向量（即 中对应这个点的一行）。由于满秩，存在不全为零的 使得 其中 是全 向量。
对于任意 ，我们有
,
根据 的任意性且 不全为零，这与 为偶数矛盾。
ch-nick-15 网友的相关建议:
这题碰巧刚遇到过
1
相关话题
假设我们已知三角形内角和为180度,那么(凸)多边形的内角和是如何计算的（用数学方法论的方法解决)?数学和物理中这些符号到底念什么？来源是什么？
做学术需要搞清楚高级计量经济学里全部的数学原理吗？
为什么正方体有十一种展开图？
n 座桥，连通 n+1 个岛，有多少种连法？
除了 3，4，5 以外是否还有别的三角形，它的三条边是连续自然数，它的面积也是自然数？
物理学常量（例如光速）把量纲去除（如果有的话）都是有理数还是无理数？
如何评价王萼芳的高等代数教材？
怎么形象清晰地解释「周期 3 意味着混沌」?
家人们，帮我看看这个极限?
前一个讨论
为什么说哲学是学科之母？
相关的话题
如何看待菲尔兹和阿贝尔奖双料得主 Michael Atiyah 宣称自己证明了黎曼猜想？阶乘的概念能否推广到全体实数，甚至是全体复数？
为什么费马大定理表述起来这么简单，证明却这么复杂？
怎么解Biler上的一道分析难题？
如何看待清华 2021 年丘成桐数学领军人才招生办法，初三生可报名申请，期间不得转专业？
有哪些违背直觉的数学问题？
三阶魔方公式的最大周期是多少？对应的公式是什么？
集合论与微积分？
0.9999…是否等于1的一个疑问?
阿基里斯和乌龟的悖论真的不能用常规逻辑推翻吗？
离散数学色里的哈斯图怎么画？
学数学或物理学到 high 很刺激，是一种怎样的经历与感受？
小学2年级学生能掌握微积分吗？
有什么与数学名词有关的趣事?
无限群是否一定含无限阶元？无限群是否一定有无限多个子群？
大学数学具体学什么，以及相关的自学用书？
真正顶尖的大师都是师承的吗？
一个会读心术和一个能预知未来的人下棋，谁能赢？
普通外国人算术真的很差吗？
张益唐九几年在美国过得那么苦逼为何不选择回国拿当时高达几百块RMB的月薪，回国没有更好的研究条件吗？
如何通俗地解释马尔科夫链?
如何看待阿里巴巴全球数学竞赛？对其他学科有哪些实际影响和意义？
数列1，22，333，4444……的通项公式是什么？
统计学中「矩」这个概念是怎么引入的？它为什么被称为矩？它与物理意义上的矩有什么相同与不同？
请试着论证下此问题是否条件充分，可解？
如何求证：无穷级数∑1/i²=π²/6，求方法？
高中数学太简单，该不该把高数上和线性代数放进高中学习？
研究数学是不是必须有天赋？
单位圆上n等分点按不同顺序顺次连接，能连接出多少种图形？
「奇变偶不变，符号看象限」这句话最早是谁提出来的？