FUZZY GRAPH

Fuzzy graph is the generalisation of the ordinary graph.

Therefore it is natural that though fuzzy graph inherits many
properties similar to those of ordinary graph, it deviates at many
places. In this chapter, the concept of fuzzy graph and many
other related terms are introduced. Also many properties of a
fuzzy graph are discussed.

2.1 Introduction to fuzzy graph

Definition 2.1.1 : A fuzzy graph G = (σ, µ) is a pair of

functions σ : V → [0, 1] and µ : V × V → [0, 1], where for
all u, v ∈ V , we have µ(u, v) ≤ σ(u) ∧ σ(v).

Remark 2.1.1 : Through out this book, µ is considered to be

symmetric. In other words, only undirected fuzzy graphs are
considered.
22 CHAPTER 2. FUZZY GRAPH

Definition 2.1.2 : The fuzzy graph H = (τ, ρ) is called a fuzzy

subgraph of G = (σ, µ) if τ (u) ≤ σ(u) for all u ∈ V and
ρ(u, v) ≤ µ(u, v) for all u, v ∈ V.

A fuzzy subgraph H = (τ, ρ) is said to be a spanning

fuzzy subgraph of G = (σ, µ) if τ (u) = σ(u) for all u. In this
case, the two graphs have same fuzzy node set; they differ only
in the arc weights.
Example 2.1.1 : Fig 2.1 represents a fuzzy graph G = (σ, µ)
where σ = {u|.8, v|.5, w|.7, x|.5} and µ = {(u, v)|.4, (u, w)|.6,
(x, v)|.5, (x, w)|.3}. Fig 2.2(a) is a fuzzy subgraph of G and Fig
2.2(b) is a spanning fuzzy subgraph of G

u(.8) .4 v(.5)

.6 .5

w(.7) .3 x(.5)
Fig.2.1 Fuzzy graph G = (σ, µ)

u(.6) .3 v(.4) u(.8) .4 v(.5)

.4 .5

w(.7) w(.7) .3 x(.5)

Fig.2.2(a) Fig.2.2(b)
A fuzzy subgraph of G A spanning fuzzy subgraph of G
2.1. INTRODUCTION TO FUZZY GRAPH 23

Definition 2.1.3 : Let G = (σ, µ) be a fuzzy graph and τ be

any fuzzy subset of σ, i.e., τ (u) ≤ σ(u) for all u,. Then the fuzzy
subgraph of G = (σ, µ) induced by τ is the maximal fuzzy
subgraph of G = (σ, µ) that has fuzzy node set τ. Evidently, this
is just the fuzzy graph (τ, ρ), where ρ(u, v) = τ (u)∧τ (v)∧µ(u, v)
for all u, v ∈ V.
Theorem 2.1.1 : If 0 ≤ s ≤ t ≤ 1, then (σt , µt ) is a subgraph
of (σs , µs ).

Proof : σ(u) ≥ t ⇒ σ(u) ≥ s and µ(u, v) ≥ t ⇒ µ(u, v) ≥ s. 

Theorem 2.1.2 : If (τ, ρ) is a fuzzy subgraph of (σ, µ), then for
any threshold t, 0 ≤ t ≤ 1, (τt , ρt ) is a subgraph of (σt , µt ).

Proof : τ (u) ≤ σ(u) ⇒ σ(u) ≥ t when τ (u) ≥ t 

The proof of the following theorem is left to the reader.
Theorem 2.1.3 : If (τ, ρ) is a fuzzy subgraph of (σ, µ), then for
all u, v in V we have ρ∞ (u, v) ≤ µ∞ (u, v).
Definition 2.1.4 : The underlying crisp graph of a fuzzy
graph G = (σ, µ) is denoted by G∗ = (σ ∗ , µ∗ ), where σ ∗ = {u ∈
V | σ(u) > 0} and µ∗ = {(u, v) ∈ V × V | µ(u, v) > 0}.

x(.4) .4 w(1)

.4 .8
.7

u(.8) v(.7)
Fig.2.3: A strong fuzzy graph
24 CHAPTER 2. FUZZY GRAPH

Definition 2.1.5 : A fuzzy graph G = (σ, µ) is a strong fuzzy

graph if µ(u, v) = σ(u) ∧ σ(v) for all (u, v) ∈ µ∗ and is a
complete fuzzy graph if µ(u, v) = σ(u)∧σ(v) for all u, v ∈ σ ∗ .
Two nodes u and v are said to be neighbors if µ(u, v) > 0.

x(.4) .4 w(1)

.8
.4 .7
.4

u(.8) .7
v(.7)
Fig.2.4: A complete fuzzy graph

2.2 Operations on fuzzy graphs

There are several operations, like complement of a fuzzy

graph, union, join, product and composition of two fuzzy graphs,
to yield new fuzzy graphs. The complement of a fuzzy graph does
not inherit the properties of complement of an ordinary graph.

2.2.1 Complement of a fuzzy graph

Definition 2.2.1 : The complement of a fuzzy graph G =

(σ, µ) is a fuzzy graph G = (σ, µ) where σ=σ and µ(u, v) =
σ(u) ∧ σ(v) − µ(u, v) for all u, v in V .

Example 2.2.1 : Figures 2.5(a) and 2.5(b) illustrate a fuzzy

graph and its complement.
2.2. OPERATIONS ON FUZZY GRAPHS 25
u(.8) .5 v(.5) u(.8) v(.5)

