Bipartite Graphs

Graph Theory
Bipartite graphs

A Senthil Thilak

Department of Mathematical and Computational Sciences

National Institute of Technology Karnataka

Graph Theory A Senthil Thilak

Bipartite Graphs

Preliminaries

Outline

1 Bipartite Graphs
Preliminaries
Bipartite graphs - Definition and examples
Characterization of bipartite graphs
Complete bipartite graphs

Graph Theory A Senthil Thilak

Bipartite Graphs

Preliminaries

Distance in graphs
Definition (Distance between two vertices)
Let u and v be two vertices of G . If u and v are in the same
component of G , then the distance between u and v , denoted
by dG (u, v) (or simply by d(u, v)) is the length of a shortest
u, v -path in G ; otherwise we define d(u, v ) to be ∞.

Example

In the graph given above, notice that the following are u, y -paths:

Graph Theory A Senthil Thilak

Bipartite Graphs

Preliminaries

Distance in graphs
Definition (Distance between two vertices)
Let u and v be two vertices of G . If u and v are in the same
component of G , then the distance between u and v , denoted
by dG (u, v) (or simply by d(u, v)) is the length of a shortest
u, v -path in G ; otherwise we define d(u, v ) to be ∞.

Example

In the graph given above, notice that the following are u, y -paths:
P 0 = (u, v , y ) P 00 = (u, w , v , y ) P 000 = (u, v , w , x, y )

Graph Theory A Senthil Thilak

Bipartite Graphs

Preliminaries

Distance in graphs
Definition (Distance between two vertices)
Let u and v be two vertices of G . If u and v are in the same
component of G , then the distance between u and v , denoted
by dG (u, v) (or simply by d(u, v)) is the length of a shortest
u, v -path in G ; otherwise we define d(u, v ) to be ∞.

Example

In the graph given above, notice that the following are u, y -paths:
P 0 = (u, v , y ) P 00 = (u, w , v , y ) P 000 = (u, v , w , x, y )
0
Here, P is a shortest u, y -path and is of length 2. Therefore,

Graph Theory A Senthil Thilak

Bipartite Graphs

Preliminaries

Distance in graphs
Definition (Distance between two vertices)
Let u and v be two vertices of G . If u and v are in the same
component of G , then the distance between u and v , denoted
by dG (u, v) (or simply by d(u, v)) is the length of a shortest
u, v -path in G ; otherwise we define d(u, v ) to be ∞.

Example

In the graph given above, notice that the following are u, y -paths:
P 0 = (u, v , y ) P 00 = (u, w , v , y ) P 000 = (u, v , w , x, y )
0
Here, P is a shortest u, y -path and is of length 2. Therefore,
d(u, y) = 2.
Graph Theory A Senthil Thilak
Bipartite Graphs

Preliminaries

Definition (Diameter and Radius of a graph)

Let u ∈ V (G ). Then,
• the distance between u and a vertex farthest from u is
called the eccentricity of u, denoted by ecc(u).

Graph Theory A Senthil Thilak

Bipartite Graphs

Preliminaries

Definition (Diameter and Radius of a graph)

Let u ∈ V (G ). Then,
• the distance between u and a vertex farthest from u is
called the eccentricity of u, denoted by ecc(u).
Thus, ecc(u) = max{d(u, v) : v ∈ V(G)}.
• The maximum distance between any two vertices in a
connected graph G is called the diameter of G , denoted by
diam(G) and the minimum distance between any two vertices
in a connected graph G is called the radius of G , denoted by
rad(G).
Thus, diam(G) = max ecc(u) : u ∈ V(G) and
rad(G) = min ecc(u) : u ∈ V(G)

Graph Theory A Senthil Thilak

Bipartite Graphs

Preliminaries

Definition (Independent sets)

For a graph G = (V , E ), a subset S of V (or E ) is said to be an
independent vertex set (or edge set), if every pair of vertices
(or edges) in S are mutually non-adjacent.

Example

The sets {2, 3} and {2, 4} are

independent vertex sets in G
and {e1 , e4 } is an independent
set of edges in G .

Graph Theory A Senthil Thilak

Bipartite Graphs

Bipartite graphs - Definition and examples

Outline

1 Bipartite Graphs
Preliminaries
Bipartite graphs - Definition and examples
Characterization of bipartite graphs
Complete bipartite graphs

Graph Theory A Senthil Thilak

Bipartite Graphs

Bipartite graphs - Definition and examples

Definition (Bipartite graph)

A graph G = (V , E ) is said to be bipartite if V (G ) can be
partitioned into two non-empty sets X and Y such that both X
and Y are independent. The sets X and Y are said to be partite
sets and the pair (X , Y ) is said to be a bipartition of G .

Graph Theory A Senthil Thilak

Bipartite Graphs

Bipartite graphs - Definition and examples

Definition (Bipartite graph)

A graph G = (V , E ) is said to be bipartite if V (G ) can be
partitioned into two non-empty sets X and Y such that both X
and Y are independent. The sets X and Y are said to be partite
sets and the pair (X , Y ) is said to be a bipartition of G .

