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: Understand the graph structure

The vertex set consists of all subsets of a 3-element universe U. Hence, the graph has:

2³ = 8 vertices

An edge exists between two vertices A and B if one is a subset of the other.

---

Step 2: Degree of the starting vertex

The empty set ∅ is a subset of every other subset of U. Therefore, it is directly connected to all remaining vertices.

Degree of ∅ = 7

---

Step 3: Shape of the BFS tree

Starting BFS from ∅:

• ∅ is visited first
• All other vertices are discovered immediately from ∅

Thus, the BFS tree has only two layers:

• Level 0: {∅}
• Level 1: all 7 nonempty subsets

---

Step 4: Count possible BFS traversals

After visiting ∅, BFS may visit the 7 adjacent vertices in any order, since they are all at the same level and no further discoveries are made.

Hence, the number of distinct BFS traversal orders equals the number of permutations of these 7 vertices:

7! = 5040

---

Final Answer:

|𝔅(∅)| = 5040