COMPUTER SCIENCE AND ENGINEERING
DATA STRUCTURES
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
P Only
|
|
|
Q Only
|
|
|
Both P and Q
|
|
|
Neither P nor Q
|
Detailed explanation-1: -Which of the following statements is/are TRUE for undirected graphs? P: Number of odd degree vertices is even. Q: Sum of degrees of all vertices is even. Correct answer is option ‘C’.
Detailed explanation-2: -Theorem: An undirected graph has an even number of vertices of odd degree. This sum must be even because 2m is even and the sum of the degrees of the vertices of even degrees is also even. Because this is the sum of the degrees of all vertices of odd degree in the graph, there must be an even number of such vertices.
Detailed explanation-3: -Solution: (a) There is no such graph; since by problem 5, the number of odd-degree vertices in a graph is always even.
Detailed explanation-4: -Which of the following statements is true for every planar graph on n vertices? Explanation: A planar graph is a graph which can drawn on a plan without any pair of edges crossing each other.
Detailed explanation-5: -It can be proven that it is impossible for a graph to have an odd number of odd vertices. The Handshaking Lemma says that: In any graph, the sum of all the vertex degrees is equal to twice the number of edges.