Induced subgraph

In graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and all of the edges, from the original graph, connecting pairs of vertices in that subset.

be any subset of vertices of G. Then the induced subgraph

is the graph whose vertex set is

The same definition works for undirected graphs, directed graphs, and even multigraphs.

may also be called the subgraph induced in

, or (if context makes the choice of

unambiguous) the induced subgraph of

Important types of induced subgraphs include the following.

The induced subgraph isomorphism problem is a form of the subgraph isomorphism problem in which the goal is to test whether one graph can be found as an induced subgraph of another.

Because it includes the clique problem as a special case, it is NP-complete.