1
$\begingroup$

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$?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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')$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.