**1. In a 7-node directed cyclic graph, the number of Hamiltonian cycle is to be ______**a) 728

b) 450

**c) 360**

d) 260

**2. If each and every vertex in G has degree at most 23 then G can have a vertex colouring of __________**

**a) 24**

**b) 23**

c) 176

d) 54

.

**3. Triangle free graphs have the property of clique number is __________**a) less than 2

b) equal to 2

c) greater than 3

**d) more than 10**

**4. Berge graph is similar to ______ due to strong perfect graph theorem.**a) line graph

**b) perfect graph**

c) bar graph

d) triangle free graph

**5. Let D be a simple graph on 10 vertices such that there is a vertex of degree 1, a vertex of degree 2, a vertex of degree 3, a vertex of degree 4, a vertex of degree 5, a vertex of degree 6, a vertex of degree 7, a vertex of degree 8 and a vertex of degree 9. What can be the degree of the last vertex?**a) 4

b) 0

**c) 2**

d) 5

**6. A ______ is a graph which has the same number of edges as its complement must have number of vertices congruent to 4m or 4m modulo 4(for integral values of number of edges).**a) Subgraph

b) Hamiltonian graph

c) Euler graph

**d) Self complementary graph**

**7. In a ______ the vertex set and the edge set are finite sets.**a) finite graph

**b) bipartite graph**

c) infinite graph

d) connected graph

.

**8. If G is the forest with 54 vertices and 17 connected components, G has _______ total number of edges.**a) 38

**b) 37**

c) 17/54

d) 17/53

**9. The number of edges in a regular graph of degree 46 and 8 vertices is ____________**a) 347

b) 230

**c) 184**

d) 186

Explanation: In a complete graph which is (n-1) regular (where n is the number of vertices) has edges n*(n-1)/2. In the graph n vertices are adjacent to n-1 vertices and an edge contributes two degree so dividing by 2. Hence, in a d regular graph number of edges will be n*d/2 = 46*8/2 = 184.**10. An undirected graph G has bit strings of length 100 in its vertices and there is an edge between vertex u and vertex v if and only if u and v differ in exactly one bit position. Determine the ratio of the chromatic number of G to the diameter of G?**a) 1/2

^{101}

**b) 1/50**

c) 1/100

d) 1/20