Q.1
A graph which has the same number of edges as its complement must have number of vertices congruent to ______ or _______ modulo 4(for integral values of number of edges).
  • a) 6k, 6k-1
  • b) 4k, 4k+1
  • c) k, k+2
  • d) 2k+1, k
Q.2
Every Isomorphic graph must have ________ representation.
  • a) cyclic
  • b) adjacency list
  • c) tree
  • d) adjacency matrix
Q.3
A cycle on n vertices is isomorphic to its complement. What is the value of n?
  • a) 5
  • b) 32
  • c) 17
  • d) 8
Q.4
How many perfect matchings are there in a complete graph ofvertices?
  • a) 60
  • b) 945
  • c) 756
  • d) 127
Q.5
A graph G has the degree of each vertex is ≥ 3 say, deg(V) ≥ 3 ∀ V ∈ G such that 3|V| ≤ 2|E| and 3|R| ≤ 2|E|, then the graph is said to be ________ (R denotes region in the graph)
  • a) Planner graph
  • b) Polyhedral graph
  • c) Homomorphic graph
  • d) Isomorphic graph
Q.6
A complete n-node graph Kn is planar if and only if _____________
  • a) n ≥ 6
  • b) n2 = n + 1
  • c) n ≤ 4
  • d) n + 3
Q.7
A graph is ______ if and only if it does not contain a subgraph homeomorphic to k5 or k3,3.
  • a) bipartite graph
  • b) planar graph
  • c) line graph
  • d) euler subgraph
Q.8
An isomorphism of graphs G and H is a bijection f the vertex sets of G and H. Such that any two vertices u and v of G are adjacent in G if and only if ____________
  • a) f(u) and f(v) are contained in G but not contained in H
  • b) f(u) and f(v) are adjacent in H
  • c) f(u * v) = f(u) + f(v)
  • d) f(u) = f(u)2 + f(v)2
Q.9
What is the grade of a planar graph consisting of 8 vertices andedges?
  • a) 30
  • b) 15
  • c) 45
  • d) 106
Q.10
A _______ is a graph with no homomorphism to any proper subgraph.
  • a) poset
  • b) core
  • c) walk
  • d) trail
0 h : 0 m : 1 s