information:extraction, structural:summarization
Infinite graphs

A further result, also commonly called Ramsey's theorem, applies to infinite graphs. In a context where finite graphs are also being discussed it is often called the "Infinite Ramsey theorem". As intuition provided by the pictorial representation of a graph is diminished when moving from finite to infinite graphs, theorems in this area are usually phrased in set-theoretic terminology.

Proof: The proof is by induction on n, the size of the subsets. For n = 1, the statement is equivalent to saying that if you split an infinite set into a finite number of sets, then one of them is infinite. This is evident. Assuming the theorem is true for n ≤ r, we prove it for n = r + 1. Given a c -colouring of the (r + 1) -element subsets of X, let a be an element of X and let Y = X \ { a }. We then induce a c -colouring of the r -element subsets of Y, by just adding a to each r -element subset (to get an (r + 1) -element subset of X). By the induction hypothesis, there exists an infinite subset Y of Y such that every r -element subset of Y is coloured the same colour in the induced colouring. Thus there is an element a and an infinite subset Y such that all the (r + 1) -element subsets of X consisting of a and r elements of Y have the same colour. By the same argument, there is an element a in Y and an infinite subset Y of Y with the same properties. Inductively, we obtain a sequence { a, a, a, …} such that the colour of each (r + 1) -element subset (a, a, …, a) with i (1) < i (2) < … < i (r + 1) depends only on the value of i (1). Further, there are infinitely many values of i (n) such that this colour will be the same. Take these a 's to get the desired monochromatic set.

A stronger but unbalanced infinite form of Ramsey's theorem for graphs, the Erdős–Dushnik–Miller theorem, states that every infinite graph contains either a countably infinite independent set, or an infinite clique of the same cardinality as the original graph.