Day 07Part 06- Examples based on Bipartite graph and Complete bipartite graph.

Ali Seron Jason

1 week ago

https://www.gyanodhan.com/video/7B4.%20GATE%20CSEIT/Discrete%20Mathematics%201/375.%20Day%2007Part%2006-%20Examples%20based%20on%20Bipartite%20graph%20and%20Complete%20bipartite%20graph.mp4

A Bipartite Graph is a graph whose vertices can be divided into two disjoint sets such that no two vertices within the same set are adjacent. A Complete Bipartite Graph is a special type of bipartite graph where every vertex from one set is connected to every vertex in the other set.

Example 1: Checking If a Graph is Bipartite

Graph:

Consider a graph with vertices V = {A, B, C, D} and edges E = {(A, C), (A, D), (B, C), (B, D)}.

Solution:

Divide the vertices into two sets:
- Set 1: {A, B}
- Set 2: {C, D}
Each edge connects a vertex in Set 1 to a vertex in Set 2 (i.e., no two vertices in the same set are adjacent).
Since this condition is satisfied, the graph is bipartite.

Example 2: Complete Bipartite Graph (K₃,₄)

A Complete Bipartite Graph Kₘ,ₙ has two sets of vertices with m and n vertices, where every vertex in one set is connected to all vertices in the other set.

Graph:

Consider K₃,₄, with two sets:

Set X: {A, B, C} (3 vertices)
Set Y: {D, E, F, G} (4 vertices)

Edges:

Each vertex from Set X connects to all vertices in Set Y:

A → {D, E, F, G}
B → {D, E, F, G}
C → {D, E, F, G}

Since every vertex from one set is connected to all vertices of the other set, this is a Complete Bipartite Graph.

Key Points:

A graph is bipartite if it can be colored using two colors without any adjacent nodes sharing the same color.
A complete bipartite graph Kₘ,ₙ connects every vertex in one set to every vertex in the other set.

Would you like more practice problems or algorithmic methods to check if a graph is bipartite?

What is a Bipartite Graph?

A Bipartite Graph is a graph where:

The set of vertices can be divided into two disjoint sets, say U and V,
Every edge connects a vertex from U to a vertex from V,
There are no edges within the same set.

Definition:

A graph G(V, E) is bipartite if you can color all vertices using 2 colors such that no two adjacent vertices share the same color.

Example 1: Simple Bipartite Graph

Let

$U = \{u_1, u_2\}$
$V = \{v_1, v_2\}$
Edges: ${(u_1,v_1), (u_2,v_2)\}$

Here, no edge connects $u_1$ to $u_2$ or $v_1$ to $v_2$ .
So this is a bipartite graph.

Trick to Check if a Graph is Bipartite

If a graph has NO odd-length cycle, it is bipartite.

Even-length cycles (like 4, 6) are allowed.

What is a Complete Bipartite Graph?

A complete bipartite graph is a bipartite graph where:

Every vertex in U is connected to every vertex in V.

Denoted as $K_{m,n}$

Where $m = ∣ U ∣$ and $n = ∣ V ∣$

Example 2: $K_{2,3}$ – Complete Bipartite Graph

Let:

$U = \{u_1, u_2\}$
$V = \{v_1, v_2, v_3\}$

Then edges = all possible pairs between U and V:

$u1→v1,v2,v3u_1 \to v_1, v_2, v_3$
$u2→v1,v2,v3u_2 \to v_1, v_2, v_3$

Total edges = $2 \times 3 = 6$

This is a complete bipartite graph $K_{2,3}$

GATE-Level Example Question

Q: Is the following graph bipartite?

This forms a 4-cycle (even-length cycle)
Yes, it’s bipartite

Summary Table:

Type	Definition	Example	Edge Count
Bipartite Graph	Vertices split into two sets, no same-set edge	U = {1,2}, V = {a,b}, Edges = (1,a), (2,b)	Depends
Complete Bipartite	Every U connects to every V	$K_{2,3}$	$m \times n$

Let me know if you want:

Practice problems with solutions
Graph diagrams (as image)
MCQs with answer keys
Python program to check bipartiteness

I can provide visuals or PDFs too!

Day 07Part 06- Examples based on Bipartite graph and Complete bipartite graph.

Example 1: Checking If a Graph is Bipartite

Graph:

Solution:

Example 2: Complete Bipartite Graph (K₃,₄)

Graph:

Edges:

Key Points: