Graph Bipartiteness

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:
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:
choice1: V1= {A, C}; V2 = {B, D}
choice2: V1= {A, D}; V2 = {B, C}

Does it matter which one i choose?

• 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? – A.B. Jan 8 '13 at 3:32
• @2.question: i meant, if it matters which one i choose, when detecting the graph bipartitiness? – A.B. 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

1 Answer

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.

• @1.question: is a graph with only 1 vertix and with no edges a bipartite graph? V1 = {v} and V2 = {} – A.B. 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