Induced Subgraph — Definition, Formula & Examples

An induced subgraph is a subgraph you get by choosing a subset of vertices from a graph and automatically including every edge from the original graph that connects two chosen vertices.

Given a graph $G = (V, E)$ and a subset $S \subseteq V$ , the subgraph of $G$ induced by $S$ , denoted $G[S]$ , is the graph $(S, E')$ where $E' = \{\{u,v\} \in E \mid u \in S \text{ and } v \in S\}$ .

Key Formula

G[S] = \bigl(S,\; \{\{u,v\} \in E \mid u \in S,\, 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 of G induced by S

How It Works

To construct an induced subgraph, you only choose vertices — the edges are determined for you. Once you pick your vertex set

S

, you must include every edge of the original graph whose both endpoints lie in

S

, and you may not include any edge that does not appear in the original graph. This distinguishes an induced subgraph from a general subgraph, where you can freely omit edges between selected vertices.

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 induced subgraph G[S] where S = {1, 2, 3}.

Step 1: Identify all edges of G whose both endpoints are in S = {1, 2, 3}.

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

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

Step 3: Construct the induced subgraph.

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

Answer: G[S] is the complete graph K₃ on vertices {1, 2, 3} with three edges.

Why It Matters

Many graph problems are stated in terms of induced subgraphs. For instance, determining whether a graph is chordal, perfect, or claw-free depends on which induced subgraphs it contains. In algorithm design, finding a maximum clique or maximum independent set amounts to finding an induced subgraph with a specific structure.

Common Mistakes

Mistake: Confusing an induced subgraph with a general subgraph by selectively omitting some edges between chosen vertices.

Correction: In an induced subgraph, you have no choice about edges: every edge of the original graph between selected vertices must be included. If you want to drop edges, the result is a (non-induced) subgraph.