.5
.3
.7 .2
.5

w(.7) x(.5) w(.7) .5 x(.5)

Fig.2.5(a) Fig.2.5(b)
Fuzzy graph G = (σ, µ) Complement G = (σ, µ)

Definition 2.2.2 : A fuzzy graph G is self-complementary if

G = G.

Example 2.2.2 : The fuzzy graph given in fig.2.6 is self

complementary.

x(.4) w(.4)
.4

.4
.4

u(.8) v(.4)
Fig.2.6: Self-complementary fuzzy graph

Theorem 2.2.1 : If G = (σ, µ) is a self-complementary fuzzy

graph, then
X 1X
µ(u, v) = (σ(u) ∧ σ(u))
u6=v
2 u6=v
26 CHAPTER 2. FUZZY GRAPH

Proof : Let G = (σ, µ) be a self-complementary fuzzy graph.

Then there exists an isomorphism f : V → V such that

σ(f (u)) = σ(u)

for all u ∈ V and

µ(f (u), f (v)) = µ(u, v)

for all u, v ∈ V .
By the definition of G, it follows that

µ(f (u), f (v)) = σ(f (u) ∧ σ(f (v)) − µ(f (u), f (v))

i.e., µ(u, v) = σ(u) ∧ σ(v) − µ(f (u), f (v))

i.e., µ(u, v) + µ(f (u), f (v)) = σ(u) ∧ σ(v)

P P P
i.e., µ(u, v) + µ(f (u), (v)) = (σ(u) ∧ σ(v))
u6=v u6=v u6=v

P P
i.e., 2 µ(u, v) = (σ(u) ∧ σ(v))
u6=v u6=v

P 1
P
i.e., µ(u, v) = 2
(σ(u) ∧ σ(v))
u6=v u6=v

Hence the theorem. 

The converse of the theorem 2.2.1, in general, is not true.

Theorem 2.2.2 : If G = (σ, µ) be a fuzzy graph such that

1
µ(u, v) = (σ(u) ∧ σ(v))
2
for all u, v ∈ V then G is self-complementary.
2.2. OPERATIONS ON FUZZY GRAPHS 27

Proof : Let G = (σ, µ) be a fuzzy graph such that

1
µ(u, v) = (σ(u) ∧ σ(v))
2

for all u, v ∈ V . Then G = G under the identity map on V. 

Now we discuss the binary operations on fuzzy graphs.

Let G1 = (σ1 , µ1 ) and G2 = (σ2 , µ2 ) be two fuzzy graphs with
the underlying crisp graphs G∗1 = (V1 , E1 ) and G∗2 = (V2 , E2 )
respectively.

2.2.2 Cartesian product and composition

Consider the Cartesian product G = G1 × G2 , =

(V, X) of graphs G1 , and G2 . Then V = V1 × V2 ,
and X = {((u, u2 ), (u, v2 )) | u ∈ V1 , (u2 , v2 ) ∈ X2 } ∪
{((u1 , w), (v1 , w)) | w ∈ V2 , (u1 , v1 ) ∈ X1 }. Using these
notations, the following operations are defined.

Definition 2.2.3 : Let σi , be a fuzzy subset of Vi and let µi be

a fuzzy subset of Xi , i = 1, 2. Define the fuzzy subsets σ1 × σ2
of V and µ1 × µ2 of X as follows:
(σ1 × σ2 )(u1 , u2 ) = min{σ1 (u1 ), σ2 (u2 )} ∀(u1 , u2 ) ∈ V
(µ1 × µ2 )((u, u2 ), (u, v2 )) = min{σ1 (u1 ), µ2 (u2 , v2 )}
∀u ∈ V1 and ∀(u2 , v2 ) ∈ X2
(µ1 × µ2 )((u1 , w), (v1 , w)) = min{σ2 (w), µ1 (u1 , v1 )}
∀w ∈ V2 and ∀(u1 , v1 ) ∈ X1 ,
Then the fuzzy graph G = (σ1 × σ2 , µ1 × µ2 ) is said to be
the cartesian product of G1 = (σ1 , µ1 ) and G2 = (σ2 , µ2 ).
28 CHAPTER 2. FUZZY GRAPH

Example 2.2.3 : The following example illustrates the carte-

sian product of G1 = (σ1 , µ1 ) and G2 = (σ2 , µ2 )

u1 (.8)

.5
.3 .7
u2 (.3) v2 (.9) w2 (1)
v1 (.6)
Fuzzy graphs G1 = (σ1 , µ1 ) and G2 = (σ2 , µ2 )

(u1 , u2 )(.3) (u1 , v2 )(.8) (u1 , w2 )(.8)

.3 .7

.3 .5 .5

.3 .6
(v1 , u2 )(.3) (v1 , v2 )(.6) (v1 , w2 )(.6)

Fig.2.5: Cartesian product G1 × G2

Theorem 2.2.3 : Let G be the Cartesian product of graphs

G1 , and G2 . Let Gi = (σi , µi ) be respectively fuzzy graphs of
Gi , i = 1, 2. Then G = (σ1 × σ2 , µ1 × µ2 ) is fuzzy graph of G.

Proof :

(µ1 × µ2 )((u, u2 ), (u, v2 ))=min{σ1 (u1 ), µ2 (u2 , v2 )}

≤ min{σ1 (u1 ), min{σ(u2 ), σ(v2 )}}
= min{σ1 (u1 ), σ(u2 )}, min{σ(u1 ), σ(v2 )}}
= min{(σ1 × σ)(u1 , u2 ), (σ1 × σ)(u1 , v2 )}
2.2. OPERATIONS ON FUZZY GRAPHS 29

