Subgraph

SUBGRAPH:

            A subgraph of a graph G(V,E) is a graph H(W,F) where W subset equal to V and F subset equal to   E. If W sub set V and F sub set E , then H is called the proper subgraph of G, if W=V, then H is called a spanning subgraph of G. A spanning subgraph of G need not contain all its edges. The graph H shown in below is a subgraph of K₅ . 

Note:Any subgraph of a graph G can be obtained by removing certain vertices and edges from G. It is to be noted that the removal of an edge does not mean the removal of its adjacent vertices, whereas the removal of a vertex means the removal of any edge incident on it.

VERTEX DELETED SUBGRAPH:

         

                   If a subset S of V and all the edges incident on the elements of S are deleted from a graph (G,E), then the resulting subgraph is called a vertex deleted subgraph of G(V,E).

                   If a subset T of E from a graph G(V,E) is deleted, then the resulting subgraph is called an edge deleted subgraph of G(V,E).

INDUCED SUBGRAPH: 

               A subgraph H(V',E') of G(V,E), where V' sub set equals to V and E' consists of only those edges that are incident on the elements of V', is called an induced subgraph  of G(V,E).

Following figures shows different subgraph of a given graph G.

UNION OF TWO GRAPH:

                        The union of two simple graph G₁(V₁,E₁) and G₂(V₂,E₂) is the simple graph with vertex V₁ U V₂ and edges  E₁ U E₂. The union of two graphs G₁  and  G₂ is denoted by G₁ U G₂. 

                Following figures shows union of two graph G₁  and  G₂.