Graph Theory
Q21.
G is undirected graph with n vertices and 25 edges such that each vertex of G has degree at least 3. Then the maximum possible value of n is ___________.Q22.
The minimum number of colours that is sufficient to vertex-colour any planar graph is _________.Q24.
A graph is self-complementary if it is isomorphic to its complement. For all self-complementary graphs on n vertices, n isQ25.
Consider the following directed graph: The number of different topological orderings of the vertices of the graph isQ26.
A given connected graph G is a Euler Graph if and only if all vertices of G are ofQ27.
Let G = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source. For x \in V, let d(x) denote the shortest distance in G from s to x. A breadth first search (BFS) is performed starting at s. Let T be the resultant BFS tree. If (u,v) is an edge of G that is not in T, then which one of the following CANNOT be the value of d(u)-d(v)?Q28.
Let T be a tree with 10 vertices. The sum of the degrees of all the vertices in T is _________.Q29.
A cube of side 1 unit is placed in such a way that the origin coincides with one of its top vertices and the three axes along three of its edges. What are the co-ordinates of the vertex which is diagonally opposite to the vertex whose co-ordinates are (1, 0, 1)?Q30.
If G is a forest with n vertices and k connected components, how many edges does G have?