Similarly,
(µ1 ×µ2 )((u1 , w)(v1 , w)) ≤ min{(σ1 ×σ)(u1 , w), (σ1 ×σ)(v1 , w)} 

The fuzzy graph G = (σ1 × σ2 , µ1 × µ2 ) of theorem 2.2.3 is

called the product of G1 = (σ1 , µ1 ) and G2 = (σ2 , µ2 ).

Theorem 2.2.4 : Suppose that G is the Cartesian product of

two fuzzy graphs G1 and G2 . Let (σ, µ) be a fuzzy graph of G.
Then (σ, µ) is a Cartesian product of a fuzzy graph of G1 and
a fuzzy graph of G2 if and only if the following equations have
solutions for xi , yj , zjk , and wih , where V1 = {v11 , v12 , . . . , v1m }
and V2 = {v21 , v22 , . . . , v2m }:

min{xi , yj } = σ(v1i , v2j ) i = 1, . . . , n ; j = 1, . . . , m (2.1)

min{xi , zjk } = µ((v1i , v2j ), (v1i , v2k )) i = 1, . . . , n (2.2)
and j, k are such that(v2i , v2k ) ∈ X2
min{yi , wih } = µ((v1i , v2j ), (v1k , v2j )) j = 1, . . . , m (2.3)
and i, h are such that (v1i , v1h ) ∈ X1

Proof : Suppose that the system of equations given by

(2.1),(2.2) and (2.3) has a solution. Consider an arbitrary, but
fixed, j, k in equations (2.2) and i, h in equations (2.3). Let
z̃jk = max{µ((vi , v2j ), (v1i , v2k )) | i = 1, . . . , n} and w̃ih =
max{µ((vi , v2j ), (v1h , v2j )) | j = 1, . . . , m} Set J = {(j, k) | j, k
are such that (v2i , v2k ) ∈ X2 } and I = {(i, h) | i, h are such
that (v1i , v1h ) ∈ X1 }. Now if {x1 , . . . , xn } ∪ {zjk | (j, k) ∈
J} ∪ {y1 , . . . , ym } ∪ {wih | (i, h) ∈ I} is any solution to (2.1),(2.2)
and (2.3), then {x1 , . . . , xn } ∪ {z̃jk | (j, k) ∈ J} ∪ {y1 , . . . , ym } ∪
{w̃ih | (i, h) ∈ I} is also a solution and, in fact, z̃jk is the
smallest possible zjk and w̃ih is the smallest possible wih . Fix
30 CHAPTER 2. FUZZY GRAPH

such a solution and define the fuzzy subsets σ1 , σ2 , µ1 and µ2 of

V1 , V2 , X1 , and X2 respectively, as follows:

σ(v1i ) = xi for i = 1, . . . , m
σ(v2j ) = yj for j = 1, . . . , n
µ(v2j , v2k ) = z̃jk for j, k such that (v2j , v2k ) ∈ X2
µ(v1i , v1h ) = w̃ih for i, h such that (v1i , v1h ) ∈ X1

For any fixed j, k,

µ( (v1i , v2j ), (v1i , v2k )) ≤ min{σ(v1i , v2j ), σ(v1i , v2k )}

= min{min{σ1 (v1i ), σ2 (v2j )}, min{σ1 (v1i ), σ2 (v2k )}}
≤ min{σ2 (v2j ), σ2 (v2k )} for i = 1, . . . , n

Thus z̃jk = max{µ((v1i , v2j ), (v1i , v2k )) | i = 1, . . . , n} ≤

min{σ2 (v2j ), σ2 (v2k )} Hence µ2 (v2j , v2k ) ≤ min{σ2 (v2j ), σ2 (v2k )}.
Thus (σ2 , µ2 ) is a fuzzy subgraph of G2 . Similarly, (σ1 , µ1 ) is
a fuzzy subgraph of G1 . Clearly, σ = σ1 × σ2 and µ = µ1 µ2 .
Conversely, suppose that (σ, µ) is the Cartesian product of fuzzy
subgraphs of G1 and G2 . Then solutions to equations (2.1),(2.2)
and (2.3) exist by definition of cartesian product. 

Remark 2.2.1 : Consider an arbitrary fixed solution to

equations (2.1),(2.2) and (2.3) as determined in the proof of
Theorem 2.2.4 (assuming one exists).

(a) Let (j, k) ∈ J and let I ′ = {ijk ⊂ z̃jk =

µ((v1ijk , v2j ), (v1ijk , v2k ))} in Theorem 2.2.4. If xijk > z̃jk for
some ijk ∈ I ′ , then zjk is unique for these particular x1 , . . . , xn ,
and equals z̃jk if xijk = zjk ∀ijk ∈ I ′ , then z̃jk ≤ zjk ≤ 1 for these
particular x1 , . . . , xn .
2.2. OPERATIONS ON FUZZY GRAPHS 31

