# Must a complete subgraph be induced?

If we had some $K_n$ subgraph where $K_n \subseteq G$, must the complete subgraph $K_n$ be an induced subgraph from $G$? In other words, can we create a situation where we remove vertices from a simple graph $G$ to obtain some complete subgraph where the subgraph was not complete when it was a part of $G$?

## 2 Answers

Every complete subgraph $K_n$ contained in a graph $G$ can be considered as an induced subgraph of $G$. Note that, by definition, an induced subgraph is formed from a subset of the vertices of the original graph along with all of the edges connecting pairs of vertices in that subset.

The subgraph $G(V')$ induced by $V' \subseteq V$ consists of $V'$ and all edges incident to nodes of $V'$.

If a subgraph $G' = (V', E')$ is complete, then $G(V')$ can not possibly contain any edges $G'$ does not; we have $G' = G(V')$.