# subgraph

We say that ${G}^{\prime}=({V}^{\prime},{E}^{\prime})$ is a *subgraph ^{}* of $G=(V,E)$ if ${V}^{\prime}\subseteq V$ and ${E}^{\prime}\subseteq E$. In this case we write ${G}^{\prime}\subseteq G$.

If ${G}^{\prime}$ contains *all edges* of $G$ that join two vertices in ${V}^{\prime}$ then ${G}^{\prime}$ is said to be the subgraph *induced* or *spanned by* ${V}^{\prime}$ and is denoted by $G[{V}^{\prime}]$. Thus, a subgraph ${G}^{\prime}$ of $G$ is an induced subgraph if ${G}^{\prime}=G[V({G}^{\prime})]$. If ${V}^{\prime}=V$, then ${G}^{\prime}$ 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\subset V(G)$, then $G-W=G[V\setminus W]$ is the subgraph of $G$ obtained by deleting the vertices in $W$ *and all edges incident ^{} with them*. Similarly, if ${E}^{\prime}\subseteq E(G)$, then $G-{E}^{\prime}=(V(G),E(G)\setminus {E}^{\prime})$. If $W=w$ and ${E}^{\prime}=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 | Pseudograph^{} |

Related topic | Multigraph^{} |

Defines | induced |

Defines | spanned by |

Defines | spanning |

Defines | spanning subgraph |

Defines | induced subgraph |