Definition
Induced Subgraph
Let
be an undirected graph and . The subgraph induced by is It retains the vertices in
and all edges between them. Thus two retained vertices are adjacent in exactly when they are adjacent in . Unlike a general subgraph, an induced subgraph does not allow edges between retained vertices to be omitted: choosing
determines completely.