Note: If G is a bipartite graph with bipartition (X , Y ), then every

edge of G has one end in X and the other in Y .

Graph Theory A Senthil Thilak

Bipartite Graphs

Bipartite graphs - Definition and examples

Example (Bipartite graphs)

(a) Graph G

Figure: Examples of bipartite graphs

Graph Theory A Senthil Thilak

Bipartite Graphs

Bipartite graphs - Definition and examples

Example (Bipartite graphs)

(a) Graph G

(c) Graph H
Figure: Examples of bipartite graphs

Graph Theory A Senthil Thilak

Bipartite Graphs

Bipartite graphs - Definition and examples

Example (Bipartite graphs)

(b) A bipartition of G
(a) Graph G

(c) Graph H
Figure: Examples of bipartite graphs

Graph Theory A Senthil Thilak

Bipartite Graphs

Bipartite graphs - Definition and examples

Example (Bipartite graphs)

(b) A bipartition of G
(a) Graph G

(c) Graph H (d) A bipartition of H

Figure: Examples of bipartite graphs

Graph Theory A Senthil Thilak

Bipartite Graphs

Bipartite graphs - Definition and examples

Example (Graph which not bipartite)

Figure: A graph that is not bipartite

Graph Theory A Senthil Thilak

Bipartite Graphs

Characterization of bipartite graphs

Outline

1 Bipartite Graphs
Preliminaries
Bipartite graphs - Definition and examples
Characterization of bipartite graphs
Complete bipartite graphs

Graph Theory A Senthil Thilak

Bipartite Graphs

Characterization of bipartite graphs

Theorem (Characterization of bipartite graphs)

A graph G is bipartite if and only if it has no odd cycle.
Proof.
Suppose that G is bipartite with bipartition (X , Y ).

Graph Theory A Senthil Thilak

Bipartite Graphs

Characterization of bipartite graphs

Theorem (Characterization of bipartite graphs)

A graph G is bipartite if and only if it has no odd cycle.
Proof.
Suppose that G is bipartite with bipartition (X , Y ). Let C = v1 v2 . . . vk v1
be a cycle in G .

Graph Theory A Senthil Thilak

Bipartite Graphs

Characterization of bipartite graphs

Theorem (Characterization of bipartite graphs)

A graph G is bipartite if and only if it has no odd cycle.
Proof.
Suppose that G is bipartite with bipartition (X , Y ). Let C = v1 v2 . . . vk v1
be a cycle in G .
Claim:

Graph Theory A Senthil Thilak

Bipartite Graphs

Characterization of bipartite graphs

Theorem (Characterization of bipartite graphs)

A graph G is bipartite if and only if it has no odd cycle.
Proof.
Suppose that G is bipartite with bipartition (X , Y ). Let C = v1 v2 . . . vk v1
be a cycle in G .
Claim: C is an even cycle.

Graph Theory A Senthil Thilak

Bipartite Graphs

Characterization of bipartite graphs

Theorem (Characterization of bipartite graphs)

A graph G is bipartite if and only if it has no odd cycle.
Proof.
Suppose that G is bipartite with bipartition (X , Y ). Let C = v1 v2 . . . vk v1
be a cycle in G .
Claim: C is an even cycle. (i.e, TP: k is even).
WLG, let v1 ∈ X .

Graph Theory A Senthil Thilak

Bipartite Graphs

Characterization of bipartite graphs

Theorem (Characterization of bipartite graphs)

A graph G is bipartite if and only if it has no odd cycle.
Proof.
Suppose that G is bipartite with bipartition (X , Y ). Let C = v1 v2 . . . vk v1
be a cycle in G .
Claim: C is an even cycle. (i.e, TP: k is even).
WLG, let v1 ∈ X . Then, as v1 and v2 are adjacent, v2 ∈ Y .

Graph Theory A Senthil Thilak

Bipartite Graphs

Characterization of bipartite graphs

Theorem (Characterization of bipartite graphs)

A graph G is bipartite if and only if it has no odd cycle.
Proof.
Suppose that G is bipartite with bipartition (X , Y ). Let C = v1 v2 . . . vk v1
be a cycle in G .
Claim: C is an even cycle. (i.e, TP: k is even).
WLG, let v1 ∈ X . Then, as v1 and v2 are adjacent, v2 ∈ Y . Similarly,
v3 ∈ X , v4 ∈ Y and so on.

Graph Theory A Senthil Thilak

Bipartite Graphs

Characterization of bipartite graphs

Theorem (Characterization of bipartite graphs)

A graph G is bipartite if and only if it has no odd cycle.
Proof.
Suppose that G is bipartite with bipartition (X , Y ). Let C = v1 v2 . . . vk v1
be a cycle in G .
Claim: C is an even cycle. (i.e, TP: k is even).
WLG, let v1 ∈ X . Then, as v1 and v2 are adjacent, v2 ∈ Y . Similarly,
v3 ∈ X , v4 ∈ Y and so on. Thus, for each 1 ≤ i ≤ k, vi ∈ X if i is odd
and vi ∈ Y , if i is even.

