Question

(i) Define the term bipartite graph. How can a bipartite graph be characterized in terms of its cycles

(ii) What does the Matching Theorem say about certain bipartite graphs?

(iii) Sketch a proof of the Matching Theorem.

Answer 1

(i) k-partite graph with k(chromatic number)=2 constitutes a special case known as the bipartite graph. These graphs are equal to two colorable graphs. In a bipartite graph, the vertices can be divided into two independent sets and no two vertices of graphs in the same set are neighbors or adjacent to each other. These graphs are widely used in modeling relationships as well as in modern coding theory.

As discussed above, a bipartite graph has two sets of vertices because of which there exists a possibility of connection between any vertex in the first set to any vertex in the second set. If the number of vertices in the graph is odd (does not contain any odd cycle) then its spectrum is symmetrical. In case of a cyclic graph, it is bipartite when all its cycles are of even length where as all acyclic graphs are bipartite.

(ii) It is a chosen set of edges such that two edges do not share common end point. Matching is basically a subset of edges where vertex belongs to only one of the edges.

(iii)

Maximum matching is equal to 5 edges