Course contentsShow
← Mathematics
Lesson 2654 of 3,12153. Graph TheoryFree lesson

Subgraphs and Induced Subgraphs

Define subgraphs formed by selecting vertices and edges, and induced subgraphs determined entirely by a vertex subset.

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.