广达杂志的大嘴巴
现在大流行的限制正在放松，人们又聚在一起了。但是已经有一段时间了，所以如果你和你的朋友需要一些帮助来打破僵局，这里有一个数学派对游戏，你可以试试。
挑战小组中的每个人握手，但只能与奇数人握手。 （如果您更喜欢社交距离，请随意用空中击掌代替。）假设是您和您的六个朋友。
一开始，大家都握手零，所以你们都从偶数开始。假设安娜和拜伦主动握手。现在他们各自握手。
美林谢尔曼/广达杂志
凯特琳需要加入，所以她和拜伦握手，给了她一次握手，一个奇数。但是现在拜伦有两次握手，所以他又回到了偶数。
Demarr、Ernest 和 Flora 也加入进来并开始握手，将偶数变为赔率，反之亦然。
最终，您的六个朋友解决了问题并得出了一个成功的配置。
但是你仍然必须与某人握手，而多一次握手会产生很大的不同。一旦你握手，你的一个朋友将有偶数次握手，现在游戏必须恢复。
上图将我们的游戏显示为一个图形——点（称为顶点）和它们之间的段（称为边）的集合。你面临的困境体现了图论中一个简单但深刻的想法，图论是一个研究这些重要表示的性质和特征的数学领域。尽管图论的许多基本原理是在数百年前建立的，但今天的科学家仍然使用它们来更好地理解各种系统是如何连接的，从政治网络中的组织到生态系统中的动物，再到互联网上的网站。事实上，在我们的数学派对游戏中，有一些积极的研究产生了关于各种图表的新结果。
在我们的游戏图中，人是顶点，握手是边。数字表示每个人有多少次握手，在图中被称为顶点的“度数”：它是连接到该顶点的边数。
样本顶点及其度数。
数学家研究的图表可能会变得非常庞大和复杂，因此查看一些简单的特征会有所帮助。一个这样的特征是图的所有度数的总和。马上，这个“度数”就告诉我们，七个人，我们的聚会游戏是不可能赢的！让我们看看为什么。
计算图的度数和的一种方法是列出所有单独的度数并将它们相加。但是还有另一种方法依赖于对边缘的巧妙计算。由于每条边都连接到两个顶点，因此它对总度数的贡献是两个：它连接到的每个顶点一个。因此，将图中的所有度数相加与计算每条边两次相同。由于度数和是边数的两倍，因此对于任何图，它总是必须是偶数。
事实上，我们甚至更早地看到了：前两个人握手的那一刻。
如果只有两个人玩这个游戏，那么他们每个人都有可能握手奇数个手。您可以将此对视为“奇数子图”，即较大图中的较小图，其顶点都具有奇数度。
构建子图时，您选择一组顶点并仅考虑这些顶点之间的边。这意味着您只需忽略连接到子图外部任何顶点的边。
通过忽略边形成子图。
形成子图自然会将图分成两部分，这是图论者在分析图时喜欢做的事情：它可以帮助他们识别以特殊方式互连的顶点簇。并且知道子图是偶数还是奇数可以提供有关图结构的额外信息。例如，一个“连通”的偶数图——意味着你总能在任意两个顶点之间找到一条路径——必须包含一个“欧拉回路”，一条只通过每条边一次的路径。
从我们的聚会游戏中我们知道，给定一组顶点，并不总是可以形成一个奇数图。但总是有可能形成一个奇子图。实现这一点的一种无聊方法是执行我们上面所做的：只需选择两个相互连接的顶点并忽略它们的所有其他边。这产生了一个奇怪的子图，但非常小。总是有可能找到一个大的奇子图吗？
众所周知，每个图都包含一个大的偶数子图。在 1960 年代，匈牙利数学家 Tibor Gallai 证明了每个图都可以分成两个偶数子图。这样做会将一组n个顶点分成两个子集，其中一个子集必须包含至少一半的顶点。这保证了每个图都有一个偶数子图，该子图至少是原始图的一半。
但是 60 多年来，奇数子图可以有多大一直是图论中的一个开放研究问题。在我们失败的派对游戏图中，有一个奇怪的子图使用了七个顶点中的六个。
这相对于原版来说是相当大的。但这是另一个失败的尝试，它使用较小的最大奇数子图，仅使用四个原始顶点。
具有最大奇数子图的图，仅使用七个顶点中的四个。
在寻找最大保证奇数子图时，一些早期的成功表示使用原始图本身大小的顶点分数。例如，在 1990 年代，数学家 Yair Caro 表明，任何具有n个顶点的图都必须有一个奇数子图，该子图至少包含的总顶点。这意味着具有 25 个顶点的图必须有一个奇数子图，其中至少包含
在 25 个顶点中，一个有 100 个顶点的图将有一个奇数子图，其中至少包含
100 个顶点。类似的结果随之而来，但数学家们正在寻找加莱的发现：一个对奇数子图起作用的分数
适用于偶数子图。
这样的结果终于在 2021 年出现，当时 Asaf Ferber 和 Michael Krivelevich 证明了每个图都有一个奇数子图，该子图至少使用原始图的顶点。这似乎是一个低标准，特别是因为有些人推测真实分数更接近
，但是找到一个有效的分数允许数学家从证明这样的分数存在到改进他们已经拥有的分数。一个数字，就像一次握手一样，可以产生很大的不同。
练习
- 找到下图的最大奇数子图。
- 展示如何将下面的循环拆分为奇数子图和偶数子图。
- 在n个顶点上的完整图是一个图，其中n个顶点中的每一个都通过一条边连接到其他每个顶点。完整的图可以是奇数图吗？
- 在 1960 年代，Tibor Gallai 证明了总是可以将一个图拆分为两个偶数子图。根据您在本专栏中所读到的内容，您可以证明并非总是可以将一个图拆分为两个奇数子图。什么原因？
点击答案1：
请注意，该图有八个顶点，并且不是奇数图，因为它有一些偶数度顶点。在该列中确定了具有七个顶点的图不可能是奇数，因此如果我们可以找到具有六个顶点的奇数子图，那么这将是最大尺寸。一个这样的例子如下所示。
点击答案2：
一种解决方案是将A和D放入它们自己的子图中。由于它们不相互连接，因此该子图中的度数均为零，使其成为偶数子图。另一个子图中的度数都是 1，所以这是一个奇数子图。注意：这些是“断开连接”图的示例。
点击答案3：
是的。当n为偶数时， n个顶点上的完整图始终是奇数图。每个顶点将连接到其他n – 1 个顶点，使每个顶点的度数为n – 1。这是一个奇数，因为 n 是偶数，所以这是一个奇数图。当n为奇数时， n个顶点上的完整图是偶数图。
点击答案4：
如果一个图有奇数个顶点，那么将它分成两个子图总是会导致一个子图的顶点数为偶数，一个子图的顶点数为奇数。正如列中所解释的，具有奇数个顶点的图不能是奇数，因此具有奇数个顶点的图不能拆分为两个奇数子图。
来源： https://www.quantamagazine.org/what-a-math-party-game-tells-us-about-graph-theory-20220324/