Bissoy.com
Doctors Medicines MCQs Q&A

The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can not be the degree sequence of any graph? I. 7, 6, 5, 4, 4, 3, 2, 1 II. 6, 6, 6, 6, 3, 3, 2, 2 III. 7, 6, 6, 4, 4, 3, 2, 2 IV. 8, 7, 7, 6, 4, 2, 1, 1

The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can not be the degree sequence of any graph? I. 7, 6, 5, 4, 4, 3, 2, 1 II. 6, 6, 6, 6, 3, 3, 2, 2 III. 7, 6, 6, 4, 4, 3, 2, 2 IV. 8, 7, 7, 6, 4, 2, 1, 1 Correct Answer II and IV

Key Points

Havel Hakimi theorem:
Arrange the degree of vertices in descending order
eg. d1, d2, d3... dn
Discard d1 and subtract '1' from the next 'di' degrees
Ex:3,2,2,1,1

discard degree 3 and subtract one from the next highest 3 degrees. It means removing a vertex of degree 3 that refers to removing 3 edges in the graphs.
So, 1,1,0,1

0,0,1,0  We should not get any negative value if it's negative, this is not a valid sequence, and Repeat it till we get the '0' sequence.

Option 1: 7, 6, 5, 4, 4, 3, 2, 1

5,4,3,3, 2, 1, 0
3, 2, 2, 1, 0, 0
1,1,0,0,0

0,0,0,0,0

Hence true.
Option 2:  6, 6, 6, 6, 3,3,2, 2
5, 5, 5, 2, 2, 1, 2 (put them in descending order)
5, 5, 5, 2, 2, 2, 1
3, 0, 0, 0, 1 (descending order)
3,1,0,0,0
0,-1,-1,0

Hence False.
Option 3: 7, 6, 6, 4, 4, 3, 2, 2
5,5, 3, 3, 2, 1, 1
4, 2, 2, 1, 0, 1
4, 2, 2, 1, 1, 0 (descending order)
1,1,0,0,0
Hence True.
Option 4: 8, 7, 7, 6, 4, 2, 1, 1
There is a degree 8 but there are only '8' vertices. A vertex cannot have an edge to itself in a simple graph. This is not a valid sequence.

Hence False.

The correct answer is II and IV.

Related Questions

Let D be a simple graph on 10 vertices such that there is a vertex of degree 1, a vertex of degree 2, a vertex of degree 3, a vertex of degree 4, a vertex of degree 5, a vertex of degree 6, a vertex of degree 7, a vertex of degree 8 and a vertex of degree 9. What can be the degree of the last vertex?
Which of the following statements regarding tree are correct? (A) All the links of a tree together does not constitute the complement of the corresponding tree (B) A connected subgraph of a connected graph is a tree if there exist (n - 1) nodes of the group (C) A connected subgraph of a connected graph is a tree if there exist many paths between any pair of nodes in it (D) The number of terminal nodes of end vertices of every tree are atleast two (E) Every connected graph has atleast one tree Choose the correct answer from the options given below: (1) (A) and (B) only (2) (B) and (C) only (3) (B) and (D) only (4) (D) and (E) only
SN1 reaction undergoes through a carbocation intermediate as follows: (X = Cl, Br, I) The correct statements are: I. The decreasing order of rate of SN1reaction is t-BuX > iso-PrX > EtX > MeX II. The decreasing order of ionization energy is MeX > EtX > iso-PrX > t-BuX III. The decreasing order of energy of activation is t-BuX > iso-PrX > EtX > MeX
Study the following statements.i) The displacement method is more useful when degree of kinematic indeterminacy is greater than the degree of static indeterminacy.ii) The displacement method is more useful when degree of kinematic indeterminacy is less than the degree of static indeterminacy.iii) The force method is more useful when degree of static indeterminacy is greater than the degree of kinematic indeterminacy.iv) The force method is more useful when degree of static indeterminacy is less than the degree of kinematic indeterminacy.The correct answer is
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.
Consider a weight balanced tree such that, the number of nodes in the left sub tree is at least half and at most twice the number of nodes in the right sub tree. The maximum possible height (number of nodes on the path from the root to the farthest leaf) of such a tree on k nodes can be described as
How is the rate of transpiration affected by decreasing humidity and by decreasing light intensity?   Decreasing humidity  Decreasing light intensity   (a).  Decreases Decreases  (b). Increases Decreases  (c). Increases Increases  (d). Decreases Increases
Consider the series - "animal, mammal, feline, tiger". Which of the following statement/s is/are true with reference to this series  (A) It is in order of increasing intension  (B) It is in order of increasing extension  (C) It is in order of decreasing intension  (D) It is in order of decreasing extension  Choose the correct answer from the options given below : 
Consider the series "tiger, feline, mammal, animal". Which of the following statement/s is/are true with reference to this series? (A) It is in order of increasing intension (B) It is in order of increasing extension (C) It is in order of decreasing intension (D) It is in order of decreasing extension Choose the correct answer from the options given below :
Consider the following with reference to Article 18? (a) No title, not being a military or academic distinction, shall be conferred by the State. (b) The citizen of India shall accept any title from any foreign State. (c) No person who is not a citizen of India shall, while he holds any office of profit or trust under the State, accept without the consent of the President any title from any foreign State. (d) The person holding any office of profit or trust under the State shall, without the consent of the President, accept any present, emolument, or office of any kind from or under any foreign State.