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,
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}} ).
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.