GkSeries.com

Graph Theory Quiz | Graph Theory Objective type Questions and Answers

Download PDF

Free download in PDF Graph Theory Objective type Questions and Answers for competitive exams. These short objective type questions with answers are very important for Board exams as well as competitive exams. These short solved questions or quizzes are provided by Gkseries.
Go To Download Page
(21) How many onto (or surjective) functions are there from an n-element (n => 2) set to a 2-element set?
[A] 2n
[B] 2n - 1
[C] 2n - 2
[D] 2(2n – 2)
Answer: 2n - 2
(22) Hasse diagram are drawn
[A] Partially ordered sets
[B] Lattices
[C] Boolean algebra
[D] None of these
Answer: Partially ordered sets

DOWNLOAD CURRENT AFFAIRS PDF FROM APP

(23) In how many ways can 5 balls be chosen so that 2 are red and 3 are black
[A] 910
[B] 990
[C] 970
[D] None of these
Answer: 990
(24) Circle has ____________
[A] No vertices
[B] Only 1 vertex
[C] 8 vertices
[D] None of these
Answer: No vertices
(25) The proposition ~qvp is equivalent to
[A] p?q
[B] q?p
[C] p?q
[D] p?q
Answer: q?p
(26) If B is a Boolean Algebra, then which of the following is true
[A] B is a finite but not complemented lattice
[B] B is a finite, complemented and distributive lattice
[C] B is a finite, distributive but not complemented lattice
[D] B is not distributive lattice
Answer: B is a finite, complemented and distributive lattice
(27) If R is a relation “Less Than” from A = {1,2,3,4} to B = {1,3,5} then RoR-1 is
[A] {(3,3), (3,4), (3,5)}
[B] {(3,1), (5,1), (3,2), (5,2), (5,3), (5,4)}
[C] {(3,3), (3,5), (5,3), (5,5)}
[D] {(1,3), (1,5), (2,3), (2,5), (3,5), (4,5)}
Answer: {(3,3), (3,5), (5,3), (5,5)}
(28) The number of distinguishable permutations of the letters in the word BANANA are,
[A] 60
[B] 36
[C] 20
[D] 10
Answer: 60
(29) Let G be a simple undirected planar graph on 10 vertices with 15 edges. If G is a connected graph, then the number of bounded faces in any embedding of G on the plane is equal to
[A] 3
[B] 4
[C] 5
[D] 6
Answer: 6
(30) A graph is tree if and only if
[A] Is planar
[B] Contains a circuit
[C] Is minimally
[D] Is completely connected
Answer: Is minimally
31 How many different words can be formed out of the letters of the word VARANASI?
[A] 64
[B] 120
[C] 40320
[D] 720
Answer: 720
32 Suppose v is an isolated vertex in a graph, then the degree of v is
[A] 0
[B] 1
[C] 2
[D] 3
Answer: 0
33 The complete graph with four vertices has k edges where k is
[A] 3
[B] 4
[C] 5
[D] 6
Answer: 6
34 Which one of the following statements is incorrect ?
[A] The number of regions corresponds to the cyclomatic complexity
[B] Cyclometric complexity for a flow graph G is V(G) = N–E+2, where E is the number of edges and N is the number of nodes in the flow graph
[C] Cyclometric complexity for a flow graph G is V(G) = E–N+2, where E is the number of edges & N is the number of nodes in the flow graph
[D] Cyclometric complexity for a flow graph G is V(G) = P + 1, where P is the number of predicate nodes contained in the flow graph G
Answer: Cyclometric complexity for a flow graph G is V(G) = N–E+2, where E is the number of edges and N is the number of nodes in the flow graph
35 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 graph drawn in a plane in such a way that any pair of edges meet only at their end vertices
36 Length of the walk of a graph is
[A] The number of vertices in walk W
[B] The number of edges in walk W
[C] Total number of edges in a graph
[D] Total number of vertices in a graph
Answer: The number of edges in walk W
37 A graph with one vertex and no edges is
[A] multigraph
[B] digraph
[C] isolated graph
[D] trivial graph
Answer: trivial graph
38 In any undirected graph the sum of degrees of all the nodes
[A] Must be even
[B] Are twice the number of edges
[C] Must be odd
[D] Need not be even
Answer: Are twice the number of edges
39 In a graph if e=[u, v], Then u and v are called
[A] Endpoints of e
[B] Adjacent nodes
[C] Neighbors
[D] All of above
Answer: All of above
40 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: 2d

Please share this page

Click Here to Read more questions

Teacher Eligibility Test