GATE CS 2023 Q.56: Graph Theory

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 \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 Breadth First Search (BFS) starting from $A$ is denoted by $\mathcal{B}(A)$ .

If $\emptyset$ denotes the empty set, then the cardinality of $\mathcal{B}(\emptyset)$ is _______.

Your answer

Official answer and solution

Official answer: 5040
From: Official GATE 2023 answer key

Solution

Analyze adjacency in the powerset graph $G$ and count permutations of vertices at distance 1 from $\emptyset$ .

The set $U = \{1, 2, 3\}$ has $|2^U| = 2^3 = 8$ subsets.
An edge exists between $A$ and $B$ if and only if $A \neq B$ and either $A \subset B$ or $B \subset A$ .
Consider the empty set $\emptyset$ :
For any non-empty subset $B \in 2^U \setminus \{\emptyset\}$ , $\emptyset \subset B$ holds true. Therefore, $\emptyset$ is adjacent to every other vertex in the graph $G$ .
In a Breadth First Search starting from $\emptyset$ $\emptyset$ :
- Level 0 contains only $\emptyset$ (visited first).
- Level 1 contains all 7 other vertices of $G$ , because all of them are directly connected to $\emptyset$ by an edge.
Since all 7 remaining vertices are at distance 1 from the start vertex $\emptyset$ , a BFS can visit these 7 vertices in any arbitrary permutation among themselves.
The number of possible BFS vertex orderings is: $|\mathcal{B}(\emptyset)| = 7! = 5040$

Final answer

5040

Common trap

Assuming vertices are partitioned into levels by subset cardinality ( $|S| = 1, 2, 3$ ), overlooking that $\emptyset \subset S$ creates direct edges from $\emptyset$ to all subsets regardless of size.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2023 Computer Science and Information Technology (CS)
Question: 56 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source