# Induced subgraph

From Encyclopedia of Mathematics

*of a graph $G $*

The graph $G[S]$ having as vertex set a given subset $S$ of the vertex set of $G$ and as edges between $x,y \in S$ all edges that exist between $x,y$ in $G$. If $G$ has an incidence matrix $I$, then the incidence matrix $I[S]$ consists precisely of those rows of $I$ corresponding to vertices in $S$.

**How to Cite This Entry:**

Induced subgraph.

*Encyclopedia of Mathematics.*URL: http://www.encyclopediaofmath.org/index.php?title=Induced_subgraph&oldid=37442