Vertex-Induced Subgraph — Definition, Formula & Examples

A vertex-induced subgraph is the subgraph you get by choosing a subset of vertices from a graph and keeping every edge that connects two of those chosen vertices.

Given a graph $G = (V, E)$ and a subset $S \subseteq V$ , the vertex-induced subgraph $G[S]$ is the graph $(S, E')$ where $E' = \{\{u, v\} \in E \mid u \in S \text{ and } v \in S\}$ . The edge set is completely determined by the choice of $S$ .

Key Formula

G[S] = \bigl(S,\; \{\{u,v\} \in E \mid u \in S \text{ and } v \in S\}\bigr)

Where:

$G = (V, E)$ = The original graph with vertex set V and edge set E
$S$ = A chosen subset of V
$G[S]$ = The subgraph induced by S

How It Works

To construct a vertex-induced subgraph, start by selecting a subset

S

of the original vertex set. Then scan every edge in the original graph: include it if and only if both of its endpoints belong to

S

. You have no freedom to drop or add edges — the vertex set alone dictates the result. This distinguishes it from a general subgraph, where you can independently choose which edges to keep.

Worked Example

Problem: Let G have vertices {1, 2, 3, 4} and edges {1-2, 1-3, 2-3, 2-4, 3-4}. Find the vertex-induced subgraph G[S] for S = {1, 2, 3}.

Step 1: List every edge in G whose both endpoints are in S = {1, 2, 3}.

\{1\text{-}2,\; 1\text{-}3,\; 2\text{-}3\}

Step 2: Edges 2-4 and 3-4 each have endpoint 4, which is not in S, so they are excluded.

Step 3: Assemble the induced subgraph.

G[S] = \bigl(\{1,2,3\},\; \{1\text{-}2,\; 1\text{-}3,\; 2\text{-}3\}\bigr)

Answer: G[{1, 2, 3}] is a triangle (complete graph K₃) on vertices 1, 2, and 3.

Why It Matters

Many classic graph problems are defined through induced subgraphs. A clique is an induced subgraph that is complete, and an independent set is an induced subgraph with no edges. Recognizing induced subgraph structure is central to algorithms courses, complexity theory (e.g., the induced subgraph isomorphism problem is NP-complete), and network analysis.

Common Mistakes

Mistake: Confusing an induced subgraph with a general subgraph, and thinking you can choose to omit some edges between vertices in S.

Correction: In a vertex-induced subgraph, the edge set is fully determined by the vertex subset — you must include every original edge whose both endpoints are in S. A general subgraph allows you to independently drop edges.