# Chapter 11. Subgraphs

# Chapter 11. Subgraphs

A subgraph is a graph contained inside another graph. It is formed by keeping some vertices and some edges from a larger graph. Subgraphs let us study local structure, extract special patterns, and reduce a graph to a simpler object.

If

$$
G=(V,E),
$$

then a graph

$$
H=(V_H,E_H)
$$

is a subgraph of \(G\) when

$$
V_H \subseteq V
$$

and

$$
E_H \subseteq E,
$$

with the condition that every edge in \(E_H\) has both endpoints in \(V_H\). This is the standard set-theoretic definition of a subgraph.

## 11.1 Basic Definition

Let \(G=(V,E)\) be a graph.

A graph \(H=(W,F)\) is a **subgraph** of \(G\) if:

$$
W \subseteq V
$$

and

$$
F \subseteq E,
$$

and every edge in \(F\) has both endpoints in \(W\).

We write

$$
H \subseteq G
$$

to mean that \(H\) is a subgraph of \(G\).

For example, let

$$
V=\{a,b,c,d\}
$$

and

$$
E=\{\{a,b\},\{a,c\},\{b,c\},\{c,d\}\}.
$$

If

$$
W=\{a,b,c\}
$$

and

$$
F=\{\{a,b\},\{a,c\}\},
$$

then

$$
H=(W,F)
$$

is a subgraph of \(G\).

The edge \(\{b,c\}\) belongs to \(G\), but it need not belong to \(H\). A general subgraph may omit edges even when their endpoints are kept.

## 11.2 Proper Subgraphs

A subgraph \(H\) of \(G\) is a **proper subgraph** if it differs from \(G\).

This means that either

$$
V(H) \subsetneq V(G)
$$

or

$$
E(H) \subsetneq E(G).
$$

Thus a proper subgraph is strictly smaller in vertices, edges, or both.

For example, every graph with at least one edge has a proper subgraph obtained by deleting that edge. Every graph with at least one vertex has a proper subgraph obtained by deleting that vertex and all incident edges.

The graph \(G\) itself is a subgraph of \(G\), but it is not a proper subgraph of \(G\).

## 11.3 Vertex Deletion

A common way to form a subgraph is to delete vertices.

If \(X \subseteq V(G)\), then

$$
G-X
$$

denotes the graph obtained from \(G\) by deleting the vertices in \(X\) and all edges incident with those vertices.

Thus

$$
V(G-X)=V(G)\setminus X.
$$

The edge set of \(G-X\) consists of all edges of \(G\) whose endpoints both remain in

$$
V(G)\setminus X.
$$

For a single vertex \(v\), one writes

$$
G-v
$$

instead of

$$
G-\{v\}.
$$

Vertex deletion is important in connectivity, cut vertices, induced subgraphs, graph minors, and algorithmic recursion.

## 11.4 Edge Deletion

Another way to form a subgraph is to delete edges.

If \(S \subseteq E(G)\), then

$$
G-S
$$

denotes the graph obtained from \(G\) by deleting the edges in \(S\) while keeping all vertices.

Thus

$$
V(G-S)=V(G)
$$

and

$$
E(G-S)=E(G)\setminus S.
$$

For a single edge \(e\), one writes

$$
G-e.
$$

Edge deletion is used to study bridges, spanning trees, forests, cuts, and minimal connected subgraphs.

## 11.5 Induced Subgraphs

An **induced subgraph** is formed by choosing vertices and keeping all edges of the original graph whose endpoints lie among the chosen vertices.

If \(S \subseteq V(G)\), then the subgraph induced by \(S\) is written as

$$
G[S].
$$

It has vertex set

$$
V(G[S])=S
$$

and edge set

$$
E(G[S])=\{\{u,v\}\in E(G): u,v\in S\}.
$$

Thus \(G[S]\) contains every edge of \(G\) between vertices in \(S\). This is the essential feature of an induced subgraph.

For example, suppose

$$
E(G)=\{\{a,b\},\{a,c\},\{b,c\},\{c,d\}\}
$$

