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)