We say that
is a subgraph of if
and
. In this case we write
.
If containsall edges of that join two vertices in then is said to be the subgraph induced or spanned by and is denoted by . Thus, a subgraph of is an induced subgraph if
. If , then is said to be a spanning subgraph of .
Often, new graphs are constructed from old ones by deleting or adding some vertices and edges. If
, then
is the subgraph of obtained by deleting the vertices in and all edges incident with them. Similarly, if
, then
. If and , then this notation is simplified to and . Similarly, if and are nonadjacent vertices of , then is obtained from by joining to .
Adapted with permission of the author from Modern Graph Theory by Béla Bollobás, published by Springer-Verlag New York, Inc., 1998.
![$ G[V']$](http://images.planetmath.org:8080/cache/objects/2256/l2h/img11.png "$ G[V']$"){kind=small}
![$ G' = G[V(G')]$](http://images.planetmath.org:8080/cache/objects/2256/l2h/img14.png "$ G' = G[V(G')]$"){kind=small}
![$ G - W = G[V\setminus W]$](http://images.planetmath.org:8080/cache/objects/2256/l2h/img19.png "$ G - W = G[V\setminus W]$"){kind=small}
