We say that G=(V,E) is a subgraphMathworldPlanetmath of G=(V,E) if VV and EE. In this case we write GG.

If G contains all edges of G that join two vertices in V then G is said to be the subgraph induced or spanned by V and is denoted by G[V]. Thus, a subgraph G of G is an induced subgraph if G=G[V(G)]. If V=V, then G is said to be a spanning subgraph of G.

Often, new graphs are constructed from old ones by deleting or adding some vertices and edges. If WV(G), then G-W=G[VW] is the subgraph of G obtained by deleting the vertices in W and all edges incidentPlanetmathPlanetmathPlanetmath with them. Similarly, if EE(G), then G-E=(V(G),E(G)E). If W=w and E=xy, then this notation is simplified to G-w and G-xy. Similarly, if x and y are nonadjacent vertices of G, then G+xy is obtained from G by joining x to y.

Adapted with permission of the author from by Béla Bollobás, published by Springer-Verlag New York, Inc., 1998.

Title subgraph
Canonical name Subgraph
Date of creation 2013-03-22 12:30:59
Last modified on 2013-03-22 12:30:59
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 10
Author CWoo (3771)
Entry type Definition
Classification msc 05C99
Related topic Graph
Related topic PseudographMathworldPlanetmath
Related topic MultigraphMathworldPlanetmath
Defines induced
Defines spanned by
Defines spanning
Defines spanning subgraph
Defines induced subgraph