存在性定理是一类定性描述。要把某种离散对象按某个确定的约束条件进行安排，如果这种特定的安排是否存在还不确定，就需要首先讨论这种特定安排的存在性问题。

在经典组合数学中，霍尔定理、拉姆齐定理和狄尔沃斯定理是三个主要的存在性定理。

霍尔定理使用于组合问题中；二部图G中的两部分顶点组成的集合分别为X, Y, ， ，G中有一组无公共点的边，一端恰好为组成X的点的充分必要条件是：X中的任意k个点至少与Y中的k(1≤k≤m)个点相邻。

霍尔定理还有一个重要推论：二部图G中的两部分顶点组成的集合分别为X,Y, 若∣X∣=∣Y∣,且G中有一组无公共端点的边，一端恰好组成X中的点，一端恰好组成Y中的点，则称二部图G中存在完美匹配。若图G的每个点度数为t，则称二部图G为t-正则的二部图存在完美匹配。

本定理是二分图匹配问题中匈牙利算法的基础。

在组合数学上，诺曼·拉姆齐(Ramsey)定理是要解决以下的问题：要找这样一个最小的数n，使得n个人中必定有k个人相识或l个人互不相识。

6 个人中至少存在3人相互认识或者相互不认识。

该定理等价于证明这6个顶点的完全图的边，用红、蓝二色任意着色，必然至少存在一个红色边三角形，或蓝色边三角形。

(Dilworth's theorem)

狄尔沃斯定理亦称偏序集分解定理，是关于偏序集的极大极小的定理，该定理断言：对于任意有限偏序集，其最大反链中元素的数目必等于最小链划分中链的数目。此定理的对偶形式亦真，它断言：对于任意有限偏序集，其最长链中元素的数目必等于其最小反链划分中反链的数目，由偏序集P按如下方式产生的图G称为偏序集的可比图：G的节点集由P的元素组成，而e为G中的边，仅当e的两端点在P中是可比较的，有限全序集的可比图为完全图。