Day 07Part 04 – Discrete Mathematics for Gate 2025 Bipartite graph and it’s Concept.

Day 07Part 04 – Discrete Mathematics for Gate 2025 Bipartite graph and it’s Concept.

Here’s a clear and concise explanation of the Bipartite Graph concept from Discrete Mathematics, tailored for GATE 2025 preparation (Day 07, Part 04):

Day 07 Part 04 – Discrete Mathematics for GATE 2025

Topic: Bipartite Graph and Its Concept

What is a Bipartite Graph?

A bipartite graph is a type of graph where:

• Vertices can be divided into two disjoint sets:
  $U$ and $V$

• Every edge connects a vertex from set $U$ to a vertex in set $V$
  (i.e., no edge exists between vertices within the same set)

Formal Definition:

A graph $G=(V,E)$ is bipartite if:
There exists a partition V=V1∪V2V = V_1 \cup V_2V=V1​∪V2​ such that for every edge $(u,v)\in E$,
either u∈V1u \in V_1u∈V1​ and v∈V2v \in V_2v∈V2​, or vice versa.

Key Properties:

• A graph is bipartite if and only if it does not contain any odd-length cycles.

• Bipartite graphs are 2-colorable, meaning you can color vertices with two colors such that no two adjacent vertices share the same color.

How to Check if a Graph is Bipartite (GATE Tip):

Use Breadth-First Search (BFS) or Depth-First Search (DFS):

• Try to color the graph using two colors.

• If at any point, two adjacent vertices have the same color → not bipartite.

Example:

Let’s take a graph with vertices:
$V=\{A,B,C,D\}$ and edges:
$E=\{(A,B),(A,D),(C,B),(C,D)\}$

Partition:
V1={A,C}V_1 = \{A, C\}V1​={A,C}, V2={B,D}V_2 = \{B, D\}V2​={B,D}

All edges go from V1→V2V_1 \to V_2V1​→V2​ → Bipartite

Applications in GATE:

• Matching Problems (e.g., job assignment)

• Scheduling

• Network flow algorithms

• DFS/BFS traversal-based MCQs

Practice Question (GATE Style):

Which of the following graphs is bipartite?
A) A triangle (3-cycle)
B) A square (4-cycle)
C) A star graph
D) A complete graph K3K_3K3​

Answer: B and C (A triangle has an odd cycle, so it’s not bipartite)

Would you like:

• A PDF study note

• A practice sheet

• This content in Hindi for easier understanding?

Let me know how I can help further!

Day 07Part 04 – Discrete Mathematics for Gate 2025 Bipartite graph and it’s Concept.

Lecture 4: Bipartite graphs, and some other common graphs