adplus-dvertising
frame-decoration

Question

An ordered n-tuple (d1, d2, … , dn) with d1 >= d2 >= ⋯ >= dn is called graphic if there exists a simple undirected graph with n vertices having degrees d1, d2, … , dn respectively. Which of the following 6-tuples is NOT graphic?

a.

(1, 1, 1, 1, 1, 1)

b.

(2, 2, 2, 2, 2, 2)

c.

(3, 3, 3, 1, 0, 0)

d.

(3, 2, 1, 1, 1, 0)

Answer: (c).(3, 3, 3, 1, 0, 0)

Engage with the Community - Add Your Comment

Confused About the Answer? Ask for Details Here.

Know the Explanation? Add it Here.

Q. An ordered n-tuple (d1, d2, … , dn) with d1 >= d2 >= ⋯ >= dn is called graphic if there exists a simple undirected graph with n vertices having degrees d1, d2, … , dn respectively....

Similar Questions

Discover Related MCQs

Q. The maximum number of edges in a bipartite graph of 12 vertices is __________________________.

Q. A cycle on n vertices is isomorphic to its complement. The value of n is _____.

Q. If G is a forest with n vertices and k connected components, how many edges does G have?

Q. Let d denote the minimum degree of a vertex in a graph. For all planar graphs on n vertices with d ≥ 3, which one of the following is TRUE?

Q. The 2^n vertices of a graph G corresponds to all subsets of a set of size n, for n >= 6 . Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements. The number of vertices of degree zero in G is:

Q. The 2^n vertices of a graph G corresponds to all subsets of a set of size n, for n >= 6. Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements. The number of connected components in G is:

Q. Let G be a simple connected planar graph with 13 vertices and 19 edges. Then, the number of faces in the planar embedding of the graph is

Q. Let G be a simple graph with 20 vertices and 100 edges. The size of the minimum vertex cover of G is 8. Then, the size of the maximum indepen­dent set of G is

Q. Let s and t be two vertices in a undirected graph G + (V, E) having distinct positive edge weights. Let [X, Y] be a partition of V such that s ∈ X and t ∈ Y. Consider the edge e having the minimum weight amongst all those edges that have one vertex in X and one vertex in Y. Let the weight of an edge e denote the congestion on that edge. The congestion on a path is defined to be the maximum of the congestions on the edges of the path. We wish to find the path from s to t having minimum congestion. Which one of the following paths is always such a path of minimum congestion?

Q. Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is _______________.

Q. A graph is self-complementary if it is isomorphic to its complement. For all self-complementary graphs on n vertices, n is

Q. In a connected graph, a bridge is an edge whose removal disconnects a graph. Which one of the following statements is True?

Q. What is the number of vertices in an undirected connected graph with 27 edges, 6 vertices of degree 2, 3 vertices of degree 4 and remaining of degree 3?

Q. The minimum number of colours that is sufficient to vertex-colour any planar graph is _______________.

Q. If all the edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and has minimum total weight is a

Q. Consider a weighted undirected graph with positive edge weights and let uv be an edge in the graph. It is known that the shortest path from the source vertex s to u has weight 53 and the shortest path from s to v has weight 65. Which one of the following statements is always true?

Q. G is a simple undirected graph. Some vertices of G are of odd degree. Add a node v to G and make it adjacent to each odd degree vertex of G. The resultant graph is sure to be