and

$$
S=\{a,b,c\}.
$$

Then

$$
G[S]
$$

has edge set

$$
\{\{a,b\},\{a,c\},\{b,c\}\}.
$$

The edge \(\{b,c\}\) cannot be omitted, because both endpoints belong to \(S\) and the edge exists in \(G\).

## 11.6 General Subgraph Versus Induced Subgraph

A general subgraph may omit edges among retained vertices. An induced subgraph may not.

Let

$$
G
$$

have vertex set

$$
\{a,b,c\}
$$

and edge set

$$
\{\{a,b\},\{a,c\},\{b,c\}\}.
$$

The graph with vertex set

$$
\{a,b,c\}
$$

and edge set

$$
\{\{a,b\}\}
$$

is a subgraph of \(G\), but it is not an induced subgraph.

The induced subgraph on

$$
\{a,b,c\}
$$

is the whole triangle.

| Type | Vertices | Edges |
|---|---|---|
| General subgraph | Choose some vertices | Choose some allowed edges |
| Induced subgraph | Choose some vertices | Must keep all edges among them |

Induced subgraphs are determined entirely by their vertex sets.

## 11.7 Edge-Induced Subgraphs

One may also form a subgraph by choosing edges.

If \(S \subseteq E(G)\), then the **edge-induced subgraph** \(G[S]\) has edge set \(S\), and its vertex set consists of all endpoints of edges in \(S\). Some authors use separate notation to avoid confusion with vertex-induced subgraphs.

For example, if

$$
S=\{\{a,b\},\{c,d\}\},
$$

then the edge-induced subgraph has vertices

$$
\{a,b,c,d\}
$$

and edges

$$
S.
$$

An edge-induced subgraph contains no isolated vertices unless the convention explicitly adds them.

## 11.8 Spanning Subgraphs

A **spanning subgraph** is a subgraph that contains every vertex of the original graph.

Thus \(H\) is a spanning subgraph of \(G\) if

$$
V(H)=V(G)
$$

and

$$
E(H)\subseteq E(G).
$$

A spanning subgraph is obtained by deleting edges only.

For example, if \(G\) is a square with one diagonal, then the square alone is a spanning subgraph. It contains all four vertices but omits the diagonal.

A spanning tree is a spanning subgraph that is also a tree.

## 11.9 Induced Versus Spanning

Induced and spanning subgraphs control different choices.

An induced subgraph chooses vertices and keeps all edges among them.

A spanning subgraph keeps all vertices and chooses edges.

| Subgraph type | Vertex set | Edge set |
|---|---|---|
| Induced subgraph | May be smaller than \(V(G)\) | Forced by chosen vertices |
| Spanning subgraph | Equal to \(V(G)\) | May be smaller than \(E(G)\) |

A subgraph that is both induced and spanning must be the original graph itself, because it keeps all vertices and all edges among those vertices.

## 11.10 Subgraphs Defined by Properties

Many important graph objects are subgraphs satisfying a property.

| Object | Subgraph property |
|---|---|
| Path | Vertices and edges form a path |
| Cycle | Vertices and edges form a cycle |
| Component | Maximal connected subgraph |
| Tree | Connected acyclic subgraph |
| Spanning tree | Spanning subgraph that is a tree |
| Clique | Induced complete subgraph |
| Independent set | Induced subgraph with no edges |
| Matching | Subgraph of independent edges |

This viewpoint is useful because many graph problems ask whether a graph contains a subgraph of a specified kind.

For example, asking whether a graph contains a triangle is asking whether it contains a subgraph isomorphic to \(K_3\).

## 11.11 Maximal Subgraphs

A subgraph is **maximal** with respect to a property if it has the property and cannot be enlarged while still having that property.

For example, a connected component is a maximal connected subgraph.

A maximal forest is an acyclic subgraph that cannot have any edge added without creating a cycle. In a connected graph, a maximal forest is a spanning tree.

Maximal means locally unenlargeable. It does not necessarily mean largest possible.

A graph may have many maximal subgraphs with the same property, and they may have different sizes.

