1. A bridge can not be a part of _______
a) a simple cycle
b) a tree
c) a clique with size ≥ 3 whose every edge is a bridge
d) a graph which contains cycles
.
2. Any subset of edges that connects all the vertices and has minimum total weight, if all the edge weights of an undirected graph are positive is called _______
a) subgraph
b) tree
c) hamiltonian cycle
d) grid
3. G is a simple undirected graph and some vertices of G are of odd degree. Add a node n to G and make it adjacent to each odd degree vertex of G. The resultant graph is ______
a) Complete bipartite graph
b) Hamiltonian cycle
c) Regular graph
d) Euler graph
4. Let G be a directed graph whose vertex set is the set of numbers from 1 to 50. There is an edge from a vertex i to a vertex j if and only if either j = i + 1 or j = 3i. Calculate the minimum number of edges in a path in G from vertex 1 to vertex 50.
a) 98
b) 13
c) 6
d) 34
.
5. What is the number of vertices in an undirected connected graph with 39 edges, 7 vertices of degree 2, 2 vertices of degree 5 and remaining of degree 6?
a) 11
b) 14
c) 18
d) 19
Explanation: We know that, sum of degree of all the vertices = 2 * number of edges
2*7 + 5*2 + 6*x = 39*2
x=9
Number of vertices = 7 + 2 + 9 = 18.
6. ______ is the maximum number of edges in an acyclic undirected graph with k vertices.
a) k-1
b) k2
c) 2k+3
d) k3+4
.
7. The minimum number of edges in a connected cyclic graph on n vertices is _____________
a) n – 1
b) n
c) 2n+3
d) n+1
.
8. The maximum number of edges in a 8-node undirected graph without self loops is ____________
a) 45
b) 61
c) 28
d) 17
9. Let G be an arbitrary graph with v nodes and k components. If a vertex is removed from G, the number of components in the resultant graph must necessarily lie down between _____ and _____
a) n-1 and n+1
b) v and k
c) k+1 and v-k
d) k-1 and v-1
.10. The 2n vertices of a graph G corresponds to all subsets of a set of size n, for n>=4. 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 can be ___________
a) n+2
b) 3n/2
c) n2
d) 2n
