Subgraph

A subgraph is a graph formed from a subset of the vertices and edges of another graph. If G = (V, E) is a graph, a subgraph H = (V', E') satisfies V' ⊆ V and E' ⊆ E, with the requirement that every edge in E' has both endpoints in V'. This holds for both undirected graphs and directed graphs (digraphs), where edges are oriented pairs.

There are several common subgraph variations. An induced subgraph on a vertex set V' ⊆ V, denoted G[V'], has vertex set V' and edge set E' consisting of all edges of E whose endpoints lie entirely in V'. A spanning subgraph uses the same vertex set as the original graph (V' = V) but a subset of the edges (E' ⊆ E). Subgraphs can also be described by their properties, such as connected subgraphs, which are subgraphs in which every pair of vertices is joined by a path within the subgraph.

Examples help illustrate the idea. From a triangle graph with vertices a, b, c and edges ab, bc, ca, a subgraph could be the edge ab with vertices {a, b}, or the induced subgraph on {a, b} which includes edge ab. The induced subgraph on a single vertex contains no edges.

Subgraphs are fundamental in structural analysis of networks, chemistry, and computer science. They lead to algorithmic problems such as subgraph recognition and subgraph isomorphism, the latter being NP-complete in general. Studying subgraphs helps understand local structure, connectivity, and patterns within larger graphs.