A relation R is said to be circular if aRb and bRc together imply cRa. Which of the following options is/are correct?
Topic-wise GATE CS PYQs with verified steps
GATE CSE 2021 Set 1 · Q43
Time
Select all that applyOne or more correct
Solution
Official answer: C) If a relation S is reflexive and circular, then S is an equivalence relation.
Discrete MathematicsLet us test the properties of relation in each option:
For Option (C): If is reflexive and circular:
Symmetry: Suppose . Since is reflexive, . Applying the circular property to and , we get . Thus, is symmetric.
Transitivity: Suppose and . By circularity, . Since is symmetric, . Thus, is transitive.
Since is reflexive, symmetric, and transitive, it is an equivalence relation.
Counterexamples for other options:
Option (A): A relation that is reflexive and symmetric is not necessarily transitive (e.g., compatibility/tolerance relation).
Options (B) and (D): The empty relation on a non-empty set is vacuously circular, symmetric, and transitive, but it is not reflexive, and hence not an equivalence relation.
Therefore, only C is correct.
Try the question first, then check your work.
Examiner trap
Use reflexivity () combined with the definition of circularity to first derive symmetry, and then use both to prove transitivity.
This Discrete Mathematics previous year question is Q43 of the GATE CSE 2021 Set 1 paper. Find more GATE CSE PYQs on Discrete Mathematics in Engineering Mathematics, or browse all GATE CSE PYQs.
Free diagnostic
Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Discrete Mathematics PYQs now with no account.
An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.
Discrete Mathematics has 50 GATE CSE PYQs across 23 papers from 2011 to 2026. 4 of them are 2-mark MSQs like this one, and GATE CSE 2021 Set 1 has 3.
How GATE tests Discrete MathematicsIndependent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.