The distance-2 layer of a graph

EasyProgramming & DSA~3m

Run breadth-first search from vertex $1$ on this undirected graph, whose edges are $\{1\text{-}2,\ 1\text{-}3,\ 2\text{-}4,\ 2\text{-}5,\ 3\text{-}5,\ 3\text{-}6,\ 5\text{-}7\}.$ How many vertices lie at shortest-path distance exactly $2$ from vertex $1$ ?

Show hints (2)+

Layer $0=\{1\}$ , layer $1=\{2,3\}$ . Which new vertices do the neighbours of $2$ and $3$ reveal?
Vertex $5$ is reachable from both $2$ and $3$ - count it once. Vertex $7$ sits one layer further out.

Answer

Reveal answer →

Want the full step-by-step worked solution? It's part of Premium - along with a worked solution for every question in the bank.

Practise free Unlock solutions

Asked at: Game-Based Aptitude, Options Market-Making

The distance-2 layer of a graph

Answer

Related questions