graph theory

Question

A graph with n vertices and 0 edges.can this graph be called as Bipartite ? i mean can we simply partition the n vertices into two sets of vertices such that there is no edge within the set as well there is no edge between the two sets and say it as a Bipartite graph ?

Answer 1

The answer is YES. A bipartite graph with no edges is known as the trivial bipartite graph. 

P.S. I asked this same question, into my classroom into IIT. I asked him that, is it possible that vertex set and edge set can be empty?

First, he laughs, then he said, We can not make vertex set empty otherwise, there will not be any graph, and yes we can make edge set empty and that will be called trivial bipartite graph. 

Comments

@rude      thanks ...then why are they saying every Bi-partite graph is 2-colorable ....the above Bi-partite graph i said is 1-colorable right ???

please see this  https://gateoverflow.in/121282/graph-theory

---

@Vignesh. A graph is 2 colorable. it does not mean that it need two colors. 2-colorable means that at most it need two colors. 

Check the second point carefully in  https://gateoverflow.in/121282/graph-theory this question. 

---

empty vertex set means a null graph

Answer 2

No, see the meaning of bipartite graph .Here the division of vertices is possible but there is no way to reach from one vertex to another. Not only the set should be disjoint but there should be a way to connect one disjoint set to another.More ever the resultant graph should be two colorable.

Comments

Trivial Bipartite graphs are two colorable (that means having 2 or less than two colors). Having edges is not mandatory for it to be a Bipartite. Chromatic number in this case would be 1 (Vertex coloring).