An important problem in graph theory is to find the number of complete subgraphs of a given size in a graph. If the graph is very large, it is usually only possible to obtain upper bounds for these numbers based on the numbers of complete subgraphs of smaller sizes. The Kruskal–Katona bounds are often used for these calculations. We investigate these bounds in specific cases and study how they might be improved.

Introduction

Graph theory has many interesting problems that lend themselves to computer investigation. Mathematica has many graph theory functions that can enable these investigations. We shall introduce the reader to Mathematica’s graph theory capability while investigating a problem in extremal graph theory. Extremal graph theory tries to find graphs satisfying certain extreme properties—for example, having the most triangles for a fixed number of edges.

We first introduce some basic graph theory concepts and show how to represent them in Mathematica. Formerly, most graph theory functions were contained in the Combinatorica package; however, this graph theory functionality has, for the most part, been absorbed by the main program, making it unnecessary to load this package.

Graph Theory Basics

A finite graph consists of two finite sets, and . The elements of the set are called vertices and the elements of the set consist of (unordered) pairs of vertices called edges. We often write . A graph is called a subgraph of graph if and ; that is, if each vertex in the subgraph is also a vertex in the graph and each edge of the subgraph is also an edge of the graph .

Graphs are often depicted as points (the vertices) and line segments (the edges) that join pairs of vertices in . Thus, to draw the graph consisting of the five labeled vertices and with edge set being all pairs of vertices, we enter the following command.

This graph is known as the complete graph on five vertices and denoted by .

In general, denotes the complete subgraph on vertices, that is, the graph with vertex set and edge set consisting of all pairs of elements of .

The complement of the graph is the graph having the same set of vertices and whose edges are exactly those pairs of vertices of that do not belong to . Thus, the graph complement of the complete graph has no edges at all.

Mathematica can also add vertices to an already existing graph. This adds two vertices labeled and to the graph .

This is how to add edges to graph . (The symbol “” can be entered from the keyboard using the Esc key; press Esc, type u and e, then press Esc again.)

Vertices and edges can be deleted with the commands and .

Another useful operation, , contracts a set of vertices into one vertex. For example, this contracts the graph by contracting the vertices labeled and into a single vertex.

The Number of Complete Subgraphs of a Graph

An important problem in graph theory is to find the number of complete subgraphs (or cliques) of a graph. For example, find the number of cliques of a certain size in a large social network graph. Here, the people are the vertices, an edge joins two people who know each other and a clique consists of people who all know each other; that is, they form a complete subgraph.

There is a dual version of this problem, equally important, that asks for the number of independent sets of a graph. A set of vertices is independent in the graph if there are no edges of connecting the vertices in the set. (Clearly, a set of vertices of is independent if and only if they form a complete graph in the complement of .)

We consider next how to compute the number of complete subgraphs exactly for small graphs and how one might obtain useful upper bounds for larger graphs.

Given , it is easy to determine how many complete subgraphs there are having, say, four vertices; the answer is the number of ways to choose four of the seven vertices, since for each such choice, all edges between the chosen vertices are also present in the original graph. The number of ways to choose four out of seven objects is just the binomial coefficient .

However, if the graph is not a complete graph, it is not so easy to determine how many complete subgraphs of a certain size it contains. We turn to this problem next.

Consider the graph previously defined.

Suppose we want to know how many subgraphs contains. We start with the list of its vertices.

Next, we form the set of all subsets of size four of this set.

Here is an example of a subset of vertices that generates a complete graph in .

We now wish to repeat this calculation for all the subsets of size four.

Finally, we count the number of times occurs in .

Let be the number of complete subgraphs with vertices contained in the graph . The following program implements .

Let us count the number of times , and occur in the graph ; that is, we calculate , and .

Bounding the Number of Complete Subgraphs of a Graph

Suppose we know that a certain graph satisfies . Can we determine the maximum of ? Surely, can have no subgraphs; that is, , as in this example.

However, the example has been shown to have 19 subgraphs and 10 subgraphs.

In fact, we have shown in a joint paper [1] that for all graphs with , the maximum value of is 10.

The following definition, due to Bollobás [2], is useful in what follows.

Definition

If , then is the maximum number of subgraphs that a graph can have if the number of its subgraphs is less than or equal to .