(b) Let (i, h) ∈ I and let J ′ = {iih ⊂ w̃ih =

µ((v1iih , v2i ), (v1iih , v2h ))} in Theorem 2.2.4. If xiih > w̃ih for
some iih ∈ J ′ , then wih is unique for these particular y1 , . . . , ym ,
and equals w̃ih if xiih = wih ∀iih ∈ J ′ , then w̃ih ≤ wih ≤ 1 for
these particular y1 , . . . , ym .

Example 2.2.4 : Let V1 = {v11 , v12 }, V1 = {v21 , v22 },

X1 = {(v11 , v12 )} and X2 = {(v21 , v22 )} Let σ((v11 , v21 )) =
1
4
, σ((v11 , v22 )) = 12 , σ((v12 , v21 )) = 18 and σ((v12 , v22 )) = 85 . Then
(σ, µ) is not a Cartesian product of fuzzy subgraphs of G1 and
G2 for any choice of µ because equations (2.1) of Theorem 2.2.4
are inconsistent:
min{x1 , y1 } = 14 , min{x1 , y2 } = 21 , min{x2 , y1 } = 81 ,min{x2 , y2 } =
5
8
, is impossible.

Examples are easily constructed where equations (2.1) have a

solution, but either equations (2.2) or (2.3) are inconsistent.
We now consider the composition of two fuzzy graphs.

Definition 2.2.4 : Let G1 [G2 ] denote the composition of graph

G1 = (V1 , X1 ) with graph G2 = (V2 , X2 ). Now G1 [G2 ] =
(V1 × V2 , X 0 ), where X 0 = X ∪ {((u1 , u2 ), (v1 , v2 )) | (u1 , v1 ) ∈
X1 , u2 6= v2 } and where X is defined as in the case for G1 × G2 .
Let σi be a fuzzy subset of Vi and let µi be a fuzzy subset of
Xi , i = 1, 2. Define the fuzzy subsets σ1 ◦ σ2 and µ1 ◦ µ2 of
V1 × V2 and X 0 , respectively, as follows:
(σ1 ◦ σ2 )(u1 , u2 ) = min{σ1 (u1 ), σ2 (u2 )} ∀(u1 , u2 ) ∈ V1 × V2
(µ1 ◦ µ2 )((u, u2 ), (u, v2 )) = min{σ1 (u), µ2 (u2 , v2 )}
∀u ∈ V1 , (u2 , v2 ) ∈ X2
32 CHAPTER 2. FUZZY GRAPH

(µ1 ◦ µ2 )((u1 , w), (v1 , w)) = min{σ2 (w), µ1 (u1 , v1 )}

∀w ∈ V2 , (u1 , v1 ) ∈ X1
(µ1 ◦ µ2 )((u1 , u2 ), (v1 , v2 )) = min{σ2 (u2 ), σ2 (v2 )µ1 (u1 , v1 )}
∀((u1 , u2 ), (v1 , v2 )) ∈ X 0 − X
The fuzzy graph G = (σ1 ◦ σ2 , µ1 ◦ µ2 ) is the composition of
G = (σ1 , µ1 ) and G = (σ2 , µ2 ).

Example 2.2.5 : The following fuzzy graphs illustrate the

composition of G1 = (σ1 , µ1 ) and G2 = (σ2 , µ2 )
u1 (.8)

.5
.3 .7
u2 (.3) v2 (.9) w2 (1)
v1 (.6)
Fuzzy graphs G1 and G2

(u1 , u2 )(.3) (u1 , v2 )(.8) (u1 , w2 )(.8)

.3 .7
.3 .3
.5
.3 .5
.3 .5
.3 .5

.3 .6
(v1 , u2 )(.3) (v1 , v2 )(.6) (v1 , w2 )(.6)

Fig.2.6: Composition G1 [G2 ]

Theorem 2.2.5 : Let G be the composition G1 [G2 ] of graph

G1 , with graph G2 . Let (σi , µi ) be a fuzzy subgraph of Gi , i =
1, 2. Then (σ1 ◦ σ2 , µ1 ◦ µ2 ) is a fuzzy subgraph of G1 [G2 ].
2.2. OPERATIONS ON FUZZY GRAPHS 33

Proof : We have already seen in the proof of the-

orem 2.2.3 that (µ1 ◦ µ2 )((u1 , u2 ), (v1 , v2 )) ≤ min{(σ1 ◦
σ2 )((u1 , u2 )), (σ1 ◦ σ2 )((v1 , v2 ))}∀((u1 , u2 ), (v1 , v2 )) ∈ X. Suppose
that ((u1 , u2 ), (v1 , v2 )) ∈ X 0 − X and so (u1 , v1 ) ∈ X1 , u2 6= v2 .
Then

(µ1 ◦ µ2 )((u1 , u2 )(v1 , v2 )) ≤ min{σ2 (u2 ), σ2 (v2 ), µ1 (u1 , v1 )}

≤ min{σ2 (u2 ), σ2 (v2 ), min{σ1 (u1 ), σ1 (v1 )}}
= min{min{σ1 (u1 ), σ2 (u2 )}, min{σ1 (v1 ), σ2 (v2 )}}
= min{(σ1 ◦ σ2 )((u1 , u2 )), (σ1 ◦ σ2 )((v1 , v2 ))}

The fuzzy graph (σ1 ◦ σ2 , µ1 ◦ µ2 ) of theorem 2.2.5 is called

the composition of (σ1 , µ1 ) with (σ2 , µ2 ). 

