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.