GATE 2016 CS (CS2) – Question 38

Engineering Mathematics · Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) · 2 marks · Multiple choice

There are 23 distinct compounds U. Each of nine compounds in S reacts with exactly three compounds of U. Which always holds? I: Every compound in U∖S reacts with an odd number. II: At least one in U∖S reacts with an odd number. III: Every compound in U∖S reacts with an even number.

Only I
Only II
Only III
None

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) Only II

Explanation

Represent reactions as undirected edges. The handshaking lemma requires an even total number of odd-degree vertices. S already contributes nine odd-degree vertices, so an odd, positive number outside S must also have odd degree. At least one exists, II. Neither all odd nor all even is forced. Select B.

More Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions

GATE 2017 CS (CS2) Q33 – An undirected graph has n vertices, 25 edges and every vertex has degree at least three.…
GATE 2012 CS (CS1) Q27 – A connected simple planar graph has ten vertices and fifteen edges. How many bounded faces…
GATE 2012 CS (CS1) Q36 – Which graph A,B,C,D is isomorphic to the given graph?
GATE 2013 CS (CS1) Q35 – For undirected graphs, P: The number of odd-degree vertices is even. Q: The sum of all…
GATE 2013 CS (CS1) Q36 – The line graph L(G) has one vertex per edge of simple G, and joins vertices iff their G…
GATE 2011 CS (CS1) Q27 – The drawings show complete graph K₄ and cube graph Q₃. Which is true?

All Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions →