Question

9. Given G is a bipartite graph and the
bipartitions of this graphs are U and
V respectively. What is the relation
between them?
(1 Point)
Number of vertices in U =
Number of vertices in V
Sum of degrees of vertices in U
= Sum of degrees of vertices in
V
Number of vertices in U>
Number of vertices in V
all cyclic graph are bipartite.​

Answer 1

Answer:

We can prove this by induction. By adding one edge, the degree of vertices in U is equal to 1 as well as in V. Let us assume that this is true for n-1 edges and add one more edge. Since the given edge adds exactly once to both U and V we can tell that this statement is true for all n vertices.