Theorem 2.2.6 : Suppose that G is the composition G1 [G2 ] of

two graphs G1 and G2 . Let (σ, µ) be a fuzzy graph of G. Consider
the following equations: (2.1),(2.2) and (2.3) of Theorem 2.2.4
and min{yj , yk , wih } =

µ((v1i , v2j )(vlh , v2k ))where ((v1i , v2j ), (vlh , v2k )) ∈ X0 − X (2.4)

A necessary condition for (σ, µ) to be a composition of fuzzy

subgraphs of G1 and G2 , is that a solution to equations (2.1)-
(2.4) exists. Suppose that a solution to equations (2.1)-(2.4)
exists. If w̃ih ≥ µ((v1i , v2j )(vlh , v2k )) ∀i, h ∈ I such that
((v1i , v2j ), (vlh , v2k )) ∈ X 0 − X, then (σ, µ) is a composition of
fuzzy subgraphs of G1 and G2 .

Proof : The necessary part of the theorem is clear. Suppose

that a solution to equations (2.1)-(2.4) exists. Then there exists
a solution to equations (2.1)-(2.4) as determined in the proof of
34 CHAPTER 2. FUZZY GRAPH

Theorem 2.2.4 for equations (2.1)-(2.3) because every wih ≥ w̃ih ,

and by the hypothesis concerning the w̃ih . Thus if σi , µi , i = 1, 2,
are defined as in the proof of Theorem 2.2.4, we have that (σi , µi )
is a fuzzy subgraph of Gi , i = 1, 2, and σ = σ1 ◦σ2 and µ = µ1 ◦µ2


Example 2.2.6 : Let G1 = (V1 , X1 ) and G2 = (V2 , X2 ) be

graphs and let σ1 , σ2 , µ1 and µ2 , be fuzzy subsets of V1 , V2 , X1
and, X2 , respectively. Then (σ1 × σ2 , µ1 µ2 ) is a fuzzy subgraph
of G1 × G2 , but (σi , µi ) is not a fuzzy subgraph of Gi , i =
1, 2: Let V1 = {u1 , v1 }, V2 = {u2 , v2 }, X1 = {(u1 , v1 )} and
X2 = {(u2 , v2 )}. Define the fuzzy subsets σ1 , σ2 , µ1 and µ2
as follows: σ1 (u1 ) = σ1 (v1 ) = σ2 (u2 ) = σ2 (v2 ) = 21 and
µ1 (u1 , v1 ) = µ2 (u2 , v2 ) = 34 . Then (σi , µi ) is not a fuzzy subgraph
of Gi , i = 1, 2. Now for x ∈ V1 and y ∈ V2 ,

(µ1 µ2 )((x, u2 )(x, v2 )) = min{σ1 (x), µ2 (u2 , v2 )} = 12

= min{σ1 (x), σ2 (u2 ), σ2 (v2 )}
= min{min{σ1 (u1 ), σ2 (u2 )}, min{σ1 (v1 ), σ2 (v2 )}}
= min{(σ1 × σ2 )((x, u2 )), (σ1 × σ2 )((x, v2 ))}

and similarly,
(µ1 µ2 )((u1 , y)(v1 , y)) = min{(σ1 × σ2 )((u1 , y)), (σ1 × σ2 )((v1 , y))}
Thus (σ1 × σ2 , µ1 µ2 ) is a fuzzy subgraph of G1 × G2 . We
also note that for x1 y1 ∈ X1 , and

x2 , y2 ∈ V2 , (µ1 ◦ µ2 )((x1 , x2 )(y1 , y2 ))

=min{σ2 (x2 ), σ2 (y2 ), µ1 (x1 , y1 )} = 12
= min{(σ1 × σ2 )((x1 , x2 )), (σ1 × σ2 )((y1 , y2 ))}

Thus (σ1 ◦ σ2 , µ1 ◦ µ2 ) is a fuzzy subgraph of G1 [G2 ].

2.2. OPERATIONS ON FUZZY GRAPHS 35

We would also like to note that in Example 2.2.6, (σ1 ×

σ2 , µ1 µ2 ) satisfies the conditions in Theorem 2.2.4 Hence (σ1 ×
σ2 , µ1 µ2 ) is the Cartesian product of fuzzy subgraphs (ωi , τi ) of
Gi , i = 1, 2. In fact, these ωi and τi , (i = 1, 2) are constant
membership functions with membership value 21 .

2.2.3 Union and Join

Definition 2.2.5 : Consider the union G = G1 ∪ G2 , of two

graphs G1 = (Vi , Xi ) and G2 = (V2 , X2 ). Let σi be a fuzzy
subset of Vi and let µi be a fuzzy subset of Xi , i = 1, 2. Define
the fuzzy subsets σ1 ∪ σ2 of V1 ∪ V2 , and µ1 ∪ µ2 of X1 ∪ X2 as
follows.

(σ1 ∪ σ2 )(u) = σ1 (u) if u ∈ V1 − V2 ,

(σ1 ∪ σ2 )(u) = σ2 (u) if u ∈ V2 − V1 , and
(σ1 ∪ σ2 )(u) = max{σ1 (u), σ2 (u)} if u ∈ V1 ∩ V2 ,
(µ1 ∪ µ2 )(u, v) = µ1 (u, v) if (u, v) ∈ X1 − X2 ,
(µ1 ∪ µ2 )(u, v) = µ2 (u, v) if (u, v) ∈ X2 − X1 , and
(µ1 ∪ µ2 )(u, v) = max{µ1 (u, v), µ2 (u, v)} if (u, v) ∈ X1 ∩ X2 ,

