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?

  • 1
    $\begingroup$ 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 ? $\endgroup$ – AJed Jan 8 '13 at 2:32
  • $\begingroup$ @1.question: is every graph with n vertices and with no edges a biartite graph? $\endgroup$ – A.B. Jan 8 '13 at 3:32
  • $\begingroup$ @2.question: i meant, if it matters which one i choose, when detecting the graph bipartitiness? $\endgroup$ – A.B. Jan 8 '13 at 3:35
  • 1
    $\begingroup$ An equivalent characterization of bipartite graphs states that a graph is bipartite if and only if it contains no cycles of odd length. $\endgroup$ – Jernej Jan 8 '13 at 8:56

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.

| cite | improve this answer | |
  • $\begingroup$ @1.question: is a graph with only 1 vertix and with no edges a bipartite graph? V1 = {v} and V2 = {} $\endgroup$ – A.B. Jan 8 '13 at 3:34
  • 2
    $\begingroup$ @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. $\endgroup$ – Pål GD Jan 8 '13 at 9:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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