Bissoy.com
Doctors Medicines MCQs Q&A

Given G is a bipartite graph and the bipartitions of this graphs are U and V respectively. What is the relation between them?

Given G is a bipartite graph and the bipartitions of this graphs are U and V respectively. What is the relation between them? Correct Answer Sum of degrees of vertices in U = Sum of degrees of vertices in V

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.

Related Questions

How many of the following statements are correct? i) All cyclic graphs are complete graphs. ii) All complete graphs are cyclic graphs. iii) All paths are bipartite. iv) All cyclic graphs are bipartite. v) There are cyclic graphs which are complete.
There are four students in a class namely A, B, C and D. A tells that a triangle is a bipartite graph. B tells pentagon is a bipartite graph. C tells square is a bipartite graph. D tells heptagon is a bipartite graph. Who among the following is correct?
A k-regular bipartite graph is the one in which degree of each vertices is k for all the vertices in the graph. Given that the bipartitions of this graph are U and V respectively. What is the relation between them?
The line graph L(G) of a simple graph G is defined as follows: There is exactly one vertex v(e) in L(G) for each edge e in G. For any two edges e and e' in G, L(G) has an edge between v(e) and v(e'), if and only if e and e' are incident with the same vertex in G. Which of the following statements is/are TRUE? (P) The line graph of a cycle is a cycle. (Q) The line graph of a clique is a clique. (R) The line graph of a planar graph is planar. (S) The line graph of a tree is a tree.
All paths and cyclic graphs are bipartite graphs.
Consider the following graphs. The curves in the graphs indicate different age groups in the populations of two countries A and B over a period of few decades: With reference to the above graphs, which of the following are the most logical and rotational inferences that can be made? 1. Over the last two and a half decades, the dependency ratio for country B has decreased. 2. By the end of the next two and a half decades, the dependency ratio of country A and be much less than that of country B. 3. In the next two decades, the work-force relative to its total population will increase in country B as compared to country A. Select the correct answer using the code given below.
According to Naiya̅yikas we ascertain the relation of universal concomitance between x and y :  (A) We can determine the relation only if we can determine the relation of essential identity between x and y   (B) By perceiving that in all cases the presence of x is accompanied by the presence of y  (C) We can determine the relation only if we can determine the relation of cause and effect between x and y  (D) By not perceiving any instance where the presence of x is not accompanied by the presence of y or vice-versa.  Choose the correct answer from the options given below : 
What is testing of a complete bipartite subgraph in a bipartite graph problem called?
Bipartite graph belongs to class 1 graphs.
In a complete bipartite graph, the intersection of two sub graphs is ______