The fuzzy graph G = (σ1 ∪ σ2 , µ1 ∪ µ2 ) is the union of the fuzzy

graphs G = (σ1 , µ1 ) and G = (σ2 , µ2 ).

Example 2.2.7 : The following fuzzy graphs illustrate the

union of G1 = (σ1 , µ1 ) and G2 = (σ2 , µ2 )
36 CHAPTER 2. FUZZY GRAPH

u1 (.7) w1 (.5) x(.9) .4 y(.4)

.7 .2 .2 .3

.3 .1
v1 (.9) x(.4) y(.6) u2 (.2) v2 (.7)
Fuzzy graphs G1 and G2
u1 (.7) w1 (.5)

.7 .2

.3 x(.9) y(.6)
v1 (.9) .4

.2 .3

u2 (.2) v2 (.7)
Fig.2.7: Union G1 ∪ G2

Theorem 2.2.7 : Let G be the union of the graphs G1 and

G2 . Let (σi , µi ) be a fuzzy sub graph of G, , i = 1, 2. Then
(σ1 ∪ σ2 , µ1 ∪ µ2 ) is a fuzzy subgraph of G.

Proof : Suppose that (u, v) ∈ X1 − X2 . Then

(µ1 ∪ µ2 )(u, v) = µ1 (u, v) = min{σ1 (u), σ2 (v)}
= min{(σ1 ∪ σ2 )(u), (σ1 ∪ σ2 )(v)} if u, v ∈ V1 − V2
= min{(σ1 ∪ σ2 )(u), max{σ1 (v), σ2 (v)}}
= min{(σ1 ∪ σ2 )(u), (σ1 ∪ σ2 )(v)}
if u ∈ V1 − V2 , v ∈ V1 ∩ V2
2.2. OPERATIONS ON FUZZY GRAPHS 37

≤ min{max{σ1 (u), σ2 (u)}, max{σ1 (v), σ2 (v)}}

= min{(σ1 ∪ σ2 )(u), max{σ1 (v), σ2 (v)}}
if u, v ∈ V1 ∩ V2

Similarly, if (u, v) ∈ X2 − X1 , then (µ1 ∪ µ2 )(u, v) ≤ min{(σ1 ∪

σ2 )(u), (σ1 ∪ σ2 )(v)}. Suppose (u, v) ∈ X1 ∩ X2 . Then

(µ1 ∪ µ2 )(u, v)= max{µ1 (u, v), µ2 (u, v)}

