Question

Let \(U = \{1,2,3\}\). Let \(2^U\) denote the power set 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\) iff (i) \(A \neq B\), and (ii) either \(A \subset B\) or \(B \subset A\). For any vertex \(A\) in \(G\), the set of all possible orderings in which the vertices of \(G\) can be visited in a BFS starting from \(A\) is denoted by \(\mathcal{B}(A)\). If \(\varnothing\) denotes the empty set, find \(|\mathcal{B}(\varnothing)|\). 

Hint:

If the start vertex is adjacent to every other vertex, BFS orderings are exactly the permutations of the remaining $n-1$ vertices $\Rightarrow$ $(n-1)!$.

Answer 1

Step 1: Neighbors of $\varnothing$.
$\varnothing \subset S$ for every nonempty $S\subseteq U$. Hence $\varnothing$ is adjacent to all the other $2^3-1=7$ vertices.
Step 2: BFS levels from $\varnothing$.
Level $0$: $\{\varnothing\}$.
Level $1$: all other $7$ vertices (every nonempty subset). No vertices remain beyond Level $1$.
Step 3: Count BFS orders.
BFS outputs the start first, then all Level-1 vertices in any tie-broken order. The number of possible visit sequences is the number of permutations of these $7$ neighbors: $7! = 5040$.
\[ \boxed{|\mathcal{B}(\varnothing)|=7!=5040} \]