Consider the following statements:
P: There exists no simple, undirected and connected graph with 80 vertices and 77 edges.
Q: All vertices of an Euler graph are of even degree.
R: Every simple, undirected, connected and acyclic graph with 50 vertices has at least two vertices of degree one.
S: There exists a bipartite graph with more than ten vertices which is 2-colourable.
What is the number of correct statements?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: D. 4
Explanation
P: a connected graph on 80 vertices needs ≥ 79 edges, so true. Q: an Eulerian (circuit) graph has all degrees even, true. R: a tree with ≥ 2 vertices has ≥ 2 leaves, true. S: every bipartite graph is 2-colourable, true. All 4.More Discrete Structures and Optimization questions
- Consider the following statements: A. There exists a Boolean algebra with 5 elements. B. Every element of a Boolean algebra has a unique co…
- Match List I with List II. Choose the correct answer from the options given below:List I List II a. Planar graph I. Probabilistic model b.…
- Consider the statements: I. There does not exist a polynomial-time algorithm to solve integer linear programming problems. II. The main foc…
- Four persons P, Q, R and S are in custody and one of them has committed a crime. They say: P: Q did it. Q: S did it. R: I did not do it. S:…
- There are three boxes. The first box has 2 white, 3 black and 4 red balls. The second box has 3 white, 2 black and 2 red balls. The third b…
- Consider the primal problem: Maximize z = 5x1 + 12x2 + 4x3 subject to x1 + 2x2 + x3 = 10 2x1 − x2 + 3x3 = 8 x1, x2, x3 ≥ 0 Its dual problem…