Let U = {1, 2, 3}. Let 2U denote the power set of U. Consider an undirected…
2023
Let U = {1, 2, 3}. Let 2U denote the power set of U. Consider an undirected graph G whose vertex set is 2U.
For any A, B ∈ 2^U, (A, B) is an edge in G if and only if:
A ≠ BEither
A ⊆ BorB ⊆ A
For any vertex A in G, the set of all possible orderings in which the vertices of G can be visited in a Breadth First Search (BFS) starting from A is denoted by B(A).
If ∅ denotes the empty set, then the cardinality of B(∅) is ________.
Attempted by 366 students.
Show answer & explanation
Correct answer: 5040
Concept: Breadth First Search discovers vertices in layers ordered by graph distance from the start vertex. All vertices tied within the same layer can be visited in any relative order among themselves (that order depends only on the arbitrary adjacency-list / enqueue sequence at the vertices that discover them), so whenever a graph has exactly two layers from a given start vertex — the start itself and everything else — the count of distinct valid BFS visiting sequences equals the factorial of the size of that second layer.
Application to this graph:
Vertices:
∅, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}— all 8 subsets ofU = {1, 2, 3}.Edges from ∅: for every non-empty subset
S,∅ ⊆ S, so∅is directly comparable to — and hence adjacent to — all 7 other vertices.BFS levels from ∅:
Level 0 = {∅}andLevel 1contains the remaining 7 vertices; since every one of them is already adjacent to ∅, none is left over to form a Level 2.Ordering count: with only the two layers {∅} and the 7 remaining vertices, the concept above applies directly: the 7 same-layer vertices can be visited in any of their
7!relative orders.
Cross-check: Test the same reasoning on a smaller instance — U' = {1} gives only 2 subsets, ∅ and {1}, so BFS from ∅ has just 1 other vertex to place: 1! = 1 ordering, i.e. exactly the single trivial traversal — consistent with the concept. Scaling back up, |U| = 3 leaves 7 same-layer vertices after ∅, so the count is 7! = 5040, matching the direct computation above and the official GATE 2023 CS answer key.
Answer: |B(∅)| = 7! = 5040.