**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) k

^{2}

c) 2k+3

d) k

^{3}+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 2 ^{n} 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) 3**

^{n/2}c) n

^{2}

d) 2

^{n}