A vertex-induced subgraph (sometimes simply called an "induced subgraph") is a subset of the vertices of a graph G together with any edges whose endpoints are both in this subset. The figure above illustrates the subgraph induced on the complete graph K_10 by the vertex subset {1, 2, 3, 5, 7, 10}. An induced subgraph that is a complete graph is called a clique. Any induced subgraph of a complete graph forms a clique. The subgraph induced by a set of vertices can be computed in the Wolfram Language using Subgraph[g, vlist]. A graph is called a perfect graph if, for each of its induced subgraphs g_i, the chromatic number of g_i equals the largest number of pairwise adjacent vertices in g_i.

clique | edge-induced subgraph | forbidden subgraph | perfect graph | subgraph