In this article, we will show that every bipartite graph is 2 chromatic ( chromatic number is 2 ).
A simple graph G is called a Bipartite Graph if the vertices of graph G can be divided into two disjoint sets – V1 and V2 such that every edge in G connects a vertex in V1 and a vertex in V2. In simple words, no edge connects two vertices belonging to the same set.
Every Bipartite Graph has a Chromatic number 2. It means that it is possible to assign one of the different two colors to each vertex in G such that no two adjacent vertices have the same color. Conversely, every 2-chromatic graph is bipartite.
Proof
Suppose a bipartite graph G(V, E). Let V1 and V2 be the disjoint sets such that every edge in G connects a vertex in V1 and a vertex in V2. Assign the first color to every vertex in V1 and the second color to every vertex in V2. Since G is bipartite, no edge in G connects two vertices belonging to the same set. That means no two adjacent vertices can have the same color. Hence, G is 2-Chromatic.
Suppose a 2-Chromatic graph G(V, E). Divide the vertices of G into two sets such that the vertices with the first color are in V1 and vertices with the second color are in V2. As the graph is 2-Chromatic, no two adjacent vertices can have the same color. Thus, we can say that no edge connects vertices belonging to the same set. An edge can only connect a vertex in V1 and a vertex in V2. Consequently, G is a Bipartite Graph.
Hence, every Bipartite Graph is 2-Chromatic and every 2-Chromatic Graph is Bipartite.
References