1.1.3 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 .