Course contentsShow
← Computer Science
Lesson 667 of 2,87216. Graphs: Representation and Basic ConceptsFree lesson

Subgraphs, Induced Subgraphs, and Spanning Subgraphs

Understand different ways to extract smaller graphs from a larger graph structure.

Subgraphs, Induced Subgraphs, and Spanning Subgraphs

You'll learn how to extract meaningful smaller graphs from a larger graph structure.

What is a Subgraph?

A subgraph is simply a graph formed by taking some vertices and edges from a larger graph. Think of it like selecting a portion of a social network—maybe just your close friends and the friendships between them—from the entire network.

Formally, graph H is a subgraph of graph G if:

  • Every vertex in H exists in G
  • Every edge in H exists in G
  • The endpoints of edges in H are also in H

Three Important Types

Induced Subgraph

An induced subgraph is created by selecting specific vertices and automatically including all edges between those selected vertices that existed in the original graph.

Analogy: You pick certain people from a party, and you must preserve all their existing relationships.

Spanning Subgraph

A spanning subgraph includes all vertices from the original graph but potentially fewer edges. You keep everyone but might remove some connections.

Analogy: Everyone from the party is still present, but some people might have stopped talking to each other.

General Subgraph

A general subgraph can have a subset of vertices and any subset of edges between those vertices—complete flexibility in what you include.

Why This Matters

Understanding subgraphs helps you:

  • Identify important subsections of networks (communities, clusters)
  • Simplify complex graph problems by focusing on relevant parts
  • Build spanning trees (coming later in your studies)
  • Analyze graph properties at different scales

Key Takeaway: Subgraphs let you zoom in on specific parts of a graph; induced subgraphs preserve all relationships between chosen vertices, while spanning subgraphs keep all vertices but can trim connections.