Thus, using this notation, we have shown in [1] that .

A Closely Related Problem

Suppose now that the number of triangles a graph can have is fixed and we want to determine the graph with the fewest edges that can have that many triangles.

For example, suppose we want a graph having 23 triangles with the fewest possible edges. Our intuition is to look for graphs that are “tightly packed,” that is, as close to complete graphs as possible. has 20 triangles and has 35. So let us start by adding a vertex to and then add three edges from to three of the vertices of . This adds new triangles.

That shows that a graph with 23 triangles can be gotten with just 18 edges. Is there a graph with fewer edges that has 23 subgraphs?

The next theorem is due to Erdös and Hanani (see [3]).

Theorem

If the number of edges is , then since , the theorem says that ; that is, the maximum number of subgraphs in a graph with 18 edges is 23.

Is there a graph with fewer edges and 23 triangles? To answer this question, we can use the Erdös–Hanani theorem to compute the various maximum numbers of triangles with fewer edges. The program gives the maximum number of triangles for a given number of edges, as determined by the Erdös–Hanani theorem; the table computes these values for edge numbers between three and 18.

We see from the table that there is no graph with fewer than 18 edges having 23 triangles. Hence the fewest edges needed to produce a graph with exactly 23 triangles is indeed 18.

The Kruskal–Katona Bound

If we specify the number of triangles rather than the number of edges a graph can have, computing the maximum numbers of larger complete graphs is not as simple as in the previous section. Exact maximum numbers are not known in most cases, only upper bounds.

A well-known theorem of extremal graph theory (proved independently by Kruskal [4] and Katona [5]) can provide an upper bound for , given , . In fact, the Kruskal–Katona result is for more general objects than graphs, but we will only be using it for graphs and only when ; that is, we specify how many triangles a graph can have and want to bound for some .

Theorem

For example, if the number of triangular subgraphs of is , then the Kruskal–Katona upper bounds for and are and .

To use this theorem in Mathematica, we first need to express as the binomial sum, . Given , the function finds the numbers , , .

Next, we define the functions and , the Kruskal–Katona upper bounds for and , given that .

Here are the results for 19 triangles.

Thus, and .

Here again is the graph with 19 triangles. It has 10 subgraphs and two subgraphs.

As mentioned, we proved in [1] that and .

Finding exactly is often very difficult and results are not known in most cases. However, if there is a graph with triangles, with (the Kruskal–Katona bound), then . Complete graphs are obvious examples. Also, as remarked in [2], if the number of triangles , we define the graph by adding to a single vertex and edges joining to vertices of ; then (the Kruskal–Katona bound). For example, suppose . We construct such a graph, .

Thus, and .

Next, we find those numbers of triangles for which this construction works; that is, the third entry in their binomial representation is 0.

Also, it is not difficult to see that if , the Kruskal–Katona bound is the same as for (since for ). So the list of the numbers of triangles for which is known can be expanded. Here are the known values for the first 100 positive integers.

This leaves the following numbers of triangles up to 100 still unknown.

We have in fact settled (see [1]) the cases (where , respectively). We add these cases to the list of the known values.

And these are the unknown values of for .

We had started listing the integer sequence (see [6]), and the preceding results can be used to add to this sequence; for example, the first term of the sequence, (when there are four triangles allowed, the graph has at most one ); the sequence continued up to . Since we now know the consecutive values up to , we can add four more consecutive values: , , , . Our conjecture in the next section implies that . Other selected values of the sequence can obviously also be obtained, given that we know so many of the first 100 cases.

Almost Complete Graphs and Turan Graphs

We have used complete graphs in building the maximal examples. However, even if we remove an edge from a complete graph, the number of subgraphs in this new graph gr1 is the same as the Kruskal–Katona bound based on the number of subgraphs (calculated by ), as the following computation shows. (This can also be established with a simple argument that we omit.)

In fact, even if we remove several edges from a complete graph, as long as they share a common vertex, the number of subgraphs in the resulting graph and the Kruskal–Katona bound (based on the number of subgraphs) remain the same, as the reader can easily check with Mathematica. However, if we remove two edges that do not share a common vertex, this is no longer the case, as the following computations show.

