Subgraphs: Zooming In on a Graph

Introduction

Imagine you are looking at a giant map of the entire United States highway system — hundreds of cities, thousands of roads, overwhelming complexity. Now imagine you cut out just your home state and study its roads in isolation. You have created a subgraph.

Subgraphs are the fundamental tool for zooming in on a graph. Almost every advanced graph theory result — connectivity, coloring, spanning trees, cliques — is stated in terms of what subgraphs a graph contains or avoids. Understanding them precisely is essential for everything that follows.

Definition

Formal Definition

Definition: A graph $H$ is a subgraph of a graph $G$, written $H \subseteq G$, if:
- Every vertex of $H$ is also a vertex of $G$: $V(H) \subseteq V(G)$
- Every edge of $H$ is also an edge of $G$: $E(H) \subseteq E(G)$

In other words: $H$ is obtained from $G$ by keeping some vertices and some edges — and discarding the rest.

The Golden Rule

The Golden Rule of Subgraphs: If an edge is included in $H$, then both of its endpoints must also be in $H$.

It is mathematically impossible to include an edge without its two endpoints. An edge floating with a missing endpoint is not a graph at all.

The Parent Graph $G$

Every subgraph example in this post is drawn from the same parent graph $G$:

$G$ has 6 vertices ($A$–$F$) and 8 edges. The two rows form a natural structure: top row $\{A,B,C\}$ and bottom row $\{D,E,F\}$ with cross-connections.

A Valid Subgraph

To create a subgraph, choose any subset of vertices, then choose any subset of the edges that connect only those vertices.

Here $H$ uses vertices $\{A,B,D,E\}$ and edges $\{AB, AD, DE\}$ (shown orange). The remaining vertices $C, F$ (faded) and the remaining edges (dashed) are in $G$ but not in $H$. Every orange edge connects two orange vertices — the Golden Rule is satisfied.

Checklist to verify a subgraph:

What Makes a Subgraph Invalid?

This attempt includes edge $BE$ but vertex $B$ is not in the vertex set (shown faded red). The edge has a missing endpoint — this violates the Golden Rule and is not a valid subgraph.

Induced Subgraphs

Sometimes you want a subgraph that gives the complete picture of the relationships among a chosen set of vertices — no cherry-picking which edges to include or exclude.

Definition

Definition: The induced subgraph $G[S]$ for a vertex set $S \subseteq V(G)$ is the subgraph that contains all vertices in $S$ and every edge of $G$ whose both endpoints are in $S$.

You choose the vertices; the edges are forced — you must include all of them. You cannot add or remove any edge from an induced subgraph.

The Social Network Example

Consider a complete social network of 4 people where everyone knows everyone ($K_4$):

Six friendships in total (every pair of 4 people). Now we want to study the sub-group $\{$Alice, Bob, Charlie$\}$.

Option 1 — Regular (non-induced) subgraph:

We pick vertices Alice, Bob, Charlie — but we decide to only include the Alice–Bob edge. This is a valid subgraph, but it hides information: Charlie knows both Alice and Bob, yet he appears isolated. The dashed edges show the friendships we deliberately omitted.

Option 2 — Induced subgraph $G[\{$Alice, Bob, Charlie$\}]$:

The induced subgraph forces all edges between the chosen vertices. Alice–Bob, Bob–Charlie, and Alice–Charlie are all included automatically. The result is $K_3$ (a triangle) — the true and complete picture of how these three people relate.

Why Induced Subgraphs Matter

Induced subgraphs preserve the full local structure. When graph theorists say “this graph contains a triangle” they mean “this graph has an induced subgraph isomorphic to $K_3$.” The induced subgraph is the honest representation of a vertex set’s internal relationships.

Graph Surgery: Removing Vertices and Edges

A practical way to build subgraphs is by deleting things from $G$.

Edge Deletion: $G - e$

Definition: $G - e$ is the graph obtained by removing edge $e$ from $G$, keeping all vertices.

The vertices at both ends of the deleted edge remain. Only the connection between them disappears.

$G - BE$: edge $BE$ (shown in red, dashed) is removed. Both $B$ and $E$ stay as vertices — they are just no longer directly connected. All other edges and vertices are unchanged.

Notation for removing a set of edges: $G - F$ where $F \subseteq E(G)$.

Vertex Deletion: $G - v$

Definition: $G - v$ is the graph obtained by removing vertex $v$ from $G$ and all edges incident to $v$.

When a vertex is deleted, every edge touching it must also go — you cannot leave edges without their endpoints.

$G - B$: vertex $B$ (faded red) is removed along with its three incident edges $AB$, $BC$, $BE$ (red dashed). The remaining graph on vertices $\{A,C,D,E,F\}$ keeps only edges that do not touch $B$.

