The given question is:
Consider the following graph:
Specify whether the above graph is bipartite or not. If yes, give the partition, else justify.
A bipartite graph is a graph in which the vertices can be divided into two disjoint sets, such that no two vertices within the same set are adjacent. In other words, it is a graph in which every edge connects a vertex of one set to a vertex of the other set.
If all the vertices of the graph can be colored only using two colors, such that no two adjacent vertex have the same colour, the graph is said to be bipartite.
Let's use the colors - RED and BLUE.
As we can see, the graph can be colored using only two colors and no two adjacent vertex have the same color. Hence, we can say that the given graph is bipartite.
The graph can be partitioned on basis of colour - all red vertices together and all blue vertices together. The partition is given as follows:
SET A: 1,6,7,4
SET B: 2,5,3,8
Comments