Graph Theory A Senthil Thilak

Bipartite Graphs

Characterization of bipartite graphs

Theorem (Characterization of bipartite graphs)

A graph G is bipartite if and only if it has no odd cycle.
Proof.
Suppose that G is bipartite with bipartition (X , Y ). Let C = v1 v2 . . . vk v1
be a cycle in G .
Claim: C is an even cycle. (i.e, TP: k is even).
WLG, let v1 ∈ X . Then, as v1 and v2 are adjacent, v2 ∈ Y . Similarly,
v3 ∈ X , v4 ∈ Y and so on. Thus, for each 1 ≤ i ≤ k, vi ∈ X if i is odd
and vi ∈ Y , if i is even. Finally, as v1 ∈ X , vk ∈ Y .

Graph Theory A Senthil Thilak

Bipartite Graphs

Characterization of bipartite graphs

Theorem (Characterization of bipartite graphs)

A graph G is bipartite if and only if it has no odd cycle.
Proof.
Suppose that G is bipartite with bipartition (X , Y ). Let C = v1 v2 . . . vk v1
be a cycle in G .
Claim: C is an even cycle. (i.e, TP: k is even).
WLG, let v1 ∈ X . Then, as v1 and v2 are adjacent, v2 ∈ Y . Similarly,
v3 ∈ X , v4 ∈ Y and so on. Thus, for each 1 ≤ i ≤ k, vi ∈ X if i is odd
and vi ∈ Y , if i is even. Finally, as v1 ∈ X , vk ∈ Y . Thus, k must be
even and hence, C must be an even cycle.
Conversely, let G contain no odd cycle.

Graph Theory A Senthil Thilak

Bipartite Graphs

Characterization of bipartite graphs

Theorem (Characterization of bipartite graphs)

A graph G is bipartite if and only if it has no odd cycle.
Proof.
Suppose that G is bipartite with bipartition (X , Y ). Let C = v1 v2 . . . vk v1
be a cycle in G .
Claim: C is an even cycle. (i.e, TP: k is even).
WLG, let v1 ∈ X . Then, as v1 and v2 are adjacent, v2 ∈ Y . Similarly,
v3 ∈ X , v4 ∈ Y and so on. Thus, for each 1 ≤ i ≤ k, vi ∈ X if i is odd
and vi ∈ Y , if i is even. Finally, as v1 ∈ X , vk ∈ Y . Thus, k must be
even and hence, C must be an even cycle.
Conversely, let G contain no odd cycle. Then, we need to find a
bipartition of G .

Graph Theory A Senthil Thilak

Bipartite Graphs

Characterization of bipartite graphs

Theorem (Characterization of bipartite graphs)

A graph G is bipartite if and only if it has no odd cycle.
Proof.
Suppose that G is bipartite with bipartition (X , Y ). Let C = v1 v2 . . . vk v1
be a cycle in G .
Claim: C is an even cycle. (i.e, TP: k is even).
WLG, let v1 ∈ X . Then, as v1 and v2 are adjacent, v2 ∈ Y . Similarly,
v3 ∈ X , v4 ∈ Y and so on. Thus, for each 1 ≤ i ≤ k, vi ∈ X if i is odd
and vi ∈ Y , if i is even. Finally, as v1 ∈ X , vk ∈ Y . Thus, k must be
even and hence, C must be an even cycle.
Conversely, let G contain no odd cycle. Then, we need to find a
bipartition of G . Let G be connected.

Graph Theory A Senthil Thilak

Bipartite Graphs

Characterization of bipartite graphs

Theorem (Characterization of bipartite graphs)

A graph G is bipartite if and only if it has no odd cycle.
Proof.
Suppose that G is bipartite with bipartition (X , Y ). Let C = v1 v2 . . . vk v1
be a cycle in G .
Claim: C is an even cycle. (i.e, TP: k is even).
WLG, let v1 ∈ X . Then, as v1 and v2 are adjacent, v2 ∈ Y . Similarly,
v3 ∈ X , v4 ∈ Y and so on. Thus, for each 1 ≤ i ≤ k, vi ∈ X if i is odd
and vi ∈ Y , if i is even. Finally, as v1 ∈ X , vk ∈ Y . Thus, k must be
even and hence, C must be an even cycle.
Conversely, let G contain no odd cycle. Then, we need to find a
bipartition of G . Let G be connected. Let u ∈ V (G ).
Define X = {v ∈ V : d(u, v ) is even} and Y = {v ∈ V : d(u, v ) is odd }

Graph Theory A Senthil Thilak

Bipartite Graphs

Characterization of bipartite graphs

Theorem (Characterization of bipartite graphs)