Warning: Deleting a single vertex can shatter a connected graph. If $B$ were a cut vertex (Post 10), removing it would create two or more disconnected components.

Notation for removing a set of vertices: $G - S$ where $S \subseteq V(G)$. This removes all vertices in $S$ and all edges with at least one endpoint in $S$.

The Subgraph Relationship

Both $G - e$ and $G - v$ produce subgraphs of $G$:
- $G - e$ is a spanning subgraph (all vertices kept, one edge removed)
- $G - v$ is a subgraph on $|V| - 1$ vertices

Spanning Subgraphs

A special class of subgraphs worth naming:

Definition: A spanning subgraph of $G$ is a subgraph that contains all vertices of $G$ (it “spans” $G$) but possibly fewer edges.

The spanning trees from Post 13 are exactly the spanning subgraphs that are also trees — connected and acyclic, with $|V| - 1$ edges.

Relationship hierarchy:

$$\text{spanning subgraph} \;\subseteq\; \text{subgraph} \;\subseteq\; G$$
$$\text{induced subgraph} \;\subseteq\; \text{subgraph} \;\subseteq\; G$$

A spanning subgraph keeps all vertices but may drop edges. An induced subgraph keeps all edges between chosen vertices but may drop vertices. These two directions are complementary ways of extracting structure from $G$.

Special Subgraphs That Matter

When graph theorists study massive networks, they hunt for specific subgraph patterns that reveal deep structure.

Paths and Cycles as Subgraphs

When we say “graph $G$ contains a path from $u$ to $v$,” we mean $G$ has a path subgraph connecting $u$ to $v$. Similarly “$G$ contains a cycle” means $G$ has a cycle as a subgraph.

This language appears constantly: “$G$ contains $C_5$ as a subgraph” means there are 5 vertices in $G$ that form a 5-cycle using edges that exist in $G$.

Cliques — The Complete Subgraph

Definition: A clique is a subset of vertices $S \subseteq V(G)$ such that every pair of vertices in $S$ is adjacent — i.e., the induced subgraph $G[S]$ is a complete graph $K_{|S|}$.

• A 3-clique is a triangle ($K_3$)
• A 4-clique is $K_4$ — four mutually adjacent vertices
• The clique number $\omega(G)$ is the size of the largest clique in $G$

Social network analogy: A clique is a tight-knit group where literally everyone knows everyone else — no stranger in the group.

The green vertices $\{A,B,C,D\}$ form a 4-clique: all 6 edges between them exist (green). The purple vertices $\{E,F,G\}$ are connected to the clique but are not part of it. Finding this $K_4$ subgraph is finding the clique.

Connection to graph coloring (Post 12): The clique number gives a lower bound on the chromatic number: $\chi(G) \geq \omega(G)$. A 4-clique forces at least 4 colors.

Independent Sets — The Stranger Group

Definition: An independent set is a subset of vertices $S \subseteq V(G)$ such that no two vertices in $S$ are adjacent — i.e., the induced subgraph $G[S]$ has no edges.

• The independence number $\alpha(G)$ is the size of the largest independent set in $G$

Social network analogy: A group of people at a party who are all complete strangers — nobody in the group knows anyone else in the group.

The orange vertices $\{A, C, F\}$ form an independent set — no orange–orange edge exists. Every blue vertex is adjacent to at least one orange vertex. The dashed edges show boundaries near the set.

Connection to graph coloring: Every color class in a proper coloring is an independent set. When you color a graph with $k$ colors, you partition its vertices into $k$ independent sets.

The fundamental identity:

$$\alpha(G) + \text{(minimum vertex cover)} = |V(G)|$$

This is König’s theorem for bipartite graphs, and the general relation is Gallai’s theorem.

The Subgraph Relationships Summary

G (full graph)
├── Spanning subgraph: keep all V, drop some E
│     └── Spanning tree: spanning subgraph that is a tree (|E| = |V|-1)
│
├── Induced subgraph G[S]: keep subset S of V, keep ALL edges within S
│     └── G[S] = K_k → S is a clique
│     └── G[S] = empty → S is an independent set
│
└── General subgraph: any subset of V and subset of E (Golden Rule applies)
      └── G - e: subgraph with one edge removed
      └── G - v: subgraph with one vertex (and its edges) removed

Practice Problems

Problem 1: Is it a Valid Subgraph?

Question: Graph $G$ has vertices $\{1,2,3,4,5\}$ and edges $\{12, 13, 24, 35, 45\}$. Is $H$ with vertices $\{1,2,3\}$ and edges $\{12, 13, 35\}$ a valid subgraph of $G$?

