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

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

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:

1. Divide the vertices into two sets:

   • Set 1: {A, B}

   • Set 2: {C, D}

2. 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).

3. 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?

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

COMBINATORIAL ANALYSIS Lecture 29: Bipartite Graphs …

Complete Bipartite Graphs and Their Line Graphs

Bipartite Graphs and Problem Solving

Lecture 3 Bipartite Graphs

Here’s a clear and simplified explanation for Day 07 Part 06 of Discrete Mathematics for Computer Engineering:
Examples based on Bipartite Graph and Complete Bipartite Graph — ideal for GATE, B.Tech, or competitive exam prep.

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={u1,u2}U = \{u_1, u_2\}U={u1​,u2​}

• V={v1,v2}V = \{v_1, v_2\}V={v1​,v2​}

• Edges: {(u1,v1),(u2,v2)}\{(u_1,v_1), (u_2,v_2)\}{(u1​,v1​),(u2​,v2​)}

Here, no edge connects u1u_1u1​ to u2u_2u2​ or v1v_1v1​ to v2v_2v2​.
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 Km,nK_{m,n}Km,n​

• Where $m=|U|$ and $n=|V|$

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

Let:

• U={u1,u2}U = \{u_1, u_2\}U={u1​,u2​}

• V={v1,v2,v3}V = \{v_1, v_2, v_3\}V={v1​,v2​,v3​}

Then edges = all possible pairs between U and V:

• u1→v1,v2,v3u_1 \to v_1, v_2, v_3u1​→v1​,v2​,v3​

• u2→v1,v2,v3u_2 \to v_1, v_2, v_3u2​→v1​,v2​,v3​

Total edges = $2\times 3=6$

This is a complete bipartite graph K2,3K_{2,3}K2,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:

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.

Graph Theory