A graph G is bipartite if and only if it has no odd cycle.
Proof.
Suppose that G is bipartite with bipartition (X , Y ). Let C = v1 v2 . . . vk v1
be a cycle in G .
Claim: C is an even cycle. (i.e, TP: k is even).
WLG, let v1 ∈ X . Then, as v1 and v2 are adjacent, v2 ∈ Y . Similarly,
v3 ∈ X , v4 ∈ Y and so on. Thus, for each 1 ≤ i ≤ k, vi ∈ X if i is odd
and vi ∈ Y , if i is even. Finally, as v1 ∈ X , vk ∈ Y . Thus, k must be
even and hence, C must be an even cycle.
Conversely, let G contain no odd cycle. Then, we need to find a
bipartition of G . Let G be connected. Let u ∈ V (G ).
Define X = {v ∈ V : d(u, v ) is even} and Y = {v ∈ V : d(u, v ) is odd }
Claim: (X , Y ) is a bipartition of G .

Graph Theory A Senthil Thilak

Bipartite Graphs

Characterization of bipartite graphs

Theorem (Characterization of bipartite graphs)

A graph G is bipartite if and only if it has no odd cycle.
Proof.
Suppose that G is bipartite with bipartition (X , Y ). Let C = v1 v2 . . . vk v1
be a cycle in G .
Claim: C is an even cycle. (i.e, TP: k is even).
WLG, let v1 ∈ X . Then, as v1 and v2 are adjacent, v2 ∈ Y . Similarly,
v3 ∈ X , v4 ∈ Y and so on. Thus, for each 1 ≤ i ≤ k, vi ∈ X if i is odd
and vi ∈ Y , if i is even. Finally, as v1 ∈ X , vk ∈ Y . Thus, k must be
even and hence, C must be an even cycle.
Conversely, let G contain no odd cycle. Then, we need to find a
bipartition of G . Let G be connected. Let u ∈ V (G ).
Define X = {v ∈ V : d(u, v ) is even} and Y = {v ∈ V : d(u, v ) is odd }
Claim: (X , Y ) is a bipartition of G . That is, TP : The sets X and Y are
independent.

Graph Theory A Senthil Thilak

Bipartite Graphs

Characterization of bipartite graphs

Theorem (Characterization of bipartite graphs)

A graph G is bipartite if and only if it has no odd cycle.
Proof.
Suppose that G is bipartite with bipartition (X , Y ). Let C = v1 v2 . . . vk v1
be a cycle in G .
Claim: C is an even cycle. (i.e, TP: k is even).
WLG, let v1 ∈ X . Then, as v1 and v2 are adjacent, v2 ∈ Y . Similarly,
v3 ∈ X , v4 ∈ Y and so on. Thus, for each 1 ≤ i ≤ k, vi ∈ X if i is odd
and vi ∈ Y , if i is even. Finally, as v1 ∈ X , vk ∈ Y . Thus, k must be
even and hence, C must be an even cycle.
Conversely, let G contain no odd cycle. Then, we need to find a
bipartition of G . Let G be connected. Let u ∈ V (G ).
Define X = {v ∈ V : d(u, v ) is even} and Y = {v ∈ V : d(u, v ) is odd }
Claim: (X , Y ) is a bipartition of G . That is, TP : The sets X and Y are
independent. Let v , w ∈ X .

Graph Theory A Senthil Thilak

Bipartite Graphs

Characterization of bipartite graphs

Theorem (Characterization of bipartite graphs)

A graph G is bipartite if and only if it has no odd cycle.
Proof.
Suppose that G is bipartite with bipartition (X , Y ). Let C = v1 v2 . . . vk v1
be a cycle in G .
Claim: C is an even cycle. (i.e, TP: k is even).
WLG, let v1 ∈ X . Then, as v1 and v2 are adjacent, v2 ∈ Y . Similarly,
v3 ∈ X , v4 ∈ Y and so on. Thus, for each 1 ≤ i ≤ k, vi ∈ X if i is odd
and vi ∈ Y , if i is even. Finally, as v1 ∈ X , vk ∈ Y . Thus, k must be
even and hence, C must be an even cycle.
Conversely, let G contain no odd cycle. Then, we need to find a
bipartition of G . Let G be connected. Let u ∈ V (G ).
Define X = {v ∈ V : d(u, v ) is even} and Y = {v ∈ V : d(u, v ) is odd }
Claim: (X , Y ) is a bipartition of G . That is, TP : The sets X and Y are
independent. Let v , w ∈ X . Then, p = d(u, v ) and q = d(u, w ) are
even.
Graph Theory A Senthil Thilak
Bipartite Graphs

Characterization of bipartite graphs

Theorem (Characterization of bipartite graphs)

