Subgraphs and Induced Subgraphs
What you'll learn: How to extract smaller graphs from larger ones by selecting vertices and edges, and understand the special case where edge selection is automatic.
The Core Idea
Imagine a social network where you want to study just your friend group within a larger community. A subgraph is exactly this: a graph formed by choosing some vertices from the original graph and some edges between them (as long as both endpoints are in your selection).
More formally, graph H = (V', E') is a subgraph of G = (V, E) if:
- V' ⊆ V (H's vertices are a subset of G's vertices)
- E' ⊆ E (H's edges are a subset of G's edges)
- Every edge in E' connects two vertices that are both in V'
You have complete freedom: pick any vertices you want, then pick any edges you want (that make sense).
Induced Subgraphs: Automatic Edge Selection
An induced subgraph is more restrictive and elegant. You only choose which vertices to keep—the edges are determined automatically: you must include every edge from the original graph whose both endpoints are in your chosen vertex set.
If you select vertex subset S ⊆ V, the induced subgraph G[S] includes:
- All vertices in S
- Every edge from G that connects two vertices in S
Analogy: A regular subgraph is like choosing specific people and specific friendships to study. An induced subgraph is choosing people and automatically including all friendships that exist among them.
Example
If G has vertices {1,2,3,4} with edges {1-2, 2-3, 3-4, 1-3}, and you select S = {1,2,3}:
- The induced subgraph G[S] must include edges {1-2, 2-3, 1-3}
- A non-induced subgraph could include just {1-2, 2-3}, omitting 1-3
Key Takeaway: Subgraphs let you freely select vertices and edges; induced subgraphs are determined entirely by vertex selection, automatically including all qualifying edges.