GATE 2023 CS Q.56: solution and answer

GATE 2023 · CSQ.56 · 2 marks · NAT

Let $U = {1, 2, 3}$ . Let $2^{U}$ denote the powerset of $U$ . Consider an undirected graph $G$ whose vertex set is $2^{U}$ . For any $A, B \in 2^{U}$ , $(A, B)$ is an edge in $G$ if and only if (i) $A \neq = B$ , and (ii) either $A ⊊ B$ or $B ⊊ 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 $\emptyset$ denotes the empty set, then the cardinality of $B (\emptyset)$ is ______.

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The cardinality of $B (\emptyset)$ , the set of distinct BFS visiting orders from $\emptyset$ , is $5040$ .

Official answer: 5040Source: Official answer key, GATE 2023 CS (IIT Kanpur)

U = {1,2,3}, so 2^U has 2^3 = 8 elements; G has 8 vertices, one per subset of U.
Edge rule: A and B are adjacent in G iff one is a strict (proper) subset of the other — this is the FULL comparability relation of the subset partial order (any degree of nesting), not merely the Hasse-diagram cover edges.
∅ is a proper subset of every one of the other 7 (nonempty) subsets of U, so ∅ is adjacent, directly, to all 7 remaining vertices in G.
Therefore a BFS starting at ∅ has exactly two levels: level 0 = {∅}, and level 1 = all 7 other vertices (each at distance 1) — there is no level 2, since every vertex is already reachable from ∅ in one step.
BFS mechanics: after dequeuing ∅, the algorithm scans ∅'s neighbor list and enqueues its unvisited neighbors. Since neither the graph nor the BFS specification fixes the order same-level neighbors are discovered, any of the 7! orders in which the 7 neighbors get enqueued is a valid BFS execution.
Once these 7 vertices are enqueued (in whichever order was chosen), dequeuing each in turn examines its own neighbors, but every vertex in G is already visited by that point, so no new vertex is discovered and the visiting order is not altered further — the final visiting order is exactly ∅ followed by the chosen permutation of the other 7.
Hence the number of distinct BFS visiting sequences starting from ∅ equals the number of permutations of the remaining 7 vertices: 7!.
7! = 7×6×5×4×3×2×1 = 5040.

KEY IDEA

$\emptyset$ is a proper subset of every one of the other 7 subsets of $U$ , so in $G$ it is adjacent to all of them simultaneously. A BFS starting at $\emptyset$ therefore has only two levels: level 0 = ${\emptyset}$ and level 1 = all remaining 7 vertices. Since BFS's traversal order is not fixed for vertices within the same level (the specification leaves the order neighbors are discovered/enqueued unconstrained), every one of the $7!$ permutations of the 7 level-1 vertices is a valid BFS visiting order following $\emptyset$ , and no further choices arise once they are enqueued (all vertices are already visited by then).

WATCH OUT FOR

Treating "adjacent iff proper subset" as only the Hasse-diagram cover relation (i.e., only edges to immediate subsets/supersets), which would make $\emptyset$ adjacent to just ${1}, {2}, {3}$ and force a multi-level BFS with far fewer orderings than $7!$ . The problem states the FULL comparability relation ( $A ⊊ B$ or $B ⊊ A$ , any degree of nesting), not just cover edges, so $\emptyset$ is directly adjacent to all 7 other vertices.

From the GATE 2023 CS paper. Every question of this paper · Download the full paper · All 28 Graph algorithms questions, with notes

GATE 2023 CS Q.56: solution and answer

Answer and solution

More Graph algorithms questions