A graph G is bipartite if and only if it has no odd cycle.
Proof.
Suppose that G is bipartite with bipartition (X , Y ). Let C = v1 v2 . . . vk v1
be a cycle in G .
Claim: C is an even cycle. (i.e, TP: k is even).
WLG, let v1 ∈ X . Then, as v1 and v2 are adjacent, v2 ∈ Y . Similarly,
v3 ∈ X , v4 ∈ Y and so on. Thus, for each 1 ≤ i ≤ k, vi ∈ X if i is odd
and vi ∈ Y , if i is even. Finally, as v1 ∈ X , vk ∈ Y . Thus, k must be
even and hence, C must be an even cycle.
Conversely, let G contain no odd cycle. Then, we need to find a
bipartition of G . Let G be connected. Let u ∈ V (G ).
Define X = {v ∈ V : d(u, v ) is even} and Y = {v ∈ V : d(u, v ) is odd }
Claim: (X , Y ) is a bipartition of G . That is, TP : The sets X and Y are
independent. Let v , w ∈ X . Then, p = d(u, v ) and q = d(u, w ) are
even. Further, as d(u, u) = 0, u ∈ X .
Graph Theory A Senthil Thilak
Bipartite Graphs

Characterization of bipartite graphs

Proof contd...
Let P be a shortest (u, w )-path of length p and Q be a shortest (u, v )-path of length q. (Refer figure
below)
16 1 Basic Results

v
P

u w1

Q
w

Fig. 1.19 Graph for proof of Theorem 1.5.10

Let w1 be the last vertex common to P and Q. Then (u, w1 )-section of P and (u, w2 )-section of Q are
of same length. Hence, the lengths of P 0 = (w1 , w )-section of P and Q 0 = (w1 , v )-section of Q are of
0 vertices
same parity (both odd or both even). adjacent
vertices of Y are In eitherin G: Let v; w be
case, Ptwo ∪ Q 0 isof ofX: Then
even p D d.u; v/ Suppose e = (v , w ) is an
length.
and
0 q D d.u; w/ are even. Further, as d.u; u/ D 0; u 2 X: Let P be a u-v shortest
edge in G , then P 0 ∪ e ∪ Qpathwill form
of length p andanQ; odd cycle,path
a u-w shortest contradicting
of length q: (See Fig.our
1.19.)hypothesis.
Let w1 be a Hence, no two vertices
in X are adjacent in G . Similarly,
vertex common nototwoP andvertices
Q such that in
the wY1 -vare adjacent
section of P and the in
w1 -w .
Gsection of
Q contain no vertices common to P and Q: Then the u-w1 sections of both P and
Q have the same length.
Hence, the lengths of the w1 -v section of P and the w1 -w section of Q are both
even or both odd. Now if e D vw is an edge of G; then the w1 -v section of P
followed by the edge vw and the w-w1 section of the w-u path Q!1 is an odd cycle
in G; contradicting the hypothesis. This contradiction proves that no two vertices of
X are adjacent in G. Similarly, no two vertices of Y are adjacent in G: This proves
the result when G is connected.
If G is not connected, let G1 ; G2; : : : ; G! be the components of G: By hypothesis,
no component of G contains an odd cycle. Hence, by the previous paragraph, each
component Gi ; 1 ! iS! !; is bipartite. S Let .Xi ; Yi / be the bipartition of Gi : Then
.X; Y /; where X D !iD1 Xi and Y D !iD1 Yi ; is a bipartition of G; and G is a
bipartite graph. !
Exercise 5.8. Prove that a simple nontrivial graph G is connected if and only if for
any partition of V into two nonempty subsets V1 and V2; there is an edge joining a
vertex of V1 to a vertex of V2:
Graph Theory Example 1.5.11. Prove that in a connected graph G with at least three vertices, any A Senthil Thilak
Bipartite Graphs

Characterization of bipartite graphs

Proof contd...
Let P be a shortest (u, w )-path of length p and Q be a shortest (u, v )-path of length q. (Refer figure
below)
16 1 Basic Results

v
P

u w1

Q
w

Fig. 1.19 Graph for proof of Theorem 1.5.10

Let w1 be the last vertex common to P and Q. Then (u, w1 )-section of P and (u, w2 )-section of Q are
of same length. Hence, the lengths of P 0 = (w1 , w )-section of P and Q 0 = (w1 , v )-section of Q are of
0 vertices
same parity (both odd or both even). adjacent
vertices of Y are In eitherin G: Let v; w be
case, Ptwo ∪ Q 0 isof ofX: Then
even p D d.u; v/ Suppose e = (v , w ) is an
length.
and
0 q D d.u; w/ are even. Further, as d.u; u/ D 0; u 2 X: Let P be a u-v shortest
edge in G , then P 0 ∪ e ∪ Qpathwill form
of length p andanQ; odd cycle,path
a u-w shortest contradicting
of length q: (See Fig.our
1.19.)hypothesis.
Let w1 be a Hence, no two vertices
in X are adjacent in G . Similarly,
vertex common nototwoP andvertices
Q such that in
the wY1 -vare adjacent
section of P and the in
w1 -w .
Gsection of
If G is disconnected, let G1Q, contain
G2 . .no. vertices
Gt becommon to P and Q: Then the
the components G1. sections of both P and
ofu-w
Q have the same length.
Hence, the lengths of the w1 -v section of P and the w1 -w section of Q are both
even or both odd. Now if e D vw is an edge of G; then the w1 -v section of P
followed by the edge vw and the w-w1 section of the w-u path Q!1 is an odd cycle
in G; contradicting the hypothesis. This contradiction proves that no two vertices of
X are adjacent in G. Similarly, no two vertices of Y are adjacent in G: This proves
the result when G is connected.
If G is not connected, let G1 ; G2; : : : ; G! be the components of G: By hypothesis,
no component of G contains an odd cycle. Hence, by the previous paragraph, each
component Gi ; 1 ! iS! !; is bipartite. S Let .Xi ; Yi / be the bipartition of Gi : Then
.X; Y /; where X D !iD1 Xi and Y D !iD1 Yi ; is a bipartition of G; and G is a
bipartite graph. !
Exercise 5.8. Prove that a simple nontrivial graph G is connected if and only if for
any partition of V into two nonempty subsets V1 and V2; there is an edge joining a
vertex of V1 to a vertex of V2:
Graph Theory Example 1.5.11. Prove that in a connected graph G with at least three vertices, any A Senthil Thilak
Bipartite Graphs

