Question

Let \( G \) be a simple, unweighted, and undirected graph. A subset of the vertices and edges of \( G \) are shown below. 

It is given that \( a - b - c - d \) is a shortest path between \( a \) and \( d \); \( e - f - g - h \) is a shortest path between \( e \) and \( h \); \( a - f - c - h \) is a shortest path between \( a \) and \( h \). Which of the following is/are NOT the edges of \( G \)?

• A. \( (b,d) \)
• B. \( (b,g) \)
• C. \( (b,h) \)
• D. \( (e,g) \)

Hint:

For shortest path problems in graphs, analyze given shortest paths carefully to determine missing edges.

Answer 1

The Correct Option is A, C, D

Analyze the shortest paths provided in the problem.
The shortest path from \( a \) to \( d \) is \( a - b - c - d \). This means there is no direct edge between \( b \) and \( d \).
The shortest path from \( e \) to \( h \) is \( e - f - g - h \). This implies that \( e \) and \( g \) are not directly connected.
The shortest path from \( a \) to \( h \) is \( a - f - c - h \), suggesting that \( b \) and \( h \) are not directly connected.