Let $G$ be a simple graph on $10$ vertices and $38$ edges. Prove that $G$ contains $K_4$ as an induced subgraph. Let $G$ be a simple graph on $10$ vertices and $38$ edges. How do I prove that $K_4$ is the induced subgraph of G?

Hint: There are only $7$ edges missing from $K_{10}$. Each missing edge can prevent up to $28$ different 4-vertex sets from inducing a $K_4$. How many 4-vertex sets are there?
