GATE CS 2023 Q46 — Graph Traversals (BFS, DFS)

To find the cardinality of $\mathcal{B}(\emptyset)$, we need to determine the number of valid Breadth-First Search (BFS) orderings of the graph $G = (V, E)$ starting from the vertex $\emptyset$.

1. Structure of the Graph

The vertex set $V$ is the power set of $U = \{1, 2, 3\}$:

The total number of vertices is $|V| = 2^3 = 8$.

An edge exists between two distinct vertices $A$ and $B$ if and only if $A \subsetneq B$ or $B \subsetneq A$.

2. Neighbors of the Start Vertex $\emptyset$

For any non-empty set $B \in 2^U \setminus \{\emptyset\}$, the empty set is a proper subset of $B$ (i.e., $\emptyset \subsetneq B$).

Therefore, the vertex $\emptyset$ is adjacent to every other vertex in the graph. The degree of $\emptyset$ is:

3. BFS Traversal from $\emptyset$

In a BFS starting from $\emptyset$:

1. The start vertex $\emptyset$ is visited first (at level 0).
2. All remaining $7$ vertices are direct neighbors of $\emptyset$ and are at distance $1$ (level 1).
3. Since all vertices in the graph are at distance $\le 1$ from $\emptyset$, the BFS will visit $\emptyset$ first, followed by all $7$ neighbors in some permutation.

Since the neighbors of a vertex can be visited in any arbitrary order during BFS, any permutation of these $7$ vertices yields a valid BFS ordering.

4. Calculation

The number of possible BFS orderings is the number of permutations of the $7$ neighbor vertices:

Thus, the cardinality of $\mathcal{B}(\emptyset)$ is 5040.