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

then a graph

is a subgraph of $G$ when

and

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:

and

and every edge in $F$ has both endpoints in $W$.

We write

to mean that $H$ is a subgraph of $G$.

For example, let

and

If

and

then

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

or

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

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

Thus

The edge set of $G-X$ consists of all edges of $G$ whose endpoints both remain in

For a single vertex $v$, one writes

instead of

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

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

Thus

and

For a single edge $e$, one writes

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

It has vertex set

and edge set

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

For example, suppose

and

Then

has edge set

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

have vertex set

and edge set

The graph with vertex set

and edge set

is a subgraph of $G$, but it is not an induced subgraph.

The induced subgraph on

is the whole triangle.

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

then the edge-induced subgraph has vertices

and edges

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

and

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.

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.

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.

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

Equivalently, $G$ contains a subgraph isomorphic to

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

and

Let

The induced subgraph

has edge set

It is a triangle.

Now define

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

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.