Definition:Induced Subgraph

Definition

Let $G = \left({V \left({G}\right), E \left({G}\right)}\right)$ be a graph.

Let $V' \subseteq V$ be a subset of vertices of $G$.

The subgraph of $G$ induced by $V'$ is the subgraph $G' = \left({V' \left({G'}\right), E' \left({G'}\right)}\right)$ of $G$ that:

• $G'$ has the vertex set $V'$;

• For all $u, v \in V'$, $e = uv \in E \left({G}\right)$ iff $e \in E' \left({G'}\right)$.

That is, it contains all the edges of $G$ that connect elements of the given subset of the vertex set of $G$, and only those edges.