## 11.12 Maximum Subgraphs

A subgraph is **maximum** with respect to a property if it has largest possible size among all subgraphs with that property.

For example, a maximum clique is a clique with as many vertices as possible.

A maximum matching is a matching with as many edges as possible.

Maximum is a global condition. It compares all subgraphs with the same property.

| Term | Meaning |
|---|---|
| Maximal | Cannot be enlarged while preserving the property |
| Maximum | Has largest possible size among all such subgraphs |

Every maximum subgraph is maximal. A maximal subgraph need not be maximum.

## 11.13 Minimal Subgraphs

A subgraph is **minimal** with respect to a property if it has the property and no proper subgraph still has that property.

For example, a tree is a minimal connected graph. Removing any edge from a tree makes it disconnected.

A minimal spanning connected subgraph of a connected graph is a spanning tree.

Minimality is used to isolate essential structure. A minimal connected subgraph contains no redundant edge. A minimal counterexample in a proof contains no smaller counterexample.

## 11.14 Subgraph Isomorphism

A graph \(G\) contains a copy of a graph \(F\) if some subgraph of \(G\) is isomorphic to \(F\).

This is called a **subgraph isomorphism**.

For example, \(G\) contains a triangle if it has three vertices \(a,b,c\) with edges

$$
\{a,b\},\{b,c\},\{c,a\}.
$$

Equivalently, \(G\) contains a subgraph isomorphic to

$$
K_3.
$$

Subgraph isomorphism is a central pattern-matching problem. It appears in chemistry, network analysis, databases, program analysis, and combinatorial algorithms.

## 11.15 Induced Subgraph Isomorphism

A graph \(G\) contains an induced copy of \(F\) if some induced subgraph of \(G\) is isomorphic to \(F\).

This is stronger than ordinary subgraph containment.

For example, suppose \(F\) is a path on three vertices. A triangle contains a path of length \(2\) as an ordinary subgraph, but it does not contain an induced path of length \(2\). Any three vertices of the triangle induce the whole triangle, not just the path.

Induced subgraph containment cares about both edges and non-edges among the chosen vertices.

## 11.16 Hereditary Properties

A graph property is **hereditary** if every induced subgraph of a graph with the property also has the property.

For example, being bipartite is hereditary under induced subgraphs. If a graph has no odd cycle, then deleting vertices cannot create an odd cycle.

Being planar is also hereditary under subgraphs. Deleting vertices or edges cannot destroy an existing planar drawing.

Hereditary properties are often characterized by forbidden induced subgraphs or forbidden subgraphs.

## 11.17 Example

Let

$$
V=\{a,b,c,d,e\}
$$

and

$$
E=
\{\{a,b\},\{a,c\},\{b,c\},\{c,d\},\{d,e\}\}.
$$

Let

$$
S=\{a,b,c\}.
$$

The induced subgraph

$$
G[S]
$$

has edge set

$$
\{\{a,b\},\{a,c\},\{b,c\}\}.
$$

It is a triangle.

Now define

$$
H=(S,\{\{a,b\},\{b,c\}\}).
$$

Then \(H\) is a subgraph of \(G\), but it is not induced, because \(\{a,c\}\) is an edge of \(G\) whose endpoints both lie in \(S\), yet it is missing from \(H\).

If

$$
F=G-\{\{a,c\}\},
$$

then \(F\) is a spanning subgraph of \(G\), because it keeps all vertices and deletes only one edge.

## 11.18 Summary

A subgraph is obtained by retaining some vertices and some edges from a graph. A proper subgraph differs from the original graph. Vertex deletion and edge deletion are the basic operations for producing subgraphs.

An induced subgraph is determined by a vertex set and keeps all original edges among those vertices. A spanning subgraph keeps every vertex and may omit edges. Edge-induced subgraphs are determined by chosen edges.

Subgraphs provide the language for paths, cycles, trees, components, cliques, matchings, minors, decompositions, and forbidden-structure theorems. They let graph theory move from a whole graph to the structures contained inside it.