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