subgraphs

In graph theory, a subgraph of a graph G = (V, E) is a graph H = (V(H), E(H)) where V(H) ⊆ V and E(H) ⊆ E, with each edge in E(H) connecting two vertices in V(H). In other words, a subgraph uses a subset of the original vertices and a subset of the original edges, with incidence preserved.

There are several common kinds of subgraphs. A vertex-induced subgraph on a subset S ⊆ V has vertex set V(H) = S and edge set E(H) consisting of all edges of G whose endpoints both lie in S; this is often denoted G[S]. An edge-induced subgraph keeps all vertices V(H) = V but may include only a subset of edges, E(H) ⊆ E. A spanning subgraph has V(H) = V, i.e., it uses all vertices but possibly fewer edges. Subgraphs obtained by removing vertices (and their incident edges) or removing edges are standard constructions, with G − v denoting the graph after deleting vertex v and its incident edges.

Subgraph relation is reflexive and transitive: any graph is a subgraph of itself, and a subgraph of a subgraph is again a subgraph. A subgraph is proper if it is not equal to the original graph. Every induced subgraph is a subgraph, but not every subgraph is induced. A subgraph isomorphism asks whether a graph H can be mapped injectively into G so that adjacency is preserved; this is a central problem in pattern matching.

Connected subgraphs, including components, are subgraphs that form connected graphs. Common special cases include spanning trees (spanning subgraphs that are trees) and induced cycles, which play key roles in various algorithms and proofs. Subgraphs provide a flexible language for analyzing local structure within larger networks.