This time, the number of subgraphs is one less than the upper bound! These graphs are also Turan graphs. The Turan graph is the graph formed by partitioning a set of vertices into subsets with sizes as equal as possible (differing by at most 1) and connecting two vertices by an edge if and only if they belong to different sets of the partition. The built-in Mathematica function draws this graph. For example, partitions the vertices into the subsets , , ; the edge is omitted since it would connect vertices in the same subset, ; is omitted since it would connect vertices in the same subset .

The graphs are especially interesting to us as they are the same as the graphs , defined before. It may not be immediately apparent that is the same graph as ; however, if we chose the right for the Turan graph, it becomes rather obvious.

In addition, can always be used to check.

Therefore, for the Turan graph , the actual number of subgraphs is just one less than the Kruskal–Katona bounds! Do these graphs provide the true maximum values of subgraphs based upon the number of their triangles? We conjecture below that they do for . In addition, it is not hard to show that the number of triangles in is . (This follows because the vertex sets of are , , , , …, ; then consider all possible ways of choosing three elements from these sets without choosing two elements from the same set.) This expression can be simplified.

The sequence of these triangle numbers for the graphs is the same (with an offset) as the sequence A000297 in [7]. (We recently added a comment to this entry that mentions this.)

Conjecture

If , the Turan graph has the maximum number of subgraphs for any graph with triangles.

Finding Maximal Examples

Mathematica has a large database of graphs accessible with the function .

We wish to find maximal examples, that is, graphs that have the greatest number of subgraphs for their number of triangles. We make this precise with the following definition. A graph is a -maximal graph with respect to subgraphs if it has the greatest number of subgraphs for any graph with the same number of subgraphs (triangles) as . We believe that these -maximal graphs are “tightly packed” and thus have a relatively small number of vertices given their number of triangles. Suppose first we wish to find all the -maximal graphs with exactly nine triangles. The Kruskal–Katona bound is three.

However, the maximal number of subgraphs is really two, that is, (see [1]). We first look for examples in the set of nonisomorphic graphs with six vertices, that is, subgraphs of .

Here is the first such graph.

We apply to each entry to get the graphs themselves but suppress the large output.

Within those, we next search for graphs with nine triangular subgraphs. There is only one.

We attach labels to the vertices of this graph for later use.

This graph has two subgraphs.

Hence is a -maximal example (see [1]).

This graph embedding is also extremal in another way; see [8].

We search for examples in the set of graphs with seven vertices, using the command , which lists all non-isomorphic graphs with seven vertices. (If , only lists some of the graphs with vertices). has 1044 entries, so the result is not immediate.

There are 35 examples of graphs with seven vertices and nine triangular subgraphs.

To see the individual graphs, we use Mathematica’s built-in function , where, in addition to the graph, the number of subgraphs of the graph is listed.

We suspect that one of the -maximal graphs in is really a simple modification of the single -maximal graph with six vertices found in ; that is, the graph plus an edge. (We obviously do not want to add a triangle!) Stepping through the , graph number 22 is easily seen to be that graph.

We then add the edge to the graph found in and finally, use to verify that they are indeed isomorphic.

Next, suppose we want to find the -maximal graphs with 19 triangles. Although has triangles, if we remove even one edge from , the resulting graph has only 16 triangles! Hence, there are no subgraphs of with exactly 19 triangles. However has triangles; thus it is reasonable to search for examples.

Sometimes there are hidden edges in graph drawings in Mathematica; the graph in the middle is a case in point (the edge from the center top to center bottom vertices cannot be seen). We therefore redraw the graphs, setting the option .

We now ask for the number of subgraphs and the number of subgraphs in these graphs.

Also, all three graphs have the same number of edges, 17.

Thus, we have found three examples of graphs that illustrate our result of [1], that .

We now ask what is the maximal number of subgraphs in a graph with 25 vertices. We again search for graphs with seven vertices and 25 triangles.

The one example we have found has 16 subgraphs, and the Kruskal–Katona bound for subgraphs is 17.

We investigate this graph further.

This is the Turan graph ; edges and are missing from . This can also be seen with the function.

Since this is one of the Turan graphs and we have conjectured that they are -maximal, we believe we have found a -maximal example with 25 triangles.

Another example: Suppose we have a graph with 29 triangles. The Kruskal–Katona bound is 22.

A search in yields no graphs with 29 triangles. If we search in , we find one graph with 29 triangles. It has 16 subgraphs.

