Department of Mathematics Elementary Graph Theory Lecture 3
Subgraphs
A subgraph of G is a graph having all of its vertices and edges in G. If G1 is a
subgraph of G, then G is a supergraph of G1.
G1 is a subgraph of G
In other words.
If G and H are two graphs with vertex sets V(H), V(G) and edge sets E(H)
and E(G) respectively such that V(H) V(G) and E(H) E(G) then we call H as a
subgraph of G or G is a supergraph of H.
1. Spanning subgraph
A spanning subgraph is a subgraph containing all the vertices of G ( if
V(H) V(G) ) then we say that H is a spanning subgraph of G ).
The graphs F1 and H1 are spanning subgraphs of a graph G1, but J1 is not a
spanning subgraph of G1.
2. Removal of a vertex and an edge
The removal of a vertex vi from a graph G result is that subgraph G – vi of G
containing of all vertices in G except vi and all edges not incident with vi .
Dr. Didar A. Ali 1
, Department of Mathematics Elementary Graph Theory Lecture 3
Thus G – vi is the maximal subgraph of G not containing vi .
On the otherhand, the removal of an edge xi from G yields the spanning
subgraph G – xi containing all edges of G except xi . Thus G – xi is the
maximal subgraph of G not containing xi .
The addition of an edge vi v j to a graph G is G vi v j where vi and v j are
non-adjacent in G.
Deleting vertices from a graph G.
Deleting edges from a graph G
Dr. Didar A. Ali 2
Subgraphs
A subgraph of G is a graph having all of its vertices and edges in G. If G1 is a
subgraph of G, then G is a supergraph of G1.
G1 is a subgraph of G
In other words.
If G and H are two graphs with vertex sets V(H), V(G) and edge sets E(H)
and E(G) respectively such that V(H) V(G) and E(H) E(G) then we call H as a
subgraph of G or G is a supergraph of H.
1. Spanning subgraph
A spanning subgraph is a subgraph containing all the vertices of G ( if
V(H) V(G) ) then we say that H is a spanning subgraph of G ).
The graphs F1 and H1 are spanning subgraphs of a graph G1, but J1 is not a
spanning subgraph of G1.
2. Removal of a vertex and an edge
The removal of a vertex vi from a graph G result is that subgraph G – vi of G
containing of all vertices in G except vi and all edges not incident with vi .
Dr. Didar A. Ali 1
, Department of Mathematics Elementary Graph Theory Lecture 3
Thus G – vi is the maximal subgraph of G not containing vi .
On the otherhand, the removal of an edge xi from G yields the spanning
subgraph G – xi containing all edges of G except xi . Thus G – xi is the
maximal subgraph of G not containing xi .
The addition of an edge vi v j to a graph G is G vi v j where vi and v j are
non-adjacent in G.
Deleting vertices from a graph G.
Deleting edges from a graph G
Dr. Didar A. Ali 2
