Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have 2 questions regarding Bipartiteness with corresponding examples.

1) Can a non-connected graph be bipartite if it has an isolated vertex? Let's take the following graph: enter image description here
I would say YES with this partition: V1 = {A, D, G} ; V2 = {B, C, E, F, H}
But what confuses me is that A is isolated.
Is that a contradiction to the bipartitiness of G ?

2) Is there a rule about the uniqueness of the partitions ? Let's take the following graph: enter image description here
choice1: V1= {A, C}; V2 = {B, D}
choice2: V1= {A, D}; V2 = {B, C}

Does it matter which one i choose?

share|cite|improve this question
The answer of the first question. Yes, it does not have to be connected. For the second, it depends on what you want. What you have done is a correct bipartite graph though. What do you want exactly ? – AJed Jan 8 '13 at 2:32
@1.question: is every graph with n vertices and with no edges a biartite graph? – Hasan Tahsin Jan 8 '13 at 3:32
@2.question: i meant, if it matters which one i choose, when detecting the graph bipartitiness? – Hasan Tahsin Jan 8 '13 at 3:35
An equivalent characterization of bipartite graphs states that a graph is bipartite if and only if it contains no cycles of odd length. – Jernej Jan 8 '13 at 8:56
up vote 3 down vote accepted

enter image description here

A graph with two sides L and R such that all edges go between L and R is a bipartite graph.

Hence, your first part is correct and so is your second part. It doesn't matter as long as both are independent sets.

share|cite|improve this answer
@1.question: is a graph with only 1 vertix and with no edges a bipartite graph? V1 = {v} and V2 = {} – Hasan Tahsin Jan 8 '13 at 3:34
@moller1111: Yes, every (finite) graph which is 2-colorable is considered bipartite. You can have lots of isolated vertices, a star whatever you can think of. It is bipartite if and only if it is 2-colorable if and only if it does not contain any odd cycles. – Pål GD Jan 8 '13 at 9:14

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.