≤ max{min{σ1 (u), (σ1 (v)}, min{σ2 (u), (σ2 (v)}}
≤ max{min{σ1 (u), (σ2 (u)}, min{σ1 (u), (σ2 (v)}}
= min{(σ1 ∪ σ2 )(u), (σ1 ∪ σ2 )(v)}

The fuzzy subgraph (σ1 ∪ σ2 , µ1 ∪ µ2 ) ) of theorem 2.2.7 is called

the union of (σ1 , µ1 ) and (σ2 , µ2 ). 

Theorem 2.2.8 : If G is a union of two fuzzy graphs G1 , and

G2 , then every fuzzy graph (σ, µ) is a union of a fuzzy graph of
G1 , and a fuzzy subgraph of G2 .

Proof : Define the fuzzy sets σ1 , σ2 , µ1 and µ2 of V1 , V2 , X1 ,

and X2 respectively as follows: σi (u) = σ(u) if u ∈ Vi and
µi (u, v) = µ(u, v) if (u, v) ∈ Xi , i = 1, 2. Then

µi (ui , vi ) = µ(ui , vi ) ≤ min{σ(ui ), σ(vi )}

= min{σi (ui ), σi (vi )} if (ui , vi ) ∈ Xi , i = 1, 2.

Thus (σi , µi ) is a fuzzy subgraph of Gi , i = 1, 2. Clearly, σ =

σ1 ∪ σ2 and µ = µ1 ∪ µ2 

Remark 2.2.2 : Union of two fuzzy graphs is a fuzzy graph.

38 CHAPTER 2. FUZZY GRAPH

Definition 2.2.6 : Consider the join G = G1 + G2 = (V1 ∪

V2 , X1 ∪ X2 ∪ X ′ ) of graphs G1 = (V1 , X1 ) and G2 = (V2 , X2 ),
where X ′ is the set of all edges joining the nodes of V1 and V2
and where we assume V1 ∩ V2 = φ. Let σi be a fuzzy subset of
Vi and µi a fuzzy subset of Xi , i = 1, 2. Define the fuzzy subsets
σ1 + σ2 of V1 ∪ V2 and µ1 + µ2 of X1 ∪ X2 ∪ X ′ as follows:
(σ1 + σ2 )(u) = (σ1 ∪ σ2 )(u) ∀ u ∈ V1 ∪ V2
(µ1 + µ2 )(u, v) = (µ1 ∪ µ2 )(u, v) if (u, v) ∈ X1 ∪ X2 and
(µ1 + µ2 )(u, v) = min{σ1 (u), σ2 (v)} if (u, v) ∈ X ′
The fuzzy graph G(σ1 + σ2 , µ1 + µ2 ) is the join of the fuzzy
graphs G(σ1 , µ1 ) and G(σ2 , µ2 ).
Example 2.2.8 : The following fuzzy graphs illustrate the join
of G1 (σ1 , µ1 ) and G2 (σ2 , µ2 )
u2 (.8) u2 (.8)

.7
u1 (.7) u1 (.7)
.8 .8 .8
.7
v2 (.9) v2 (.9)
.6 .6 .9

.7 .4 .7
v1 (1) v1 (1)
.4
w2 (.4) w2 (.4)

Fig.2.8: Fuzzy graphs G1 ,G2 and join G1 + G2

Theorem 2.2.9 : Let G be the join of the graphs G1 and
G2 . Let (σi , µi ) be a fuzzy sub graph of G, , i = 1, 2. Then
(σ1 + σ2 , µ1 + µ2 ) is a fuzzy subgraph of G.
2.2. OPERATIONS ON FUZZY GRAPHS 39

Proof : Suppose at (u, v) ∈ X1 ∪ X2 . Then the desired result

follows from theorem 2.2.7. Suppose that (u, v) ∈ X ′ . Then

(µ1 + µ2 )(u, v) = min{σ1 (u), σ2 (v)}

= min{(σ1 ∪ σ2 )(u), (σ1 ∪ σ2 )(v)}
= min{(σ1 + σ2 )(u), (σ1 + σ2 )(v)} 

Theorem 2.2.10 : If G is the join of two subgraphs G1 and G2 ,

then every strong fuzzy subgraph (σ, µ) of G is a join of a strong
fuzzy subgraph of G1 and a strong fuzzy subgraph of G2 .

Proof : Define the fuzzy subsets σ1 , σ2 , µ1 and µ2 of V1 , V2 , X1 ,

and X2 respectively as follows: σi (u) = σ(u) if u ∈ Vi and
µi (u, v) = µ(u, v) if (u, v) ∈ Xi , i = 1, 2. Then (σi , µi ) is a
fuzzy subgraph of Gi , i = 1, 2. and σ = σ1 + σ2 as in the
proof of Theorem 2.2.8. If (u, v) ∈ X1 ∪ X2 , then µ(u, v) =
(µ1 + µ2 )(u, v) as in the proof of Theorem 2.2.8. Suppose that
(u, v) ∈ X ′ , where u ∈ V1 and v ∈ V2 . Then (µl + µ2 )(u, v) =
min{σ1 (u), σ2 (v)} = min{σ(u), σ(v)} = µ(u, v), where the latter
equality holds because (σ, µ) is strong. 

Example 2.2.9 : Let G1 = (V1 , X1 ) and G2 = (V2 , X2 ) be

graphs and let σ1 , σ2 , µ1 and µ2 , be fuzzy subsets of V1 , V2 , X1
and, X2 , respectively. Then (σ1 ∪ σ2 , µ1 ∪ µ2 ) is a fuzzy subgraph
of G1 ∪ G2 , but (σi , µi ) is not a fuzzy subgraph of Gi , i = 1, 2:
Let V1 = V2 − {u, v} and X1 = X2 = {(u, v)}. Define the
fuzzy subsets σ1 , σ2 , µ1 and µ2 of V1 , V2 , X1 and X2 respectively
as follows: σ1 (u) = 1 = σ2 (v), σ1 (v) = 41 = σ2 (u), µ1 (u, v) = 12 =
µ2 (u, v). Then (σi , µi ) is not a fuzzy subgraph of Gi , i = 1, 2.
40 CHAPTER 2. FUZZY GRAPH

Now

(µ1 ∪ µ2 )(u, v) = max{µ1 (u, v), µ2 (u, v)} = 12 < 1

= min{max{(σ1 (u), σ2 )(u), max{σ1 (v), σ2 (v)}}
= min{(σ1 ∪ σ2 )(u), (σ1 ∪ σ2 )(v)}

Thus (σ1 ∪ σ2 , µ1 ∪ µ2 ) is a fuzzy subgraph of G1 ∪ G2 . The

preceding example can easily be extended to the case where
V1 * V2 , V2 * V1 , X1 * X2 and X2 * X1 , as follows: Let
V1 = {u, u, w}, V2 = {u, u, z}, X1 = {(u, v), (u, w)}, X2 =
{(u, v), (v, z)} and σ1 (w) = σ2 (z) = 1 = µ(u, w) = µ(u, z).

Theorem 2.2.11 : Let G1 = (V1 , X1 ) and G2 = (V2 , X2 ) be

graphs. Suppose that V1 ∩V2 = φ. Let σ1 , σ2 , µ1 and µ2 , be fuzzy
subsets of V1 , V2 , X1 and, X2 , respectively. Then (σ1 ∪σ2 , µ1 ∪µ2 )
is a fuzzy subgraph of G1 ∪ G2 if and only if (σ1 , µ1 ) and (σ2 , µ2 )
are fuzzy subgraphs of G1 and G2 respectively.

Proof : . Suppose that (σ1 ∪ σ2 , µ1 ∪ µ2 ) is a fuzzy subgraph of

G1 ∪ G2 . Let (u, v) ∈ X1 . Then (u, v) ∈ / X2 , and u, v ∈ V1 − V2 .
Hence µ(u, v) = (µ1 ∪ µ2 )(u, v) ≤ min{(σ1 ∪ σ2 )(u), (σ1 ∪
σ2 )(v)} = min{σ1 (u), σ1 (v)}. Thus (σ1 , µ1 ) is a fuzzy subgraph
of G1 . Similarly, (σ2 , µ2 ) is a fuzzy subgraph of G2 . The converse
is nothing but the theorem 2.2.7 which we proved already. 

Theorem 2.2.12 : Let G1 = (V1 , X1 ) and G2 = (V2 , X2 ) be

graphs. Suppose that V1 ∩V2 = φ. Let σ1 , σ2 , µ1 and µ2 , be fuzzy
subsets of V1 , V2 , X1 and, X2 , respectively. Then (σ1 +σ2 , µ1 +µ2 )
is a fuzzy subgraph of G1 + G2 if and only if (σ1 , µ1 ) and (σ2 , µ2 )
are fuzzy subgraphs of G1 and G2 respectively.
2.2. OPERATIONS ON FUZZY GRAPHS 41

Proof : The desired result follows from the proof of Theorem

2.2.11 and theorem 2.2.9. 

Theorem 2.2.13 : Let G1 : (σ1 , µ1 ) and G2 : (σ2 , µ2 ) be two

fuzzy graphs. Then i. G1 + G2 = G1 ∪ G2 and ii. G1 ∪ G2 =
G1 + G2

Proof : We shall prove that the identity map is the required

isomorphism. Let I : V1 ∪ V2 → V1 ∪ V2 be the identity
map. Then it is required to prove σ1 + σ2 (u) = σ 1 ∪ σ 2 (u) and
µ1 + µ2 (u, v) = µ1 ∪ µ2 (u, v).
σ1 + σ2 (u) = (σ1 + σ2 )(u) by the definition of compliment.
(
σ1 (u) if u ∈ V1
σ1 + σ2 (u) =
σ2 (u) if u ∈ V2
(
σ 1 (u) if u ∈ V1
=
σ 2 (u) if u ∈ V2

= σ 1 ∪ σ 2 (u)

µ1 + µ2 (u, v) = (σ1 + σ2 )(u) ∧ (σ1 + σ2 )(v) − (µ1 + µ2 )(u, v)



 (σ1 ∪ σ2 )(u) ∧ (σ1 ∪ σ2 )(v) − (µ1 + µ2 )(u, v)

 if (u, v) ∈ E1 ∪ E2
=

 (σ1 ∪ σ2 )(u) ∧ (σ1 ∪ σ2 )(v) − (σ1 (u) ∧ σ2 )(v)


if (u, v) ∈ E′


 σ1 (u) ∧ σ1 (v) − µ1 (u, v) if (u, v) ∈ E1

 σ (u) ∧ σ (v) − µ (u, v) if (u, v) ∈ E
2 2 2 2
=


 σ1 (u) ∧ σ2 (v) − σ1 (u) ∧ σ2 (v) if (u, v) ∈ E′

where u ∈ V1 , v ∈ V2
42 CHAPTER 2. FUZZY GRAPH


 µ1 (u, v) if (u, v) ∈ E1

= µ2 (u, v) if (u, v) ∈ E2


0 if (u, v) ∈ E′
= µ1 ∪ µ2 (u, v)

Now we prove the second result.

To prove σ1 ∪ σ2 (u) = σ 1 + σ 2 (u) and µ1 ∪ µ2 (u, v) = µ1 +
µ2 (u, v).

σ1 ∪ σ2 (u) = (σ1 ∪ σ2 )(u)

(
σ1 (u) if u ∈ V1
=
σ2 (u) if u ∈ V2
(
σ 1 (u) if u ∈ V1
=
σ 2 (u) if u ∈ V2

= (σ 1 ∪ σ 2 )(u)

= (σ 1 + σ 2 )(u)

µ1 ∪ µ2 (u, v) = (σ1 ∪ σ2 )(u) ∧ (σ1 ∪ σ2 )(v) − (µ1 ∪ µ2 )(u, v)


 σ1 (u) ∧ σ1 (v) − µ1 (u, v) if (u, v) ∈ E1

= σ2 (u) ∧ σ2 (v) − µ2 (u, v) if (u, v) ∈ E2


σ1 (u) ∧ σ2 (v) − 0; whenu ∈ V1 , v ∈ V2

 µ1 (u, v) if (u, v) ∈ E1

= µ2 (u, v) if (u, v) ∈ E2


σ1 (u) ∧ σ2 (v); whenu ∈ V1 , v ∈ V2
2.2. OPERATIONS ON FUZZY GRAPHS 43
(
µ1 ∪ µ2 (u, v); if (u, v) ∈ E1 or E2
=
σ1 (u) ∧ σ2 (v); if (u, v) ∈ E′
= µ1 + µ2 (u, v)

Exercise
1. Give an example of a fuzzy graph so that
X 1X
µ(u, v) = (σ(u) ∧ σ(u))
u6=v
2 u6=v

but not self-complementary.

2. Let G1 = (σ1 , µ1 ) and G2 = (σ2 , µ2 ) be two strong fuzzy

graphs. Then show that G1 ◦ G2 is a strong fuzzy graph
and G1 ◦ G2 = G1 ◦ G2 .

3. Give examples of G1 = (σ1 , µ1 ) and G2 = (σ2 , µ2 ) such

that G1 ◦ G2 6= G1 ◦ G2 .