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?

This is trivial with Turan's theorem, it tells us the maximum number of edges a graph without an induced $K_4$ can have is the number of edges in the Turan graph $T(10,3)$
In this case the Turan graph is the complete multipartite graph $K_{4,3,3}$. This graph has $45-6-3-3=33$ edges. So in fact it is true with as little as $34$ edges.