Characterization of bipartite graphs

Proof contd...
Let P be a shortest (u, w )-path of length p and Q be a shortest (u, v )-path of length q. (Refer figure
below)
16 1 Basic Results

v
P

u w1

Q
w

Fig. 1.19 Graph for proof of Theorem 1.5.10

Let w1 be the last vertex common to P and Q. Then (u, w1 )-section of P and (u, w2 )-section of Q are
of same length. Hence, the lengths of P 0 = (w1 , w )-section of P and Q 0 = (w1 , v )-section of Q are of
0 vertices
same parity (both odd or both even). adjacent
vertices of Y are In eitherin G: Let v; w be
case, Ptwo ∪ Q 0 isof ofX: Then
even p D d.u; v/ Suppose e = (v , w ) is an
length.
and
0 q D d.u; w/ are even. Further, as d.u; u/ D 0; u 2 X: Let P be a u-v shortest
edge in G , then P 0 ∪ e ∪ Qpathwill form
of length p andanQ; odd cycle,path
a u-w shortest contradicting
of length q: (See Fig.our
1.19.)hypothesis.
Let w1 be a Hence, no two vertices
in X are adjacent in G . Similarly,
vertex common nototwo
P andvertices
Q such that in
the wY1 -vare adjacent
section of P and the in
w1 -w .
Gsection of
If G is disconnected, let G1Q, contain
G2 . .no. vertices
Gt becommon to P and Q: Then the
the components G1. sections
ofu-w of both P and each G (1 ≤ i ≤ t)
By hypothesis, i
contains no odd cycle and Qbyhave thethe same length.
above discussion, each Gi (1
Hence, the lengths of the w -v section of P and the
≤ i ≤ t) is bipartite.
w -w section of Q are both
1 1
even or both odd. Now if e D vw is an edge of G; then the w1 -v section of P
followed by the edge vw and the w-w1 section of the w-u path Q!1 is an odd cycle
in G; contradicting the hypothesis. This contradiction proves that no two vertices of
X are adjacent in G. Similarly, no two vertices of Y are adjacent in G: This proves
the result when G is connected.
If G is not connected, let G1 ; G2; : : : ; G! be the components of G: By hypothesis,
no component of G contains an odd cycle. Hence, by the previous paragraph, each
component Gi ; 1 ! iS! !; is bipartite. S Let .Xi ; Yi / be the bipartition of Gi : Then
.X; Y /; where X D !iD1 Xi and Y D !iD1 Yi ; is a bipartition of G; and G is a
bipartite graph. !
Exercise 5.8. Prove that a simple nontrivial graph G is connected if and only if for
any partition of V into two nonempty subsets V1 and V2; there is an edge joining a
vertex of V1 to a vertex of V2:
Graph Theory Example 1.5.11. Prove that in a connected graph G with at least three vertices, any A Senthil Thilak
Bipartite Graphs

Characterization of bipartite graphs

Proof contd...
Let P be a shortest (u, w )-path of length p and Q be a shortest (u, v )-path of length q. (Refer figure
below)
16 1 Basic Results

v
P

u w1

Q
w

Fig. 1.19 Graph for proof of Theorem 1.5.10

