Skip to main content
2 of 4
added 100 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.

bof
  • 13.4k
  • 2
  • 43
  • 66