Thread: Bipartite Graphs

A graph G has a property that every edge of G joins an odd vertex with an even vertex. Prove that G is bipartite and has even size.

Please help me out.

Thanks.

Hi,

Originally Posted by zhupolongjoe

A graph G has a property that every edge of G joins an odd vertex with an even vertex. Prove that G is bipartite and has even size.

Please help me out.

Thanks.

this is how i understand your language, pls correct me if otherwise:
"odd vertex" means vertex of odd degree,
"size of G" is the number of vertices of G.

Then the first statement is obvious (partition of the graph consists of the set of odd-degree vertices and the set of even-degree vertices),
and the second statement is wrong ( consider graph G=(V,E) where V={u,v,w} and E={{u,v},{v,w}} ).

THat's correct....why the text tell me to prove something that is false?

Originally Posted by zhupolongjoe

THat's correct....why the text tell me to prove something that is false?

I don't know.. provided you typed the problem correctly and definitions fit, we can't say anything about the size of G. In fact, the size of G can be an arbitrary number n: take G=(V,E), V={v_i ; i < n}, E = empty set.

Originally Posted by zhupolongjoe

THat's correct....why the text tell me to prove something that is false?

In a graph with all even vertices, every odd vertex is joined to an even vertex.

Well okay, verbatim, the problem reads "A graph G has the property that every edge of G joins an odd vertex with an even vertex. Show that G is bipartite and has even size."

Oh, oops, actually the books uses "size" for number of edges, not vertices. (order is number of vertices)...maybe that will make a difference.

Originally Posted by zhupolongjoe

Well okay, verbatim, the problem reads "A graph G has the property that every edge of G joins an odd vertex with an even vertex. Show that G is bipartite and has even size."

Do you see how important language is?
Even now I would prefer the addition of the phrase “A graph with at least one edge…”.
It is clear from the statement of the problem that no edge can have two even vertices or two odd. Therefore, the graph is partition into two sets, even vertices and odd vertices. No two vertices in either set share an edge.
Therefore, the graph is bipartite.