# 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 Related topic Defines induced Defines spanned by Defines spanning Defines spanning subgraph Defines induced subgraph