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 389 students.
Show answer & explanation
Correct answer: 5040
Concept: Breadth First Search discovers vertices in layers ordered by graph distance from the start vertex. When every vertex of a layer is discovered from the SAME single parent — as happens at Level 1, whose vertices are all direct neighbors of the start vertex itself — their relative visiting order is exactly the arbitrary adjacency-list / enqueue order at that one shared parent, so it can realize any of the n! permutations (this single-parent condition is what makes the claim safe; in a deeper layer fed by several different parents the achievable orders are generally more constrained). So whenever a graph has exactly two layers from a given start vertex — the start itself and everything else — the entire second layer shares the start vertex as its sole parent, and 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.