A graph is a simple collection of points called vertices and a collection of lines called edges each of which joins either a pair of points or a single point to itself.

If no self loop& no parallel edges are present in a graph, the graph is (1)

known as _

A)Multigraph b) pseudograph c) simple graph d)None of these

2)If parallel edges are allowed but self loops are not permitted,the graph (1) known as

a)multigraph

b) pseudograph

c) simple graph

d) none of these

3)If parallel edges as well asself loops are allowed,the graph is known (1) as________

a)multigraph

b) pseudograph

c) simple graph

d) none of these

4) How many nodes are necessary to construct a graph with exactly 8 edges in which each node is of degree 2. (2)

a) 2

b) 4

c) 8

d) 16

5) The sum of the degrees of the vertices of a graph is ** (1)** a) equal to no. of edges

**b)twice the no. of edges**

c)half the no. of edges

d)thrice the no. of edges

6)In a graph,the number of vertices of odd degree is____

**(1)**

*___*a) odd

b) even

c) Zero

d) None of these

7) Degree of any vertex of a simple graph with n vertices is at the most____ (1)

a) n

b) (n+1)

c) (n-1)

d) 2n

8)Maximum number of edges in a simple graph with n vertices is (2)

a) n(n+1)/2 b)(n(n-1))/2 c) 2n d) n

9)Determine the no. of edges in a graph with 6 nodes,2 vertices of degree 4& 4 vertices of degree 2. (2)

a) 4

b) 8

c) 2

d) 16

10)An a directed graph, e is an edge from ato b then *__* (1)

a) a is known as initial vertex & b is not a terminal vertex

b) a is not initial vertex & b is not a terminal vertex

c) a is not initial vertex & b is not a terminal vertex

d) a is known as initial vertex & b is terminal vertex

11)A graph with n vertices is a complete graph if___________ (1)

a) degree of each vertex is n

b) degree of each vertex is n -1

c)degree of each vertex is n +1

d)degree of each vertex is 2n

12)No. of edges in a complete graph K_nis________ (1)

a) (n(n+1))/2 b)(n(n-1))/2 c) n d) n^2

13) Which is true? (2)

a) complete graph ↔regular graph

b) complete graph ↔regular graph but converse need not be true

c)regulargraph↔complete graph

d)regulargraph↔complete graph but converse need not be true

14) A complete bipartiate graph K_(m,n) is regular if_________ (1)

a) m>n

b) m**_** (1) a) pendant vertex b)isolated vertex c)node d)junction

15) How many edges K_6has? (2)

a) 30

b) 15

c) 6

d)21

16)How many edges K_4,6has? (2)

a) 24

b) 15

c) 10

d)12

17) Which graph is complete bipartite graph but not a regular graph ? (2)

a)K_(3,3 ) b)None of these c)K_(4,4 ) d)K_(1,6)

18) If G is a graph whose set of vertices is V. If V can be partitioned into two subsets V_1&V_2 such that every edge of G joins V_1 with V_2 also V_1∪V_2=V

And V_1∩V_2=∅ , then__________ (1)

G is a regular graph

b) G is bipartite graph

c) G is a complete graph

d) None of these

19) A vertex with degree zero is known as ** __** (1)

a) pendant vertex

b)isolated vertex

c)node

d)junction

20) A vertex with degree one is known as **_** (1)

a) pendant vertex

b) isolated vertex

c) node

d) junction

21) How many nodes are necessary to construct a graph with exactly n edges in which each node is of degree 2 ? (2)

a)n-1

b)n

c)n+1

d)2n

22) Two graphs G_1 and G_(2 ) are isomorphic if *_** (2)
a) no. of vertices as well as edges in G_1&G*(2 )are same

b)G_1has n vertices of degree K then G_2 must have exactly n vertices of degree K

c) adjacency is preserved

d) All of these

23) Under which condition K_(m,n) , the complete bipartiate graph will have an Eulerian circuit? (1)

a) If m = n & both are odd

b) If m ≠ n &either m is odd or n is odd

c)If both m & n are even (m=n,or m≠n).

d) None of these

24) An undirected graph possesses an Eulerian path if___________ (1)

a)it is connected & has either zero or two vertices of odd degree

b)it is connected & has even no of vertices(>2) of odd degree

c) Both (a) and (b)

d) none of these

25) An undirected graph possesses an Eulerian circuit if___________ (1)

a) it is connected & has two vertices of odd degree

b) it is connected & it’s vertices are all of even degree

c) Both (a) and (b)

d) none of these

26) A path is known as Eulerian path if____________ (1)

a) Every vertex of the graph G appears exactly once in the path

b) Every edge of the graph G appears exactly once in the path

c) Both (a) and (b)

d) None of these

27) A path in a connected graph G is Hamiltonian path if__________ (1)

a) It contains every edge of G exactly once.

b) It contains every vertex of G exactly once.

c) Both (a) and (b).

d) None of these.

28) How many Hamiltonian circuits exists in K_n? (2)

a) n

b) n-1

c) n(n-1)/2

d) (n-1)!/2

29) The length of Hamiltonian circuit of K_n is (1)

a) n

b) n-1

c) n(n-1)/2

d) (n-1)!/2

30) The length of Hamiltonian circuit is________ (1)

a) The no.of edges in the circuit

b) The no. of vertices in the circuit

c) No.of edges + vertices in the circuit

d) None of these

31) A complete graph K_n where n odd contains__________ (2)

a) Eulerian Circuit

b) Hamiltonian Circuit

c) Both (a) and (b)

d) None of these

32) If v, e and r are the number of vertices, edges and regions in the graph,

Then for any connected planar graph, which condition is satisfied? (2)

v + e + r = 2

v –e + r = 2

v + e – r = 2

v – e – r = 2

33) Which graphs are nonplanar graphs? (2)

a)K_5

b) K_3,3

c) Both (a) and (b)

d) None of these

34) A subgraph G’ of G is known as Spanning Subgraph if________ (1)

a) G’ contains all the edges of G

b) G’ contains all the vertices of G

c) Both (a) and (b)

d) None of these

35) A graph is called as null graph if___________ (1)

a) It has no edges

b) It has no vertices

c) It has no edges and no vertices

d) None of these