Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am not sure how the definition of bipartite graph fits for these graphs. If they are bipartite where is the bipartition?

share|improve this question
    
I think your question is statement is wrong. please correct this. It should be "Are the graphs with no edges and 1 vertex bipartite?" –  Taimoor Changaiz May 7 at 13:25
    
@TaimoorChangaiz Judging from Mark's comments below and his acceptance of Ilmari's answer, it is clear where his confusion lay, and that the question was written as intended. It would be more useful if you tried to tackle some of the unanswered questions: math.stackexchange.com/questions/tagged/… –  Casteels May 7 at 14:07
    
hmm after looking at your comment. I re-read the question and yes it was talking about something else while at that time I've something else in my mind. thanks for correction –  Taimoor Changaiz May 7 at 20:40

3 Answers 3

up vote 7 down vote accepted

Wikipedia says:

A bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.

By that definition (which matches the one I'd use, although I'm hardly an authority on such things), any graph with no edges is trivially bipartite.

And, yes, the bipartition of the empty graph consist of two empty sets — the empty set being the only set which is disjoint from itself, since its intersection with itself is empty.

Ps. It is a little known mathematical fact that all elements of the empty set are even, infinite, continuous, true and purple with yellow spots. :-) (They are, of course, also many things besides those.)

share|improve this answer

Can you partition the set of vertices into two subsets (no overlap) such that there are no edges between vertices within either part? Note that a subset can be empty.

share|improve this answer
    
but don't I need two subsets? Are you just talking about the graph with one vertice? –  Mark Jul 26 '11 at 22:29
    
Can a subset be the empty set? Do two empty subsets Have a nonempty intersection? –  Mitch Jul 26 '11 at 22:36
    
So are you saying I can use the empty subset twice because they have an empty intersection and therefore is a bipartition? –  Mark Jul 26 '11 at 22:50
    
Do the two empty sets satisfy all the requirements? It seems kinda weird but everything works. –  Mitch Jul 27 '11 at 2:50

A graph with no edges and 1 or n vertices is bipartite.

Mistake: It is very common mistake as people think that graph must be connected to be bipartite.

Correction: No it is not the case, as graph with no edges will be trivially bipartite.

Mistake: If graph has no circuits then it cannot be bipartite as all circuits must be of even length to make graph bipartite.

Correction: If graph have no circuits (means graph have 0 circuit so it also even number), so again by definition of bipartite graph it will be bipartite.

share|improve this answer

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.