subgraph (original) (raw)

We say that G′=(V′,E′) is a subgraph of G=(V,E) if V′⊆V and E′⊆E. In this case we write G′⊆G.

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 W⊂V⁢(G), then G-W=G⁢[V∖W] is the subgraph of G obtained by deleting the vertices in W and all edges incident with them. Similarly, if E′⊆E⁢(G), then G-E′=(V⁢(G),E⁢(G)∖E′). If W=w and E′=x⁢y, then this notation is simplified to G-w and G-x⁢y. Similarly, if x and y are nonadjacent vertices of G, then G+x⁢y is obtained from G by joining x to y.