Gate Exam

Which of the following statements is/are TRUE for undirected graphs?
P: Number of odd degree vertices is even. Q: Sum of degrees of all vertices is even.

Option
(A) P only
(B) Q only
(C) Both P and Q
(D) Neither P nor Q

Read Solution (Total 2)

draw sample undirected graph and check (A)only follows
10 years agoHelpfull: Yes(0) No(0)

Answer (C)
Q is true: Since the graph is undirected, every edge increases the sum of degrees by 2.
P is true: If we consider sum of degrees and subtract all even degrees, we get an even number (because Q is true). So total number of odd degree vertices must be even.
8 years agoHelpfull: Yes(0) No(0)

Gate Other Question

Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is Â½. What is the expected number of unordered cycles of length three?

Option
(A) 1/8
(B) 1
(C) 7
(D) 8 In a k-way set associative cache, the cache is divided into v sets, each of which
consists of k lines. The lines of a set are placed in sequence one after another.
The lines in set s are sequenced before the lines in set (s+1). The main memory
blocks are numbered 0 onwards. The main memory block numbered j must be
mapped to any one of the cache lines from
(A) (j mod v) *k to (j mod v) *k + (k − 1)
(B) (j mod v) to (j mod v) + (k − 1)
(C) (j mod k) to ( j mod k) + (v − 1)
(D) (j mod k) * v to ( j mod k) * v + (v − 1)