Erdős 序列

令 为一个任意图。那么存在一个集合 和一个子集族 , , ... 的 可以与 的顶点一一对应，使得 的边出现 当且仅当 且 ，其中 表示 空集。这个定理由 Erdős 等人 (1966) 归功于 Szpilrajn-Marczewski (1945)。

这个定理的一个推论是，对于每个在 个 顶点上的有限简单图 ，存在一个 个不同的非负整数序列 可以与 的顶点一一对应，使得顶点 和 被边连接 当且仅当 且 不是互质的（即，如果它们共享一个公因子）。

这样的序列可以被称为 Erdős 序列，而对应于给定 Erdős 序列的图被称为 Erdős 图，这些术语可能是首次在此引入。

例如，Erdős 序列 (2, 3, 5, 6, 10, 15) 对应于 2-三角形网格图，如上图所示。

在具有 个顶点的图的 Erdős 序列中，最小的最大值由 给出，其中 表示素数阶乘。这个值由星图 对于 达成。

简单的情况包括空图 , 它具有序列 , 其中 是第 个素数，以及完全图 , 它具有序列 。

下表总结了各种图的 Erdős 序列，这些序列是字典序第一且具有最小可能最大值的序列。它们也在上图中进行了说明。

图	Erdős 序列
空图	(1, 2)
路径图	(2, 4)
空图	(1, 2, 3)
路径图	(2, 3, 6)
三角形图	(2, 4, 6)
爪图	(2, 3, 5, 30)
四面体图	(2, 4, 6, 8)
路径图	(3, 5, 6, 10)
方形图	(10, 14, 15, 21)
星图	(2, 3, 5, 7, 210)
轮图	(6, 10, 14, 15, 21)