GATE CS 2023 (Forenoon) — Question 56

Discrete MathematicsGraph Theory (Connectivity, Paths, Cycles, Trees)NAT2 marksHard

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 \(B(A)\). If \(\phi\) denotes the empty set, then the cardinality of \(B(\phi)\) is ________.
Practise the full 2023-FN paper
Challenge a friend: WhatsApp Telegram
Recommended book · affiliate linkIntroduction to Algorithms (CLRS)The standard reference behind most GATE algorithm questions.
Practise more on Graph Theory (Connectivity, Paths, Cycles, Trees)Timed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group