vertexinduced

In graph theory, a vertex-induced subgraph on a set S of vertices of a graph G=(V,E) is the subgraph G[S] that contains all and only the edges of G whose endpoints lie in S. Equivalently, G[S] has vertex set S and edge set E[S] = { (u,v) ∈ E : u ∈ S and v ∈ S }. In directed graphs, the induced subgraph preserves the direction of each edge.

The vertex-induced subgraph is obtained by deleting from G all vertices not in S and all edges incident to those vertices. The concept emphasizes the retained adjacencies among the selected vertices.

Interpretations and examples: The induced subgraph reflects the induced relationships among the chosen vertices. For instance, S is a clique if and only if G[S] is complete; S is an independent set if G[S] contains no edges.

Distinctions and scope: Induced subgraphs are distinguished from arbitrary subgraphs that can omit some edges among S. They are also closely related to the notion of subgraphs formed by vertex deletions. The induced subgraph is uniquely determined by S.

Applications: Induced subgraphs are fundamental in structural graph theory, property testing, and algorithm design. They are central to definitions of graph classes such as chordal graphs and to problems like induced subgraph isomorphism, where one seeks a vertex subset whose induced subgraph is isomorphic to a given pattern.