Complete and Connected Graphs

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