Problem 2: Induced Subgraph

Question: Graph $G$ has vertices $\{A,B,C,D\}$ and edges $\{AB, AC, BC, CD\}$. What is the induced subgraph $G[\{A,B,C\}]$?

Problem 3: Edge vs Vertex Deletion

Question: Graph $G$ has vertices $\{1,2,3,4\}$ and edges $\{12,13,23,34\}$.
(a) What is $G - 13$?
(b) What is $G - 3$?

Problem 4: Identifying a Clique

Question: A graph has vertices $\{A,B,C,D,E\}$ and edges $\{AB,AC,AD,BC,BD,CD,CE,DE\}$. What is the largest clique? What is $\omega(G)$?

Problem 5: Independent Set and Coloring

Question: If a graph has an independent set of size 4, what does that tell you about graph coloring?

Problem 6: Spanning Subgraph

Question: A connected graph $G$ has 7 vertices and 10 edges. How many edges does a spanning tree of $G$ have? Is a spanning tree a subgraph of $G$?

Summary Table

Edge operations:

Real-World Applications

Social Network Analysis

Real social networks (Facebook, LinkedIn) are graphs with millions of vertices. Finding cliques identifies tight-knit communities. Finding large independent sets identifies groups that never interact. Both operations are computed on subgraphs of the massive network.

Subgraph Isomorphism in Drug Discovery

A drug molecule is a graph (atoms = vertices, bonds = edges). To check if a molecule contains a known “toxic substructure,” chemists look for subgraph isomorphism — does the molecule’s graph contain a copy of the dangerous pattern as a subgraph? This is one of the most computationally important subgraph problems in bioinformatics.

Compiler Register Allocation (Revisited)

In Post 12 we noted that register allocation uses graph coloring. The independent sets in the interference graph are exactly the sets of variables that can share a register — each color class is an independent set.

Network Resilience

Removing a vertex or edge ($G - v$, $G - e$) models failure in infrastructure networks. Engineers study which vertex deletions disconnect the graph (cut vertices from Post 10) by analysing the resulting subgraph. A graph is $k$-connected (Post 10) precisely when no set of $k-1$ vertices can disconnect it — a statement about which vertex deletions produce connected subgraphs.

The Maximum Clique and Maximum Independent Set Problems

Theorem: Finding the maximum clique ($\omega(G)$) and the maximum independent set ($\alpha(G)$) are both NP-complete for general graphs.

For real-world graphs with thousands of vertices, these problems can take supercomputers years. However:
- For perfect graphs (which include bipartite graphs, chordal graphs, interval graphs) both problems can be solved in polynomial time
- For planar graphs, a $\frac{4}{3}$-approximation exists
- In practice, branch-and-bound algorithms solve moderate instances (a few hundred vertices) quickly

Key Takeaways

1. A subgraph $H \subseteq G$ uses a subset of $G$’s vertices and a subset of $G$’s edges. The Golden Rule: every edge in $H$ must have both endpoints in $H$.
2. An induced subgraph $G[S]$ is the “honest” subgraph on vertex set $S$ — all edges between vertices of $S$ are automatically included; none can be omitted.
3. A spanning subgraph keeps all vertices of $G$ but may drop edges. Spanning trees are the minimally-connected spanning subgraphs.
4. Edge deletion $G - e$ removes an edge but keeps all vertices. Vertex deletion $G - v$ removes a vertex and all its incident edges.
5. A clique is a complete subgraph: every pair of vertices in the clique is adjacent. The clique number $\omega(G)$ is the size of the largest clique; it lower-bounds the chromatic number: $\chi(G) \geq \omega(G)$.
6. An independent set is a subgraph with no edges: no two vertices in the set are adjacent. Every color class in a proper coloring is an independent set.
7. Finding maximum cliques and maximum independent sets is NP-complete in general — among the hardest computational problems known.

Explore Further

Use the GraphArena Playground to experiment:

• Build the parent graph $G$ with 6 vertices and draw a subgraph by selecting 4 of the vertices — check the Golden Rule for each edge you include.
• Build $K_4$ and construct the induced subgraph on 3 vertices — verify all 3 edges are forced.
• Build any connected graph with 5 vertices, then delete a vertex. Does the resulting graph stay connected? Try deleting different vertices.
• Build a 6-vertex graph and try to find its maximum clique manually. Then find a maximum independent set — notice that the two sets are often complementary in structure.
• Color your graph from the independent set exercise: do the color classes match the independent sets you found?

Subgraphs are the microscope of graph theory — they let you isolate exactly the structure you care about and study it without distraction from the rest of the network.