Multiple Choice Questions

1. Maximum number of edges in a n-Node undirected graph without self loop is
A	n2
B	n(n – 1)
C	n(n + 1)
D	n(n – 1)/2
	Answer D

2. A vertex of a graph is called even or odd depending upon
A	Total number of edges in a graph is even or odd
B	Total number of vertices in a graph is even or odd
C	Its degree is even or odd
D	None of these
	Answer C

3. Let G be a complete undirected graph on 6 vertices. If vertices of G are labeled, then the number of distinct cycles of length 4 in G is equal to
A	15
B	30
C	90
D	360
	Answer A

4. The maximum degree of any vertex in a simple graph with n vertices is
A	n–1
B	n+1
C	2n–1
D	N
	Answer A
5. Which of the following statement is true A Every graph is not its own subgraph B The terminal vertex of a graph are of degree two. C A tree with n vertices has n edges. D A single vertex in graph G is a subgraph of G. Answer D 6. Find the number of relations from A = {cat, dog, rat} to B = {male , female} A 64 B 6 C 32 D 15 Answer A 7. The number of distinct relations on a set of 3 elements is A 8 B 9 C 18 D 512 Answer D 8. A graph with one vertex and no edges is A multigraph B digraph C isolated graph D trivial graph Answer D 9. The number of leaf nodes in a complete binary tree of depth d is A 2d B 2d–1+1 C 2d+1+1 D 2d+1 Answer A 10. The length of Hamiltonian Path in a connected graph of n vertices is A n–1 B n C n+1 D n/2 Answer A 11. A graph with no edges is known as empty graph. Empty graph is also known as A Trivial graph B Regular graph C Bipartite graph D None of these Answer A 12. The number of leaf nodes in a complete binary tree of depth d is A 2d B 2d–1+1 C 2d+1+1 D 2d+1 Answer A 13. The length of Hamiltonian Path in a connected graph of n vertices is A n–1 B n C n+1 D n/2 Answer A 14. A graph with n vertices will definitely have a parallel edge or self loop if the total number of edges are A greater than n–1 B less than n(n–1) C greater than n(n–1)/2 D less than n2/2 Answer A 15. The complete graph with four vertices has k edges where k is A 3 B 4 C 5 D 6 Answer D 16. A graph is tree if and only if A Is planar B Contains a circuit C Is minimally D Is completely connected Answer C 17. Choose the most appropriate definition of plane graph A A graph drawn in a plane in such a way that any pair of edges meet only at their end vertices B A graph drawn in a plane in such a way that if the vertex set of graph can be partitioned into two non - empty disjoint subset X and Y in such a way that each edge of G has one end in X and one end in Y C A simple graph which is Isomorphic to Hamiltonian graph D None of these Answer A 18. Suppose v is an isolated vertex in a graph, then the degree of v is A 0 B 1 C 2 D 3 Answer A 19. A connected graph T without any cycles is called A A tree graph B Free tree C A tree D All of above Answer D 20. Consider a weighted undirected graph with positive edge weights and let (u, v) be an edge in the graph. It is known that the shortest path from source vertex s to u has weight 53 and shortest path from s to v has weight 65. Which statement is always true ? A Weight (u, v) <= 12 B Weight (u, v) = 12 C Weight (u, v) >= 12 D Weight (u, v) > 12 Answer C 21 G1 and G2 are two graphs as shown : A  Both G1 and G2 are planar graphs B Both G1 and G2 are not planar graphs. C G1 is planar and G2 is not planar graph. D G1 is not planar and G2 is planar graph. Answer D 22. A connected graph T without any cycles is called A A tree graph B Free tree C A tree D All of above Answer D 23. Consider a weighted undirected graph with positive edge weights and let (u, v) be an edge in the graph. It is known that the shortest path from source vertex s to u has weight 53 and shortest path from s to v has weight 65. Which statement is always true ? A Weight (u, v) <= 12 B Weight (u, v) = 12 C Weight (u, v) >= 12 D Weight (u, v) > 12 Answer C 24. G1 and G2 are two graphs as shown : A  Both G1 and G2 are planar graphs B Both G1 and G2 are not planar graphs. C G1 is planar and G2 is not planar graph. D G1 is not planar and G2 is planar graph. Answer D 25. Choose the most appropriate definition of plane graph A A graph drawn in a plane in such a way that any pair of edges meet only at their end vertices B A graph drawn in a plane in such a way that if the vertex set of graph can be partitioned into two non - empty disjoint subset X and Y in such a way that each edge of G has one end in X and one end in Y C A simple graph which is Isomorphic to Hamiltonian graph D None of these Answer A