Q. Consider an undirected graph G where self-loops are not allowed. The vertex set of G is {(i, j): 1 <= i <= 12, 1 <= j <= 12}. There is an edge between (a, b) and (c, d) if |a − c| <= 1 and |b − d| <= 1. The number of edges in this graph is __________.

View solution

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. Which of the following 6-tuples is NOT graphic?

View solution

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

View solution

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

View solution

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

View solution

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?

View solution

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:

View solution

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:

View solution

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

View solution

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

View solution

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?

View solution

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 _______________.

View solution

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

View solution

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

View solution

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?

View solution

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

View solution

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

View solution

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?

View solution

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

View solution