We examine the following problem for simple unlabelled graphs: for a fixed n, find the graph H with the greatest number of edges such that for any graph G on n vertices, H is a subgraph of either G or the complement of G. No theoretical solution has been found, so this problem is attacked computationally, with published source code. Results were calculated and are described up through n=11, with partial results beyond.
The most well-known family of problems in Ramsey theory can be phrased as asking for which n and r it is true that for all graphs G on n nodes, the complete graph Kr is a subgraph of either G or the complement of G (written Gc). The Ramsey numbers are defined as the sequence of n at which this first holds for r = 1, 2, 3, …. To make phrasing less awkward, I introduce the term ingraph: H is an ingraph of G iff H is a subgraph of either G or Gc. So, the fourth Ramsey number is 18 because every graph on 18 nodes has K4 as an ingraph. I will call K4 a universal ingraph for 18.
Here we consider a generalization of this question where we relax the condition that the ingraph must be complete. We seek the densest graph (meaning most number of edges) which is a universal ingraph for n. The complete graph on r nodes has r·(r+1)/2 edges, which skips a lot of possibilities. For example, perhaps there is a universal ingraph for 17 which extends K3 and includes some but not all of K4. Or maybe there are universal graphs which do not resemble complete graphs at all, and perhaps such a graph for 17 may have even more edges than K4. Indeed, the latter will turn out to be the case.
An equivalent formulation can be made in terms of graph coloring. Color all edges on n nodes either red or blue. Then we seek an H such that any such colored graph contains a monochromatic copy of H. With this formulation, we can immediately see one natural generalization for future work: increasing the number of colors.
I tried to attack this problem theoretically, and then heuristically. These efforts did not bear fruit. So, instead, I wrote software to exhaustively enumerate graphs (up to symmetry) at each n and search for universal ingraphs; and also to attempt to construct counter-examples to candidate universal ingraphs. With this tooling, I was able to compute the densest universal ingraph (DUI) for n up to 11 and get partial results up to 13.
The software is written in Rust and published on GitHub: https://github.com/galenhuntington/ingraphs
| n | e |
|---|---|
| 1 | 0 |
| 2 | 1 |
| 3 | 2 |
| 4 | 2 |
| 5 | 3 |
| 6 | 5 |
| 7 | 6 |
| 8 | 7 |
| 9 | 8 |
| 10 | 10 |
| 11 | 12 |
| 12 | 14? |
| 12 | ≤17 |
The values of e (most number of edges) for each n are summarized in the table to the right. The following sections provide details for each of these.
This is a trivial case because a graph of 1 node can have no edges, and so the DUI is an empty graph.
This is also fairly trivial. We can see that K2 is an ingraph of the only two possible graphs, the empty graph and the complete graph (which has one edge). Thus this is our DUI:
The chromatic formulation quickly shows us that the above is a DUI. If K3 (a triangle) is colored with 2 colors, at least two edges must be of the same color, and they meet at a point.
Interestingly, the DUI for 4 is the same as the DUI for 3 above. This may be the only case where increasing n does yield a denser DUI.
The DUI for 4 is also linear, with one edge more:
At 6, the DUI is a square with an edge coming out of one vertex, adding two edges to the previous DUI:
This is the first case where the DUI has more than one edge more than for the previous n.
Here we add another edge out of the same vertex:
The DUI for 8 is a domino shape, with 7 edges:
This is not an extension of the previous graph, the first case where this has happened.
At 9, things get more complex, and it is the first time we do not have a unique solution. To describe the results, first consider this graph (coloring described below), which I call 9X:
This is the domino shape in the previous DUI except with one corner node “cloned”.
It turns out this is almost a universal ingraph for 9. Out of the 274,668 distinct graphs (up to symmetry), there is exactly one which it fails to be an ingraph of. Here is the exception:
This graph is not planar and may be hard to make sense of, so I have colored edges that cross others to help visually distinguish them. It has 18 edges, which form six triangles, and is highly symmetric, more than may be clear in the above drawing. It can be defined by labelling its points a,b for a, b = 0, 1, 2, and drawing an edge between two points if either of these two coordinates are equal. From this definition, we see there is an automorphism taking any triangle to any other, in any orientation. It is also isomorphic to its own complement, as can be seen by mapping a,b to ((a+b) mod 3),((a+2b) mod 3). The graph can be symmetrically rendered in four dimensions: plot the point a,b in six-dimensional Euclidean space at (a0, a1, a2, b0, b1, b2) where xr=1 if x=r else 0, and note that the induced diagram lies entirely in the four-dimensional subspace defined by a0+a1+a2=1 and b0+b1+b2=1.
Thus the graph 9X only barely fails to be a DUI for 9. However, we can get a universal ingraph by removing any of the four edges colored red above (or a blue one, since the two edges are symmetrically equivalent to the two nearby red ones). With some straightening out, that yields the following four DUIs:
Up until now, all DUIs have been embeddable in the square lattice. This is true for all but the last of the above four. However, the exception can be embedded in the cubic lattice.
The first graph is asymmetric. All other DUIs so far besides the empty graph have exhibited some symmetry.
There are two DUIs for 10, with 10 edges:
The first is of course one edge more than 9X. These two graphs, as drawn, may not look similar, but in fact they are closely related in two different ways. If either of the blue edges in the first graph is disconnected from their shared node and connected instead to the lonely point on the left, one gets the second graph.
There is a unique DUI for 11, with 12 edges. This graph is not planar, and there are various ways to draw it. Here is one rendering, where I vary the edge width to indicate a third dimension:
This graph is not an extension of either of the DUIs for 10. However, it does contain 9X as a subgraph.
This drawing illustrates the graph‘s two symmetries (a symmetry group of size 4). It can be mirrored upside-down, and also along the axis perpendicular to the page, by switching the two nodes that are off the plane of the page.
The graph can also be thought of as the edges of a cube, except with one edge connecting a point to its direct opposite rather than the adjacent point, which when flattened looks like the left:
It can similarly be drawn as a straight “triomino” with two extra edges, as on the right. In both of these renderings, however, the symmetries are less evident.
While it is not exhaustively proven, evidence suggests that there is a unique DUI for 12 with 14 edges. It can be drawn as the previous graph plus a new node connected to two existing nodes. This is perhaps most cleanly diagrammed by building on the flattened cube rendering:
Computation has shown this is the only possible universal ingraph with 14 edges. I did an extensive search for counterexamples to it being a universal ingraph, including checking all graphs on 12 vertices with exactly 33 edges (that is, half the possible edges), where a counterexample would be expected to be found, without finding any.
This graph extends both DUIs for n=10, as well as that for n=11. It is asymmetric; each new edge kills one of the mirror symmetries.
As of this writing, computations have gotten us down to one possible DUI with 17 edges. If it holds up, that is a jump of (at least) 3. However, the counter-example search space is huge and only a small part has been explored, so it would be premature to say there is a good chance this is a DUI. This graph, like n=11, has two symmetries. It is an extension of that graph and those for n=10, but not of the previous one.
The current algorithms take time roughly linear in the number of graphs. This number grows quickly, with about 300× as many graphs at 13 than at 12, and 575× more than that at 14. Even if we throw a lot of compute at this problem, we will quickly hit limits.
What would help is theoretical results that reduce the search space.
Where is this going? While many DUIs are not extensions of the previous one, there does seem to be eventual convergence. If so, it means that an infinite graph is being slowly drawn for us, edge by edge. But what pattern it is creating is mysterious.
Perhaps most remarkable is how “square” all of the DUIs are. In fact, not a single DUI contains a triangle (K3). Indeed, an even stronger property holds: every DUI exhibits a 2-coloring (coloring the nodes red and blue such that no same-colored nodes are adjacent). It is premature to conjecture that these properties will always hold. After all, from early results one might have conjectured that every DUI for n+1 extends the one for n, or that it is always unique, or that every DUI can be embedded in the square lattice, or in the cubic lattice, or that all DUIs are planar.
An interesting question is the growth rate of e vs. n. At first, it looked nearly linear, but then we start seeing jumps of 2. Will the rate increase continue? The total number of edges is quadratic in n, which is an upper bound.
We may not get a simple method for finding DUIs, but one thought is that there might be a sub-problem which is more tractable. For instance, perhaps there is a readily computable characteristic function on graphs which measures its rough likelihood of being an ingraph. It may not be practical to find the graph with the largest value, but we could still derive results, such as why square shapes are common, if such a function existed.
Much as in Ramsey theory, there are many directions in which this problem can be generalized. As mentioned, with the chromatic interpretation, we can add more colors. There are also more complex generalizations, such as “super-graphs” where there are planes on three nodes instead of edges on two. I have not explored any of these.
Finally, pessimistically, this problem may also share the difficulty of Ramsey theory. As of 2025, the value of the fifth Ramsey number is still not known. Perhaps finding DUIs will also never be practical beyond a certain, small, number. After all, it too is subject to the exponential explosion in the number of graphs. Well, I hope not.