# zbMATH — the first resource for mathematics

On the number of complete subgraphs contained in certain graphs. (English) Zbl 0116.01202
Let $$G$$ and $$\bar G$$ (the ”complement” of $$G$$) be graphs with the same vertices and without loops or multiple edges, such that every two distinct vertices are joined by an edge in exactly one of these graphs. $$C_k (G)$$ is the number of complete subgraphs of $$G$$ with $$k$$ vertices. Theorem 1 states that for every $$k \geq 3$$ and every $$n$$, there exists a $$G$$ with $$n$$ vertices such that $$C_k (G)+C_k (\bar G) < {n \choose k} 2^{1-{k \choose 2}}$$. Theorem 2 and 3 determine the maximum value of $$C_k (G)$$ as $$G$$ runs over (in the case of Theorem 2) all graphs with $$l$$ edges and (in Theorem 3) all graphs with $$n$$ vertices which do not possess a complete subgraph with $$l$$ vertices. Some unsolved related problems are mentioned.

##### MSC:
 05C30 Enumeration in graph theory
combinatorics