Let \(G\) be a graph with vertex set \(V\), and let \(S \subseteq V\). Then \(S\) is an independent set of \(G\) — no edge of \(G\) has both of its ends in \(S\) — if and only if the complement \(V \setminus S\) is a covering of \(G\), that is, every edge of \(G\) has at least one end in \(V \setminus S\).

Let \(G\) be a simple graph on a finite vertex set \(V\), and write \(n = \left\lvert V\right\rvert \) for its number of vertices. Denote by \(\alpha (G)\) the independence number of \(G\), the largest size of a set of vertices no two of which are adjacent, and by \(\beta (G)\) the covering number of \(G\), the smallest size of a set of vertices meeting every edge. Then

Let \(G\) be a finite simple graph on \(n\) vertices with minimum degree \(\delta (G) \gt 0\) (so that \(G\) has no isolated vertices, and edge coverings exist). Then the matching number and the edge covering number of \(G\) satisfy

where \(\alpha '(G)\) is the largest number of edges in a matching of \(G\) and \(\beta '(G)\) is the smallest number of edges in an edge covering of \(G\).

This is the theorem of Gallai (1959).

Let \(G\) be a finite bipartite graph with vertex classes \(X\) and \(Y\), and suppose that \(G\) has minimum degree \(\delta (G) \gt 0\), so that every vertex is an endpoint of at least one edge. Then the independence number \(\alpha (G)\)—the greatest number of pairwise non-adjacent vertices—equals the edge covering number \(\beta '(G)\), the least number of edges in an edge covering of \(G\) (a set of edges meeting every vertex).

Let \(G\) be a finite simple graph. Then \(G\) is bipartite if and only if every subgraph \(H\) of \(G\) satisfies

where \(V(H)\) is the vertex set of \(H\) and \(\alpha (H)\) denotes the independence number of \(H\), that is, the size of a largest set of pairwise non-adjacent vertices of \(H\).

A finite simple graph \(G\) is bipartite if and only if, for every subgraph \(H\) of \(G\) whose minimum degree \(\delta (H)\) is positive, the independence number \(\alpha (H)\) — the greatest number of pairwise nonadjacent vertices of \(H\) — equals the edge covering number \(\beta '(H)\).

Let \(G\) be a finite simple graph, and write \(\alpha (G)\) for its independence number (the size of a largest set of pairwise non-adjacent vertices). Suppose \(G\) is connected and \(\alpha \)-critical, meaning that \(\alpha (G - e) \gt \alpha (G)\) for every edge \(e\) of \(G\). Then \(G\) has no cut vertex: for every vertex \(v\), the singleton \(\{ v\} \) is not a vertex cut, that is, it is not the case that \(\{ v\} \) is a proper subset of the vertex set whose deletion leaves the graph induced on the remaining vertices disconnected.

Let \(G\) be a finite connected simple graph that is \(\beta \)-critical, meaning that deleting any single edge strictly decreases its covering number \(\beta (G)\) (the least number of vertices meeting every edge). Then no single vertex is a cut vertex: for every vertex \(v\), the singleton \(\{ v\} \) is not a vertex cut, that is, removing \(v\) never leaves the graph disconnected.

Let \(G\) be a connected finite simple graph with \(\varepsilon \) edges, and let \(\beta (G)\) denote its covering number, the least number of vertices in a covering of \(G\). Then

Fix natural numbers \(k\) and \(l\), and say that \(n\) is a Ramsey bound for \((k,l)\) if every simple graph on \(n\) vertices contains either a clique on \(k\) vertices or an independent set on \(l\) vertices. If \(n \le m\) and \(n\) is a Ramsey bound for \((k,l)\), then \(m\) is also a Ramsey bound for \((k,l)\).

For every pair of natural numbers \(k\) and \(l\), there exists a natural number \(n\) with the following property: every simple graph on \(n\) vertices contains either a clique of size \(k\) or an independent set of size \(l\).

For natural numbers \(k\) and \(l\), let \(r(k,l)\) denote the Ramsey number, defined as the least \(n\) (equivalently, the infimum over all such \(n\)) for which every simple graph on \(n\) vertices contains either a clique of size \(k\) or an independent set of size \(l\). Then \(r(k,l)\) itself has this property: every simple graph on \(r(k,l)\) vertices contains a clique of size \(k\) or an independent set of size \(l\).

Let the Ramsey number \(r(k,l)\) denote the least natural number \(n\) such that every simple graph on \(n\) vertices contains either a clique on \(k\) vertices or an independent set on \(l\) vertices. Then for every integer \(l \ge 1\) one has \(r(1,l) = 1\).

For every integer \(k \ge 1\), the Ramsey number satisfies \(r(k, 1) = 1\); that is, \(1\) is the least number of vertices \(n\) for which every simple graph on \(n\) vertices contains either a clique of size \(k\) or an independent set of size \(1\).

For every integer \(l \ge 1\), the Ramsey number satisfies \(r(2, l) = l\). Equivalently, \(l\) is the least number of vertices \(n\) such that every simple graph on \(n\) vertices contains either an edge (a clique on \(2\) vertices) or an independent set of size \(l\).

Write \(r(k,l)\) for the Ramsey number: the least \(n\) for which every simple graph on \(n\) vertices contains either a clique of size \(k\) or an independent set of size \(l\). Then for every integer \(k \ge 1\),

For integers \(k \ge 2\) and \(l \ge 2\), the Ramsey numbers satisfy

where \(r(k, l)\) denotes the least number of vertices \(n\) such that every simple graph on \(n\) vertices contains either a clique on \(k\) vertices or an independent set on \(l\) vertices.

For natural numbers \(k, l \ge 2\), let \(r(k, l)\) denote the Ramsey number: the least \(n\) such that every simple graph on \(n\) vertices contains either a clique on \(k\) vertices or an independent set on \(l\) vertices. If both \(r(k, l-1)\) and \(r(k-1, l)\) are even, then

The cycle graph \(C_5\) on five vertices contains no clique of size \(3\); that is, no three of its vertices are pairwise adjacent.

Let \(C_5\) denote the cycle graph on five vertices, in which the vertices are arranged in a ring and each vertex is adjacent exactly to its two neighbours. Then \(C_5\) contains no independent set of three vertices; that is, no three of its vertices are pairwise non-adjacent.

Let \(r(3,3)\) denote the Ramsey number for the pair \((3,3)\): the least natural number \(n\) such that every simple graph on \(n\) vertices contains either three mutually adjacent vertices (a triangle) or three mutually non-adjacent vertices (an independent set of size \(3\)). Then

Consider the graph on the thirteen vertices \(\mathbb {Z}/13\mathbb {Z}\) in which two distinct vertices are joined by an edge exactly when their difference is a nonzero cubic residue modulo \(13\), that is, an element of \(\{ 1,5,8,12\} \). This graph contains no clique on three vertices: there is no triple of pairwise adjacent vertices, so the graph is triangle-free.

Let \(G\) be the graph on the thirteen vertices \(\mathbb {Z}/13\mathbb {Z}\) in which two distinct vertices are joined by an edge exactly when their difference is a cubic residue modulo \(13\), that is, an element of \(\{ 1,5,8,12\} \). Then \(G\) contains no independent set of five vertices: among any five vertices, some two are adjacent.

Let \(r(k,l)\) denote the Ramsey number, the least \(n\) such that every simple graph on \(n\) vertices contains either a clique of size \(k\) or an independent set of size \(l\). Then

Let \(P_{17}\) denote the Paley graph of order \(17\): its vertices are the elements of the field \(\mathbb {Z}/17\mathbb {Z}\), and two vertices are joined by an edge whenever their difference is a nonzero quadratic residue modulo \(17\) (that is, one of \(1, 2, 4, 8, 9, 13, 15, 16\)). Then \(P_{17}\) contains no clique on four vertices; equivalently, there is no set of four pairwise adjacent vertices.

Let \(G\) be the Paley graph of order \(17\): its vertices are the elements of the field \(\mathbb {Z}/17\mathbb {Z}\), and two vertices are joined by an edge exactly when their difference is a nonzero quadratic residue modulo \(17\) (that is, one of \(1, 2, 4, 8, 9, 13, 15, 16\)). Then \(G\) contains no independent set of size \(4\); equivalently, among any four vertices of \(G\) some two are adjacent.

Write \(r(4,4)\) for the least \(n\) such that every simple graph on \(n\) vertices contains either a clique on \(4\) vertices or an independent set of \(4\) vertices. Then \(r(4,4) \ge 18\).

For integers \(k, l \ge 1\), the Ramsey number \(r(k, l)\) — the least \(n\) such that every simple graph on \(n\) vertices contains either a clique on \(k\) vertices or an independent set on \(l\) vertices — satisfies

For every natural number \(n\), the number of simple graphs on the vertex set \(\{ 1, 2, \ldots , n\} \) equals \(2^{\binom {n}{2}}\), since a simple graph is determined by choosing which of the \(\binom {n}{2}\) possible unordered pairs of distinct vertices form edges.

For an integer \(k \ge 1\), let \(r(k,k)\) denote the Ramsey number: the least \(n\) such that every simple graph on \(n\) vertices contains either a clique of size \(k\) or an independent set of size \(k\). Then

Let \(k\) and \(l\) be positive integers, and let \(r(k,l)\) denote the associated Ramsey number. Then

Fix an integer \(m \ge 1\) of colours and integers \(k_1, k_2, \dots , k_m\) with \(k_i \ge 2\) for every \(i\), and let \(r(k_1, \dots , k_m)\) denote the multicolour Ramsey number: the least \(n\) such that every colouring of the edges of the complete graph \(K_n\) with \(m\) colours contains, for some colour \(i\), a complete subgraph on \(k_i\) vertices all of whose edges have colour \(i\). Then

where the \(i\)th summand is obtained from \(r(k_1, \dots , k_m)\) by decreasing the argument \(k_i\) by one.

For any natural numbers \(k_1, \ldots , k_m\), the multicolour Ramsey number satisfies

the right-hand side being the multinomial coefficient \(\binom {k_1 + \cdots + k_m}{k_1, \ldots , k_m}\).

For natural numbers \(k\) and \(l\), let \(r(k,l)\) denote the Ramsey number: the least \(n\) such that every simple graph on \(n\) vertices contains either a clique on \(k\) vertices or an independent set on \(l\) vertices. Then \(r(k,l) = r(l,k)\).

For an integer \(n \ge 1\), write \(r_n\) for the \(n\)-colour triangle Ramsey number: the least \(N\) such that every colouring of the edges of the complete graph \(K_N\) with \(n\) colours contains a triangle whose three edges all receive the same colour. Then

For every integer \(n \ge 2\), the \(n\)-colour triangle Ramsey number \(r_n = r(3, 3, \dots , 3)\) — the least \(N\) for which every colouring of the edges of the complete graph on \(N\) vertices with \(n\) colours yields a monochromatic triangle in some colour — satisfies

where \(e = \exp (1)\) and \(\lfloor \, \cdot \, \rfloor \) is the floor function.

Let \(r_3 = r(3,3,3)\) denote the three-colour Ramsey number for triangles, that is, the least \(n\) such that every colouring of the edges of the complete graph \(K_n\) with three colours contains a monochromatic triangle. Then \(r_3 \le 17\); equivalently, every \(3\)-edge-colouring of \(K_{17}\) admits three vertices whose three connecting edges all receive the same colour.

Let \(G\) and \(H\) be simple graphs on finite vertex sets, and let \(G[H]\) denote their composition (lexicographic product): the simple graph with vertex set \(V(G) \times V(H)\) in which \((u,v)\) is adjacent to \((u',v')\) exactly when \(uu' \in E(G)\), or else \(u = u'\) and \(vv' \in E(H)\). Writing \(\alpha (\cdot )\) for the independence number, the independence number of the composition satisfies

For positive integers \(k\) and \(l\), write \(r(a,b)\) for the Ramsey number: the least \(n\) such that every simple graph on \(n\) vertices contains either a clique on \(a\) vertices or an independent set of \(b\) vertices. Then, provided \(k \ge 1\) and \(l \ge 1\),

For every natural number \(n \ge 0\), the diagonal Ramsey number satisfies

where \(r(k, l)\) denotes the least number of vertices \(N\) such that every graph on \(N\) vertices contains either a clique on \(k\) vertices or an independent set on \(l\) vertices. (H. L. Abbott)

Let \(G\) be a finite simple graph and let \(T\) be a tree on \(m\) vertices. If every vertex of \(G\) has degree at least \(m-1\), so that the minimum degree satisfies \(\delta (G) \ge m-1\), then \(G\) contains a copy of \(T\); that is, there is an injective map from the vertices of \(T\) into those of \(G\) that sends every edge of \(T\) to an edge of \(G\), exhibiting \(T\) as a subgraph of \(G\).

Let \(T\) be a tree on \(m\) vertices, and let \(n\) be a natural number for which \(m-1\) divides \(n-1\). Writing \(K_{1,n}\) for the star on \(n+1\) vertices — the complete bipartite graph whose parts have sizes \(1\) and \(n\) — the two-colour generalised Ramsey number of \(T\) against \(K_{1,n}\) satisfies

Let \(T\) be a tree on \(m\) vertices, and let \(n \ge 1\). Then the generalised Ramsey number \(r(T, K_n)\) — the least integer \(N\) for which every colouring of the edges of the complete graph \(K_N\) with two colours contains either a copy of \(T\) in the first colour or a copy of the complete graph \(K_n\) in the second — is given by

(Erdős, 1970.) Let \(m \ge 1\), and let \(G\) be a finite simple graph that is \(K_{m+1}\)-free, i.e. contains no complete subgraph on \(m+1\) vertices. Then there exists a complete multipartite graph \(H\) on the same number of vertices such that \(G\) is degree-majorised by \(H\); that is, writing the degree sequences of \(G\) and \(H\) in nondecreasing order, each entry of \(G\)’s sequence is at most the corresponding entry of \(H\)’s. Moreover, if \(G\) and \(H\) have the same degree sequence, then \(G\) and \(H\) are isomorphic.

Let \(G\) and \(H\) be simple graphs on a common finite vertex set \(V\). If every vertex has at least as high a degree in \(H\) as in \(G\), that is \(d_G(v) \le d_H(v)\) for all \(v \in V\), then \(G\) is degree-majorised by \(H\).

Let \(V\) be a finite vertex set, let \(m \geq 1\), and let \(G\) be a simple graph on \(V\) that contains no clique on \(m+1\) vertices. Write \(T\) for the Turán graph \(T(|V|, m)\), the complete \(m\)-partite graph on \(|V|\) vertices whose parts differ in size by at most one. If \(G\) has exactly as many edges as \(T\), then \(G\) is isomorphic to \(T\).

Let \(G\) be a finite simple graph on \(n\) vertices with \(m\) edges. If \(n^2 \lt 4m\), then \(G\) contains a triangle, that is, three mutually adjacent vertices.

Let \(G\) be a finite simple graph that is not bipartite, with \(n\) vertices and \(m\) edges. If

equivalently \(m \gt \tfrac {(n-1)^2}{4} + 1\), then \(G\) contains a triangle, i.e. three pairwise adjacent vertices. (Erdős)

Let \(G\) be a finite simple graph with vertex set \(V\), write \(n = \left\lvert V\right\rvert \) for its number of vertices and \(d(v)\) for the degree of a vertex \(v\), and let \(m \ge 2\) be an integer. If

then \(G\) contains a copy of the complete bipartite graph \(K_{2,m}\).

Let \(G\) be a finite simple graph on a vertex set with \(n\) vertices, and let \(m \ge 2\) be an integer. If the number of edges of \(G\) satisfies

then \(G\) contains the complete bipartite graph \(K_{2,m}\) as a subgraph.

Let \(x_0, x_1, \dots , x_{n-1}\) be \(n\) points of the Euclidean plane \(\mathbb {R}^2\), and consider the unit-distance graph on them, whose edges join the pairs of points lying at distance exactly \(1\). Then the number of such edges is at most

Let \(G\) be a finite simple graph whose vertex set has \(n\) elements, and write \(e(G)\) for its number of edges. Let \(m \ge 1\) be an integer. If

then \(G\) contains the complete bipartite graph \(K_{m,m}\) as a subgraph.

Let \(n \ge 1\), and let \(r_n = r(3,\ldots ,3)\) be the \(n\)-colour Ramsey number for triangles. If \(S_1, S_2, \ldots , S_n\) partition the set \(\{ 1, 2, \ldots , r_n\} \) — that is, each \(S_i\) is a subset of \(\{ 1, \ldots , r_n\} \) and every integer \(k\) with \(1 \le k \le r_n\) lies in exactly one of the \(S_i\) — then for some \(i\) the part \(S_i\) contains integers \(x, y, z\) (not necessarily distinct) with \(x + y = z\).

The Schur number for three parts equals fourteen, \(s_3 = 14\). Equivalently, \(14\) is the least integer \(N\) with the property that every partition of \(\{ 1,2,\ldots ,N\} \) into three subsets has some subset containing elements \(x,y,z\) (not necessarily distinct) with \(x+y=z\).

For each integer \(n \ge 1\), the Schur numbers satisfy

where \(s_m\) denotes the least \(N\) such that every partition of \(\{ 1, 2, \ldots , N\} \) into \(m\) subsets has some part containing elements \(x, y, z\) with \(x + y = z\). Equivalently, \(s_n \ge 3 s_{n-1} - 1\).

For every integer \(n \ge 3\), the Schur number \(s_n\) satisfies

equivalently \(s_n \ge \tfrac {1}{2}\bigl(27\cdot 3^{\, n-3} + 1\bigr)\).

Let \(x_1, x_2, \ldots , x_n\) be points in the Euclidean plane \(\mathbb {R}^2\) whose set \(\{ x_1, \ldots , x_n\} \) has diameter exactly \(1\). Then the number of unordered pairs \(\{ x_i, x_j\} \) whose Euclidean distance satisfies \(d(x_i, x_j) \gt 1/\sqrt{2}\) is at most \(\lfloor n^2/3 \rfloor \).

For every natural number \(n\), there exist points \(x_1, x_2, \ldots , x_n\) in the Euclidean plane \(\mathbb {R}^2\) such that the set \(\{ x_1, x_2, \ldots , x_n\} \) has diameter exactly \(1\) and exactly \(\lfloor n^2/3\rfloor \) of the unordered pairs \(\{ x_i, x_j\} \) satisfy \(d(x_i, x_j) \gt 1/\sqrt{2}\), where \(d\) denotes Euclidean distance.

Let \(x_1, \dots , x_n\) be points of the Euclidean plane \(\mathbb {R}^2\) whose set \(\{ x_1, \dots , x_n\} \) has diameter exactly \(1\). Then the number of unordered pairs \(\{ i, j\} \) with \(i \ne j\) and \(\operatorname{dist}(x_i, x_j) = 1\) is at most \(n\); equivalently, the unit-distance graph on these points has at most \(n\) edges.

Let \(V\) be a finite vertex set, let \(m\) be a natural number, and let \(G\) be a simple graph on \(V\) that contains no clique on \(m+1\) vertices. Then the number of edges of \(G\) is at most the number of edges of the Turán graph \(T(\left\lvert V\right\rvert , m)\), the complete \(m\)-partite graph on \(\left\lvert V\right\rvert \) vertices whose parts differ in size by at most one.