So it looks like the most subgraphs we can find for a graph with 29 triangles is 16. We can do better! For 26 triangles, since , the Kruskal–Katona bound is . Thus, if we add vertices and to and connect them to four and three vertices of , respectively, we get a graph with 29 triangles and 20 subgraphs.

The graph has eight vertices, but it did not show up in , which has only 289 out of 12346 possible graphs. contains all 1044 graphs with seven vertices.

A Larger Example

We have looked at examples with relatively few vertices, and these examples might give the impression that the Kruskal–Katona bounds do not differ significantly from the real values—so why expend so much effort trying to improve them? We construct a larger example to show that the difference can be quite large.

Here is another example.

The Kruskal–Katona bound, however, usually yields more than twice as many subgraphs! More extreme examples can easily be constructed.

Conclusion

There have been some efforts to improve the Kruskal–Katona bounds in the case of graphs (see, for example [1] and [9]); however these have had very limited success. We feel that not enough insight into this problem has been gained and that perhaps by using computer experiments, conjectures can formulated and then proved to advance our knowledge in this area. For example, if we knew that a maximal example with 19 triangles must occur in a graph with seven vertices, our search of would be sufficient to prove that the maximum number of subgraphs a graph with 19 subgraphs can have is 10. We succeeded in proving this result in [1] without using computers, but only with a great deal of effort.

To read more on using Mathematica’s graph theory capability to investigate other maximal problems in graph theory, see [10] and [11].

Acknowledgement

I wish to thank the editor, whose sage advice substantially improved this paper’s programing and content.

References

[1]	R. Cowen and W. Emerson, “On Finding ,” Graph Theory Notes, New York Academy of Sciences, 34, 1998 pp. 26–30. www.researchgate.net/publication/287991696_On_Finding_k4k3_x.
[2]	B. Bollobás, “Relations between Sets of Complete Subgraphs,” Proceedings of the Fifth British Combinatorial Conference, Aberdeen, 1975 pp. 79–84. www.researchgate.net/publication/268543809_Relations_between_sets_of_complete_subgraphs.
[3]	P. Erdös, “On the Number of Complete Subgraphs Contained in Certain Graphs,” Publications of the Mathematics Institute of the Hungarian Academy of Sciences, 7, 1962 pp. 459–464.
[4]	J. Kruskal, “The Number of Simplices in a Complex,” Mathematical Optimization Techniques (R. Bellman, ed.), Berkeley: University of California Press, 1963 pp. 251–278.
[5]	G. Katona, “A Theorem of Finite Sets,” The Theory of Graphs (P. Erdös, ed.), Budapest: Akadémia Kiadó, 1968 pp. 187–207.
[6]	N. J. A. Sloane. The Online Encyclopedia of Integer Sequences. oeis.org/A020917.
[7]	N. J. A. Sloane. The Online Encyclopedia of Integer Sequences. oeis.org/A000297.
[8]	E. W. Weisstein. “Graham’s Biggest Little Hexagon” from MathWorld—A Wolfram Web Resource. mathworld.wolfram.com/GrahamsBiggestLittleHexagon.html.
[9]	A. Frohmader, “A Kruskal–Katona Type Theorem for Graphs.” arxiv.org/abs/0710.3960.
[10]	E. W. Weisstein. “Cage Graph” from MathWorld—A Wolfram Web Resource. mathworld.wolfram.com/CageGraph.html.
[11]	E. W. Weisstein. “Degree-Diameter Problem” from MathWorld—A Wolfram Web Resource. mathworld.wolfram.com/Degree-DiameterProblem.html.
R. Cowen, “Improving the Kruskal–Katona Bounds for Complete Subgraphs of a Graph,” The Mathematica Journal, 2018. dx.doi.org/doi:10.3888/tmj.20-6.

About the Author

Robert Cowen is Professor Emeritus in Mathematics, Queens College, CUNY. He does research in logic, combinatorics and set theory. He taught a course in Mathematica programming for many years, emphasizing discovery of mathematics, and is currently working on a text on learning Mathematica through discovery with John Kennedy. His website is sites.google.com/site/robertcowen.

Robert Cowen
16422 75th Avenue
Fresh Meadows, NY 11366
robert.cowen@gmail.com