in Graph Theory edited by
1,897 views
0 votes
0 votes

Which of the following graphs are bipartite?

  1. Only $(1)$
  2. Only $(2)$
  3. Only $(2)$ and $(3)$
  4. None of $(1),(2),(3)$
  5. All of $(1),(2),(3)$
in Graph Theory edited by
1.9k views

3 Answers

1 vote
1 vote

A graph $G=(V(G), E(G))$ is said to be Bipartite if and only if there exists a partition $V(G)=A\cup B$ and $A\cap B =\emptyset.$ Hence all edges share a vertex from both set $A$ and $B,$ and there are no edges formed between two vertices in the set $A,$ and there are not edges formed between the two vertices in $B.$

$$\textbf{(OR)}$$

A bipartite graph, also called a bigraph, is a set of graph vertices decomposed into two disjoint sets such that no two graph vertices within the same set are adjacent. 

  • $G$ is bipartite if and only if all cycles in $G$ are of even length.
  • Every tree is bipartite.
  • A graph is bipartite if and only if it is $2$-colorable $,\text{(i.e. its chromatic number is less than or equal to}\: 2).$

The first graph is known as the Peterson graph.

It is not a bipartite graph.

The Petersen graph has chromatic number $3,$ meaning that its vertices can be colored with three colors — but not with two — such that no edge connects vertices of the same color. It has a list colouring with $3$ colours, by Brooks' theorem for list colourings.

The Petersen graph has chromatic index $4;$ coloring the edges requires four colors. As a connected bridgeless cubic graph with chromatic index four, the Petersen graph is a snark.

Reference:

The second graph is a bipartite graph because it is $2$-colorable.

The third graph is the wheel graph.

In a wheel graph, the hub has degree $n-1$, and other nodes have degree $3.$ Wheel graphs are $3$-connected. $W_{4} = K_{4}$, where $K_{4}$ is the complete graph of order four. The chromatic number of $W_{n}$ is

$\chi(W_{n}) = \left\{\begin{matrix} 3 & \text{for n odd} \\ 4 & \text{for n even} \end{matrix}\right.$

It is not a bipartite graph.

Reference:

So, the correct answer is $(B).$

edited by
1 vote
1 vote
  • A graph is said to be a bipartite graph, when vertices of that graph can be divided into two independent sets such that every edge in the graph is either start from the first set and ended in the second set connected to the first set, in other words, we can say that no edge can found in the same set.
  • Bipartite graphs are precisely the class of graphs that are $2$-colorable. Checking of a bipartite graph is possible by using the vertex coloring. When a vertex is in the same set, it has the same color, for another set, the color will change.

For the given option we can see only option $2)$ is $2$-colorable graph.

Moreover, a bipartite graph has no odd length cycle which is not present in option $2)$

Hence Option $2)$ is correct answer

0 votes
0 votes
A graph is bipartite if and only if the  vertices of graph can be coloured with at most 2 colour. We can see that graph 1 and 3 can not be coloured with 2 colour, but graph 2 can be coloured with 2 colour. So only graph 2 is bipartite.
Answer:

Related questions