Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 0 down vote favorite

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|improve this question
1  
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 at 2:32
@1.question: is every graph with n vertices and with no edges a biartite graph? – moller1111 Jan 8 at 3:32
@2.question: i meant, if it matters which one i choose, when detecting the graph bipartitiness? – moller1111 Jan 8 at 3:35
1  
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 at 8:56

1 Answer

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|improve this answer
@1.question: is a graph with only 1 vertix and with no edges a bipartite graph? V1 = {v} and V2 = {} – moller1111 Jan 8 at 3:34
1  
@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 at 9:14

Your Answer

 
discard

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.