A portion of a graph G obtained by either eliminating edges from G and/or eliminating some vertices and their associated edges. Formally a subgraph of a graph G with vertices V and edges E is a graph G′ with vertices V′ and edges E′ in which V′ is a subset of V and E′ is a subset of E (edges in E′ joining vertices in V′).

If V′ is a proper subset of V or E′ is a proper subset of E then G′ is a proper subgraph of G. If all the vertices of G are present in the subgraph G′ then G′ is a spanning subgraph of G. See also spanning tree.