GATE CS 2023 Set 1 — Question 56
Go beyond PYQs with Success TrackerAI-powered personalised practice and doubt support. Unlimited practice on eligible plans; AI usage limits apply.NAT+2 / -0HardBFS TraversalGraphs (Data Structure)Programming & Data StructuresSets, Relations & FunctionsSets & CombinatoricsEngineering Mathematics
Engineering Mathematics → Graphs (Data Structure) → BFS Traversal
Last updated
Question
Let . Let denote the powerset of . Consider an undirected graph whose vertex set is . For any , is an edge in if and only if (i) , and (ii) either or . For any vertex in , the set of all possible orderings in which the vertices of can be visited in a Breadth First Search (BFS) starting from is denoted by .If denotes the empty set, then the cardinality of is ________.
Correct answer
5040 to 5040
Solution
The set has . The vertex set of the graph is the power set , which contains vertices.The edges are defined by the strict subset relation: an edge exists between and if one is a proper subset of the other ( or ).We perform a BFS starting from the empty set .
Since the empty set is a proper subset of every non-empty set, is connected to all other vertices in the graph. Specifically, for any , we have , so is an edge.In a BFS traversal:
Since the empty set is a proper subset of every non-empty set, is connected to all other vertices in the graph. Specifically, for any , we have , so is an edge.In a BFS traversal:
1.The start vertex is visited first (Level 0).
2.All neighbors of are discovered and added to the queue. Since is connected to all other vertices, all these 7 vertices are neighbors and belong to Level 1.
3.The order in which these 7 neighbors are visited depends on the order they are added to the BFS queue. Since the definition of BFS allows visiting neighbors in any arbitrary order, any permutation of these 7 vertices constitutes a valid BFS ordering.
4.Once these 7 vertices are in the queue, they are processed one by one. Since there are no remaining unvisited vertices (total vertices = 8), the traversal completes.
Thus, the number of valid BFS orderings is the number of permutations of the 7 non-empty subsets:Continue learning with Success Tracker
A step still unclear? Work through it with support
Use Success Tracker to ask about the reasoning, then try another GATE CS question to check your understanding.
AI-powered practice· Unlimited practice on eligible plans
- PYQs with solutions
- Attempt available previous-year questions, then compare your reasoning with the worked solution. Coverage varies by stream.
- Practice that adapts
- Choose a topic, work on weaker areas and bookmark questions to revisit. Your attempts feed your progress tracking.
- AI doubt support
- Ask follow-up questions about a step or concept while practising, instead of stopping at the final answer.
Unlimited practice is available on eligible plans. Free practice and AI usage have limits; check the current plan allowances before choosing.
This page stays readable without an account. AI responses can be wrong; check them against the solution and source material.
More questions on Graphs (Data Structure)
2026 Set 2 Q3A day can only be cloudy or sunny. The probability of a day being cloudy is , independent of…2026 Set 2 Q5‘When it is raining, peacocks dance.’ Based only on this sentence, which one of the following…2026 Set 2 Q8Figures (i) and (ii) represent intercity highway systems. The black dots represent cities and the…2026 Set 1 Q10An unbiased six-faced dice whose faces are marked with numbers 1, 2, 3, 4, 5, and 6 is rolled twice…2026 Set 2 Q10An unbiased six-faced dice whose faces are marked with numbers 1, 2, 3, 4, 5, and 6 is rolled twice…