Subgraph

Definition

Subgraph

A graph is called subgraph of graph if it holds that:

Induced Subgraph

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.

Link to original