CLASS NOTE MCA 2ND SEMESTER
SUBJECT: GRAPH THEORY
OPERATIONS ON GRAPHS:
Union: Let G1 and G2 be two graphs. Then the union of these graphs, denoted by G1 ∪ G2 is
defined as the graph G such that
V(G)= V(G1) ∪ V(G2)
E(G)= E(G1) ∪ E(G2)
1 a
1 2 1 a 2
e b
a b g e g
b c
3 x j
c 3
2 x 4
d j 3 d
e G2 G = G1 ∪ G2
G1 4
Intersection: Let G1 and G2 be two graphs. Then the intersection of these graphs, denoted
by G1 ∩ G2 is defined as the graph G such that
V(G)= V(G1) ∩ V(G2)
E(G)= E(G1) ∩ E(G2)
1 a 1
1 2
e b a
a b g
3 x j b
c 3 2
2
d
3
e G2 G = G1 ∩ G2
G1 4
a
Prepared by: PRANJAL DAS
Department of Computer Applications 1
GIMT GUWAHATI
CLASS NOTE MCA 2ND SEMESTER
SUBJECT: GRAPH THEORY
Ring Sum: Let G1 and G2 be two graphs. Then the ring sum of these graphs, denoted by
b
G1 ⊕ G2 is defined as the
he graph G such that
V(G)= V(G1) ∪ V(G2)
E(G)= E(G1) ∪ E(G2) - E(G1) ∩ E(G2) = E(G1) ∆ E(G2)
1 a
1 2
e b
a b g
3 x j
c 3
2
d
e G2 G = G1 ⊕ G2
G1 4
Complement of a graph:: A complement of a graph G is denoted by G , is the graph
obtained by deleting all the edges of G and adding all the edges which a
are
re not in G but
they are in the complete graph with same number of vertices in G.
Therefore = Kn- G.
G
V1 V2 V1 V2
V4 V3 V4 V3
G1
G1
G2 G2
Prepared by: PRANJAL DAS
Department of Computer Applications 2
GIMT GUWAHATI
CLASS NOTE MCA 2ND SEMESTER
SUBJECT: GRAPH THEORY
Addition of a vertex: Let G be a graph and v be any vertex which is not in G, if we add v
to G, after addition v to G the new graph is denoted by G+v.
G G+v
Deletion of a vertex: Let G be a graph and v be any vertex which is in G, if we want to
remove v from G, then we have to delete v form G as well as all the edges which are
incident on v. After deletion v from G the new graph is denoted by G-v.
a v
d
b c
G-v
G
Deletion of a edge: Let G be a graph and e be any edge which is in G, if we want to
remove e from G, then we have to simply delete the edge e form G. After deletion of e from
G the new graph is denoted by G-e.
a e1 v e5
d
e2 e4
b e3 c
G G - e1
Prepared by: PRANJAL DAS
Department of Computer Applications 3
GIMT GUWAHATI
CLASS NOTE MCA 2ND SEMESTER
SUBJECT: GRAPH THEORY
Fusion of vertices: Fusion of two to vertices a and b in a graph G is an operation on G
which two vertices a and b are fused (or merged) together without deleting of any edges of
G.
c
b
e
f
f
Fusion of vertices Fusion of vertices Fusion of vertices
a and d a and c e and f
Problem: Prove that a simple graph and its complement cannot both be
disconnected.
Solution: Let G be a simple disconnected graph and u, v ∈ V (G). If u and v belong
to different components of G, then the edge uv ∈ E(G¯). If u and v belong to the same
component of G, choose a vertex w in another component of G. (G has at least two
components, since it is disconnected.). But then the edges uw and wv belong to E(G¯).
That is, in all cases there is a u, v-path in G¯. Hence a simple graph and its complement
cannot both be disconnected.
Prepared by: PRANJAL DAS
Department of Computer Applications 4
GIMT GUWAHATI
CLASS NOTE MCA 2ND SEMESTER
SUBJECT: GRAPH THEORY
Problem: Let G be a graph with girth 4 (shortest cycle of length four) in which every
vertex has degree k. Prove that G has at least 2k vertices.
Solution: Consider a graph G , it is given that all the vertices of G are of same degree k.
Again it is given that shortest cycle length is 4 , so there can’t be an edge where both the
end vertices are adjacent to a common vertex. Lewt us consider an edge ek with end
vertices u and v. So u and v does not has common end vertices. Since both u and v has
degree k , both u and v has disjoint set of neighbors each of having k neighbors.
Therefore, total number of vertices in the graph should be more than 2K. Hence G has at
least 2k vertices
Prepared by: PRANJAL DAS
Department of Computer Applications 5
GIMT GUWAHATI
