Subgraphs

Subgraph

A graph $\text{subgraph}$ is formed by selecting a subset of the vertices of a larger graph $G$ and then choosing a subset of the edges that connect those vertices.

In formal terms, if $H$ is a $\text{subgraph}$ of $G$, then $V(H)\subseteq V(G)$ and $E(H)\subseteq E(G)$. This ensures that adjacency relationships are preserved from $G$ to $H$.

$\text{Subgraphs}$ are fundamental in graph theory for analyzing local structures, testing properties, and simplifying complex networks while retaining essential connectivity information.

Figure 1. Deleting some vertices or edges (b) from the supergraph (a) leaves a subgraph (c).

Figure 2. A subgraph and a non-subgraph from the supergraph.

$\mathbf{\text{Example}}$
A social network graph restricted to users from one city and only the friendships among them is a $\text{subgraph}$ of the full network.

$\mathbf{\text{Metaphor}}$
Taking a $\text{subgraph}$ is like zooming into a city map to view only the streets and intersections within that city boundary.

Spanning Subgraph

A $\text{spanning}$ $\text{subgraph}$ includes all vertices of $G$ but only a subset of the edges. It “spans” the entire vertex set of the original graph.

Formally, $H$ is a $\text{spanning}$ $\text{subgraph}$ if $V(H)=V(G)$ while $E(H)\subseteq E(G)$.

$\text{Spanning}$ $\text{subgraph}$s are critical in algorithms such as minimum spanning tree, where one seeks a $\text{subgraph}$ that connects all vertices at minimal cost.

Figure 3. Spanning subgraphs of $C_3$.

Induced Subgraph

An $\text{induced}$ $\text{subgraph}$ is determined entirely by its chosen vertices: it contains every edge of $G$ whose endpoints both lie in the selected vertex set.

Formally, if $H$ is induced by $V(H)$, then $E(H)=E(G)\cap (\genfrac{}{}{0ex}{}{V(H)}{2})$. This preserves all adjacency relations within the subset.

$\text{Induced}$ $\text{subgraphs}$ capture complete local interactions and are useful for studying community structures or motif discovery.

$\mathbf{\text{Example}}$
Selecting the set of red vertices in a graph and including all edges between them yields an $\text{induced}$ $\text{subgraph}$.

Figure 4. Induced subgraph.

$\mathbf{\text{Metaphor}}$
An $\text{induced}$ $\text{subgraph}$ is like isolating all rooms in a building with windows and considering all connecting hallways between those rooms.

Subgraph Induced by a Vertex Set

Given a subset $A$ of vertices, the notation $G[A]$ denotes the $\text{induced}$ $\text{subgraph}$ by $A$, capturing exactly those vertices and their interconnecting edges.

In this context, $V(G[A])=A$ and $E(G[A])=E(G)\cap (\genfrac{}{}{0ex}{}{A}{2})$. This formalizes the idea of focusing on a specific subset of nodes.

$G[A]$ is an essential tool for analyzing substructures of large graphs, as it provides a precise mechanism to extract and study local patterns.

Figure 5. Induced subgraph $G[A]$.

$\mathbf{\text{Example}}$
If $A$ represents all authors in a co-authorship graph from a particular university, then $G[A]$ shows all collaborations among those authors.

$\mathbf{\text{Metaphor}}$
Constructing $G[A]$ is like selecting chapters from a book and then including every cross-reference between those chapters.

Conclusion

We have explored different ways to extract meaningful parts from a graph: the general $\text{subgraph}$, the $\text{spanning}$ variant covering all vertices, the $\text{induced}$ variant preserving all internal edges of a chosen vertex set, and the formal extraction notation $G[A]$ for a specific subset.

Each type of subgraph serves unique purposes in graph algorithms and theoretical analysis, from simplifying network structures to isolating communities.

Understanding these definitions and notations equips you with fundamental tools for dissecting and examining large, complex graphs in both theoretical and applied settings.