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$?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
0
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.
answered Oct 20, 2016 at 10:01
$\begingroup$
$\endgroup$
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')$.
