The chromatic index of a bipartite graph with at least one edge is:

কম্পিউটার সায়েন্স

বিবিধ

বিসিএস

উত্তরের বিবরণ

Answer: ক) 1
Chromatic Index: The minimum number of colors needed to color the edges of a graph so that no two edges incident on the same vertex have the same color.
Bipartite Graph: A graph whose vertices can be divided into two disjoint sets U and V, with edges only between U and V, no edges within the same set.
Vizing's Theorem:
For any simple graph, the chromatic index χ′(G) is either:
Δ(G) or Δ(G)+1
Δ(G) = maximum degree of the graph.

Special case for bipartite graphs:
If the graph is bipartite, the chromatic index is exactly equal to its maximum degree (Δ(G)
Since a bipartite graph has at least one edge, its maximum degree Δ(G)≥1
Step 1: Minimum chromatic index
For a bipartite graph with at least one edge, the smallest possible maximum degree is 1 (e.g., a single edge).
So the chromatic index = maximum degree = 1 if it’s just one edge.

Step 2: General case
For general bipartite graphs, chromatic index = maximum degree.
For example:

A star graph K1,n → max degree = n → chromatic index = n.
But the question asks for simple bipartite graph with ≥1 edge and not a specific graph, so the minimum guaranteed chromatic index = 1.

Chromatic index of a bipartite graph = maximum degree Δ
Minimum guaranteed chromatic index (for any bipartite graph with at least one edge) = 1