2.1.4. Subgraphs and induced subgraphs
A graph H is a
subgraph of a graph G if and
. We also say that G is a supergraph
of H.
We delete a vertex v of G if
and
, and the
subgraph
has vertex set
and E(H) contains all of those edges of G which are not incident with v.
If
, then
(delete an edge) is the subgraph of G having vertex set
and edge set
.
If u and v
are nonadjacent vertices of a graph G, then G + f, where f
= uv, denotes the graph with vertex set
and edge set
. So,
.



Whenever a subgraph H of a graph G has the same order as G, then H is called a spanning subgraph of G.
If U is a
nonempty subset of the vertex set
of a graph G, then the subgraph
of G induced by U is the
graph having vertex set U and whose edge set consists of those edges of G incident with two elements of U. A subgraph H of G is vertex-induced
if H =
for
some subset U of
.




If X is a
nonempty subset of
,
then the subgraph
induced
by X is the graph having edge set X and whose vertex set consists
of those vertices of G incident
at least one edge of X. A subgraph H of G is edge-induced
if
for some subset X of
.



