Infinite Monochromatic Cliques in Colored Countable Graphs

From Colored Pairs to a Monochromatic Clique

A finite coloring of the edges of an infinite complete graph may look complicated: the colors can be assigned without any repeating pattern or apparent structure. The infinite Ramsey theorem for pairs says that this complexity cannot continue on every infinite set of vertices. Some infinite set has all its pairs assigned the same color. In graph language, that set is an infinite monochromatic complete subgraph.

Throughout, a graph is simple: it has no loops or multiple edges. For a vertex set \(X\), the complete graph on \(X\) has every unordered pair of distinct vertices as an edge. We write its edge set as \(\binom{X}{2}\). A finite edge-coloring with \(r\) colors is a function \(c:E(G)\to [r]\), where \([r]=\{1,\ldots,r\}\) and \(r\) is a positive integer. The coloring need not be proper: adjacent edges are allowed to have the same color.

The word “clique” concerns adjacency: every two distinct vertices in the set must be joined. “Monochromatic” adds a condition on those edges. The conclusion is stronger than finding infinitely many edges of one color, since those edges must fit together as all pairs within one infinite vertex set.

The Pair-Theorem Application

We use the infinite Ramsey theorem for pairs, established earlier in the course. In the form needed here, it states that for every positive integer \(r\), every function \(f:\binom{\mathbb{N}}{2}\to [r]\), where \(\mathbb{N}=\{1,2,3,\ldots\}\), has an infinite subset \(I\subseteq\mathbb{N}\) and a color \(a\in[r]\) such that \(f(\{i,j\})=a\) for every pair of distinct \(i,j\in I\).

Proof. Let \(G\) be a countably infinite complete graph, let \(V(G)=\{x_1,x_2,\ldots\}\) be an enumeration without repetitions, and let \(c:E(G)\to[r]\) be its edge-coloring, for some positive integer \(r\). Define a coloring \(f\) of pairs of positive integers by \(f(\{i,j\})=c(x_ix_j)\) whenever \(i\ne j\). This is defined for every pair because \(G\) is complete. By the infinite Ramsey theorem for pairs, there are an infinite set \(I\subseteq\mathbb{N}\) and a color \(a\in[r]\) such that \(f(\{i,j\})=a\) for all distinct \(i,j\in I\). Set \(Y=\{x_i:i\in I\}\). Since the enumeration has no repetitions and \(I\) is infinite, \(Y\) is infinite. Every pair of distinct vertices in \(Y\) is an edge of \(G\), and for \(i,j\in I\) its color is \(c(x_ix_j)=f(\{i,j\})=a\). Thus \(Y\) induces an infinite complete subgraph all of whose edges have color \(a\). \(\square\)

The countability assumption is used to index the vertices by the positive integers. No particular order is required: any enumeration without repetitions gives the pair-coloring to which the theorem applies. Completeness matters because it ensures that every pair in the selected set is an edge and therefore has a color.

What the Conclusion Does—and Does Not—Specify

The theorem guarantees that some color has an infinite clique. It does not allow us to prescribe the color in advance. For instance, in the parity-of-the-gap coloring, the even positive integers give a red infinite clique, while the odd positive integers also give a red infinite clique: the difference between \(2a+1\) and \(2b+1\), for \(a<b\), is \(2(b-a)\), which is even. This example has an explicit red clique, but a general coloring need not make a particular named color the one selected by the theorem.

Nor does the theorem promise that an infinite clique appears among the first \(N\) vertices for some fixed \(N\) that works for every coloring. Its conclusion concerns an infinite vertex set. The earlier finite Ramsey existence result is about finding finite monochromatic complete subgraphs in sufficiently large finite complete graphs; the present application instead uses the infinite theorem for pairs to select a single infinite set on which every pair has the same color.

Proof. Removing the finite set \(F\) from the infinite set \(Y\) leaves an infinite set: if \(Y\setminus F\) were finite, then \(Y=(Y\setminus F)\cup(Y\cap F)\) would be a union of two finite sets and therefore finite, a contradiction. Every two distinct vertices in \(Y\setminus F\) were already in \(Y\), so they are adjacent and their edge has the same color as before. Thus \(Y\setminus F\) is an infinite monochromatic clique. \(\square\)

This corollary is useful when a finite number of vertices are excluded by an additional condition. The color remains fixed because the selected set is only being reduced; no edges among its remaining vertices change color.

Common Pitfall

A frequent error is to mistake one small arithmetic calculation for the general pair calculation. In the parity-of-the-gap example, someone might claim that the edge \(2\,6\) is blue because “\(6-2=3\), which is odd.” The subtraction is wrong: \(6-2=4\), and \(4\) is even, so the edge is red. More importantly, a proof of a monochromatic clique must check an arbitrary pair from the proposed infinite set. For the even vertices, that check is \(2b-2a=2(b-a)\), which is even for every pair of positive integers \(a<b\).

A second distinction is between a color class of edges and a monochromatic clique. Infinitely many edges of one color alone do not show that their endpoints form a clique of that color: the necessary condition is that every pair in one infinite vertex set has that color. The pair theorem supplies exactly this stronger, coordinated conclusion.