(a) Define a Bipartite Graph and Complete Bipartite Graph. (b) For a complete…
(a) Define a Bipartite Graph and Complete Bipartite Graph.
(b) For a complete bipartite graph Km,n, derive the formula for the number of edges.
(c) Find the number of edges in K3,4 and verify whether a graph with 7 vertices and 12 edges can be a complete bipartite graph.
Attempted by 21 students.
Show answer & explanation
Bipartite and Complete Bipartite Graphs
(a) Definitions:
A Bipartite Graph G=(V,E) is a graph whose vertex set V can be partitioned into two disjoint sets V1 and V2 such that every edge connects a vertex from V1 to V2. No edge exists within the same set, making both sets independent.
A Complete Bipartite Graph Km,n is a bipartite graph in which every vertex of V1 (size m) is connected to every vertex of V2 (size n).
(b) Edge Formula Derivation:
Let ∣V1∣=m and ∣V2∣=n. Each of the mmm vertices in V1 is adjacent to all n vertices of V2.
∣E∣=m×n
(c) Numerical Verification:
Given V=7, E=12. Possible partitions: (1,6),(2,5),(3,4).
1 × 6 = 6, 2 × 5 = 10, 3 × 4 = 12
Hence, the graph can be represented as K3,4.
Key Property & Conclusion:
A graph is bipartite iff it contains no odd cycle. Thus, bipartite graphs model relationships between two distinct sets, while Km,n represents maximum connectivity between them, making it highly useful in network modeling and matching problems.