Let w1 be the last vertex common to P and Q. Then (u, w1 )-section of P and (u, w2 )-section of Q are
of same length. Hence, the lengths of P 0 = (w1 , w )-section of P and Q 0 = (w1 , v )-section of Q are of
0 vertices
same parity (both odd or both even). adjacent
vertices of Y are In either in G: Let v; w be
case, Ptwo ∪ Q 0 isof of X: Then
even p D d.u; v/ Suppose e = (v , w ) is an
length.
and
0 q D d.u; w/ are even. Further, as d.u; u/ D 0; u 2 X: Let P be a u-v shortest
edge in G , then P 0 ∪ e ∪ Qpath will form
of length p andanQ; odd cycle,path
a u-w shortest contradicting
of length q: (See Fig.our
1.19.)hypothesis.
Let w1 be a Hence, no two vertices
in X are adjacent in G . Similarly,
vertex common nototwo
P andvertices
Q such that in
the wY1 -vare adjacent
section of P and the in
w1 -w .
Gsection of
If G is disconnected, let G1Q, contain
G2 . .no. vertices
Gt becommon to P and Q: Then the
the components G1. sections
ofu-w of both P and each G (1 ≤ i ≤ t)
By hypothesis, i
contains no odd cycle and Qbyhave thethe same length.
above discussion, each Gi (1
Hence, the lengths of the w1 -v section of P and the
≤ i ≤ t) is bipartite. Let (Xi , Yi ) be the
w1 -w section of Q are both
1≤
bipartition of Gi for each i,even i ≤odd.
or both Then,
t. Now if e D vw is an edge of G; then the w1 -v section of P
followed by the edge vw and the w-w1 section of the w-u path Q!1 is an odd cycle
in G; contradicting the hypothesis. This contradiction proves that no two vertices of
X are adjacent in G. Similarly, no two vertices of Y are adjacent in G: This proves
the result when G is connected.
If G is not connected, let G1 ; G2; : : : ; G! be the components of G: By hypothesis,
no component of G contains an odd cycle. Hence, by the previous paragraph, each
component Gi ; 1 ! iS! !; is bipartite. S Let .Xi ; Yi / be the bipartition of Gi : Then
.X; Y /; where X D !iD1 Xi and Y D !iD1 Yi ; is a bipartition of G; and G is a
bipartite graph. !
Exercise 5.8. Prove that a simple nontrivial graph G is connected if and only if for
any partition of V into two nonempty subsets V1 and V2; there is an edge joining a
vertex of V1 to a vertex of V2:
Graph Theory Example 1.5.11. Prove that in a connected graph G with at least three vertices, any A Senthil Thilak
Bipartite Graphs

Characterization of bipartite graphs

Proof contd...
Let P be a shortest (u, w )-path of length p and Q be a shortest (u, v )-path of length q. (Refer figure
below)
16 1 Basic Results

v
P

u w1

Q
w

Fig. 1.19 Graph for proof of Theorem 1.5.10

Let w1 be the last vertex common to P and Q. Then (u, w1 )-section of P and (u, w2 )-section of Q are
of same length. Hence, the lengths of P 0 = (w1 , w )-section of P and Q 0 = (w1 , v )-section of Q are of
0 vertices
same parity (both odd or both even). adjacent
vertices of Y are In eitherin G: Let v; w be
case, Ptwo ∪ Q 0 isof of X: Then
even p D d.u; v/ Suppose e = (v , w ) is an
length.
and
0 q D d.u; w/ are even. Further, as d.u; u/ D 0; u 2 X: Let P be a u-v shortest
edge in G , then P 0 ∪ e ∪ Qpath will form
of length an
p and Q; odd cycle,path
a u-w shortest contradicting
of length q: (See Fig.our
1.19.)hypothesis.
Let w1 be a Hence, no two vertices
in X are adjacent in G . Similarly,
vertex common nototwo
P andvertices
Q such that in
the wY1 -vare adjacent
section of P and the inw1 -w .
Gsection of
If G is disconnected, let G1Q, contain
G2 . .no. vertices
Gt becommon to P and Q: Then the
the components G1. sections
ofu-w of both P and each G (1 ≤ i ≤ t)
By hypothesis, i
contains no odd cycle and Qbyhave thethe same length.
above discussion, each Gi (1
Hence, the lengths of the w1 -v section of P and the
≤ i ≤ t) is bipartite. Let (Xi , Yi ) be the
w1 -w section of Q are both
t t
1≤
bipartition of Gi for each i,even i ≤odd.
or both Then,
t. Now if e Dwith =∪
X edge
vw is an ofi=1 Xi and
G; then = ∪of
Ysection
the w1 -v i=1P Yi , (X , Y ) forms a
bipartition of G and hence,followed
G is by the edge vw and the w-w1 section of the w-u path Q!1 is an odd cycle
bipartite.
in G; contradicting the hypothesis. This contradiction proves that no two vertices of
X are adjacent in G. Similarly, no two vertices of Y are adjacent in G: This proves
the result when G is connected.
Exercise If G is not connected, let G1 ; G2; : : : ; G! be the components of G: By hypothesis,
no component of G contains an odd cycle. Hence, by the previous paragraph, each
component Gi ; 1 ! iS! !; is bipartite. S
Prove that a simple non-trivial graph G is connectedLetif.Xand i ; Yi / be the bipartition of Gi : Then
only if for any partition of V
.X; Y /; where X D !iD1 Xi and Y D !iD1 Yi ; is a bipartition of G; and G is a
into two
non-empty subsets V1 andbipartite
V2 , there
graph. is an edge joining a vertex of V1 to a vertex ! of V2 .
Exercise 5.8. Prove that a simple nontrivial graph G is connected if and only if for
any partition of V into two nonempty subsets V1 and V2; there is an edge joining a
vertex of V1 to a vertex of V2:
Graph Theory Example 1.5.11. Prove that in a connected graph G with at least three vertices, any A Senthil Thilak
Bipartite Graphs

