Skip to main content
4 of 4
added 328 characters in body
bof
  • 13.4k
  • 2
  • 43
  • 66

The mathematical questions have been answered by Fedor Petrov and Gerhard Paseman. My purpose is to offer a partial answer to the historical/bibliographical question suggested in parentheses at the the end; namely, that the same notion, or something closely related to it (being vague because I'm too lazy to read the paper in detail), can be found in:

K. Čulík, Applications of graph theory to mathematical logic and linguistics, in: Theory of Graphs and its Applications, Proceedings of the Symposium held in Smolenice in June 1963; Publishing House of the Czechoslovak Academy of Sciences, Prague; Academic Press, New York and London; pp. 13–20.

Čulík defines the number of completeness of a graph $G$, denoted by $\omega(G)$, as the smallest cardinal number of a collection of complete subgraphs covering all the edges and vertices of $G$. As a slight modification, let me define $\varepsilon(G)$ as the smallest number of complete subgraphs covering all the edges of $G$. (I'm sorry if $\varepsilon$ is a bad choice of notation; I don't know if there is any Greek letter that does not already have a reserved meaning in graph theory.) If $\overline G$ denotes the complement of $G$, it is easy to see that $$\delta(G)=\varepsilon(\overline G).$$ The answers to the mathematical questions for infinite and finite graphs follow from the fact that $\varepsilon(G)\le|E(G)|$ in all cases, while $\varepsilon(G)=|E(G)|$ if $G$ is triangle-free. Thus, if $G$ is an infinite graph, then $\delta(G)=\varepsilon(\overline G)\le|E(\overline G)|\le|V(G)|$; if $G$ is a finite graph with $n$ vertices and $\overline G$ is bipartite with $\left\lfloor\frac{n^2}4\right\rfloor$ edges, then $\delta(G)=\varepsilon(\overline G)=|E(\overline G)|=\left\lfloor\frac{n^2}4\right\rfloor$.

The papers citing Čulík's paper may also be relevant, but I don't have time to look into them.

bof
  • 13.4k
  • 2
  • 43
  • 66