## You are here

Homesubgraph

## Primary tabs

# 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 *Modern Graph Theory* by Béla Bollobás, published by Springer-Verlag New York, Inc., 1998.

## Mathematics Subject Classification

05C99*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections