Question 15

Let us check each option:

• Option A (MNOPQR): Starts at $M$. The neighbors of $M$ are $N, Q, R$. After visiting $M$ and its neighbor $N$, the remaining unvisited neighbors at distance 1 ($Q$ and $R$) must be visited before any distance-2 vertex. However, $O$ (distance 2 from $M$) is visited before $Q$ and $R$, violating BFS.
• Option B (NQMPOR): Starts at $N$. The neighbors of $N$ are $M, O, Q$. After visiting $Q$ and $M$, the remaining neighbor $O$ at distance 1 must be visited before $P$ (distance 2). Visiting $P$ before $O$ violates BFS.
• Option C (QMNROP): Starts at $Q$. The neighbors of $Q$ are $M, N, O, P$. Vertex $R$ is at distance 2 from $Q$ (via $M$). Visiting $R$ before $O$ and $P$ violates BFS.
• Option D (POQNMR):
  1. Start at vertex $P$. Visit $P$, enqueue neighbors of $P$: $O$, then $Q$. Visited order: $P$.
  2. Dequeue $O$. Neighbors of $O$ are $N$ (unvisited), $Q$ (already queued), $P$ (visited). Enqueue $N$. Visited order: $P, O$.
  3. Dequeue $Q$. Neighbors of $Q$ are $M$ (unvisited), $N$ (already queued), $P$ (visited), $O$ (visited). Enqueue $M$. Visited order: $P, O, Q$.
  4. Dequeue $N$. Unvisited neighbors: none. Visited order: $P, O, Q, N$.
  5. Dequeue $M$. Unvisited neighbor is $R$. Enqueue $R$. Visited order: $P, O, Q, N, M$.
  6. Dequeue $R$. Queue empty. Visited order: $P, O, Q, N, M, R$.

The sequence POQNMR is a strictly valid BFS traversal order, matching option D.