Characterization of bipartite graphs

Remark (Testing whether a graph is bipartite)

• The above theorem implies that in order to prove that a graph

G is not bipartite, it is enough to show the presence of an odd
cycle in G . This is much easier than examining all possible
bipartitions to prove that none work.

Graph Theory A Senthil Thilak

Bipartite Graphs

Characterization of bipartite graphs

Remark (Testing whether a graph is bipartite)

• The above theorem implies that in order to prove that a graph

G is not bipartite, it is enough to show the presence of an odd
cycle in G . This is much easier than examining all possible
bipartitions to prove that none work.
• On the other hand, to prove that G is bipartite, we
define/identify a bipartition of V (G ) and prove that the two
partite sets are independent; this is much easier than
examining all cycles, whether they are even or not.

Graph Theory A Senthil Thilak

Bipartite Graphs

Characterization of bipartite graphs

Remark (Testing whether a graph is bipartite)

• The above theorem implies that in order to prove that a graph

G is not bipartite, it is enough to show the presence of an odd
cycle in G . This is much easier than examining all possible
bipartitions to prove that none work.
• On the other hand, to prove that G is bipartite, we
define/identify a bipartition of V (G ) and prove that the two
partite sets are independent; this is much easier than
examining all cycles, whether they are even or not.
• Bipartite graphs find applications in many scheduling problems
like job scheduling, frequency scheduling, traffic scheduling
etc...

Graph Theory A Senthil Thilak

Bipartite Graphs

Complete bipartite graphs

Outline

1 Bipartite Graphs
Preliminaries
Bipartite graphs - Definition and examples
Characterization of bipartite graphs
Complete bipartite graphs

Graph Theory A Senthil Thilak

Bipartite Graphs

Complete bipartite graphs

Complete bipartite graphs

• We know that if G is bipartite, then V (G ) can be partitioned into
two subsets X and Y called partite sets, such that each edge of G
has one end in X and one end in Y .
• However, this does not mean that every vertex of X is adjacent to
every vertex of Y . If this does happen, however, then we call G a
Complete bipartite graph.
• A complete bipartite graph with partition (X , Y ) such that |X | = s
and |Y | = t is denoted by Ks,t or Kt,s .
• The graph K1,t (or Ks,1 ) is referred to as a Star graph.

Figure: Examples of Complete bipartite graphs

Graph Theory A Senthil Thilak

Bipartite Graphs

Complete bipartite graphs

Complete multipartite graphs

Bipartite graphs belong to a more general class of graphs.

Graph Theory A Senthil Thilak

Bipartite Graphs

Complete bipartite graphs

Complete multipartite graphs

Bipartite graphs belong to a more general class of graphs.
Definition (k-partite or Multi-partite graph)
A graph G is k-partite (or Multi-partite) if V (G ) can be partitioned
into k subsets say, V1 , V2 . . . Vk (called partite sets) such that each Vi
is independent. Equivalently, if (u, v ) is an edge of G , then u and v
belong to different partite sets.

Graph Theory A Senthil Thilak

Bipartite Graphs

Complete bipartite graphs

Complete multipartite graphs

Bipartite graphs belong to a more general class of graphs.
Definition (k-partite or Multi-partite graph)
A graph G is k-partite (or Multi-partite) if V (G ) can be partitioned
into k subsets say, V1 , V2 . . . Vk (called partite sets) such that each Vi
is independent. Equivalently, if (u, v ) is an edge of G , then u and v
belong to different partite sets.
If, in addition, every two vertices in different partite sets are joined by
and edge, then G is a Complete k-partite graph. If |Vi | = ni , for
1 ≤ i ≤ k, then we denote this complete k-partite graph by Kn1 , n2 ...nk .

Graph Theory A Senthil Thilak

Bipartite Graphs

Complete bipartite graphs

Complete multipartite graphs

Bipartite graphs belong to a more general class of graphs.
Definition (k-partite or Multi-partite graph)
A graph G is k-partite (or Multi-partite) if V (G ) can be partitioned
into k subsets say, V1 , V2 . . . Vk (called partite sets) such that each Vi
is independent. Equivalently, if (u, v ) is an edge of G , then u and v
belong to different partite sets.
If, in addition, every two vertices in different partite sets are joined by
and edge, then G is a Complete k-partite graph. If |Vi | = ni , for
1 ≤ i ≤ k, then we denote this complete k-partite graph by Kn1 , n2 ...nk .

Figure: Examples of Complete multipartite graphs

Graph Theory A Senthil Thilak

Bipartite Graphs

Complete bipartite graphs

Thank You!!!

Graph Theory A Senthil Thilak