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

Correct Answer: 5040