Problem Detail: 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$?
Asked By : jchaykow
Answered By : Mario Cervera
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/64880 Ask a Question Download Related Notes/Documents
