Question

Consider the given graph and shortest paths: The shortest paths given are: \[ a - b - c - d, \quad e - f - g - h, \quad a - f - c - h \] Which of the following cannot be an edge in the original graph?

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

Hint:

Edges that do not contribute to any shortest path are likely to be absent from the graph.

Answer 1

The Correct Option is C

To determine which edge cannot exist in the original graph, we analyze the shortest paths: 1. The given shortest paths are a - b - c - d, e - f - g - h, and a - f - c - h. 2. If an edge were present in the original graph but not used in any shortest path, it might be an invalid edge. 3. Checking each option: - \( (e, f) \) is part of the shortest path e - f - g - h. - \( (b, d) \) could be an alternative connection but is not necessarily invalid. - \( (b, g) \) is highly unlikely as there is no connection between \( b \) and \( g \) in the shortest path. - \( (b, h) \) may be a possible long path but does not necessarily violate the shortest path. Thus, the edge \( (b, g) \) cannot exist in the original graph. Conclusion: The correct answer is (3) (b, g), as this edge does not fit within the provided shortest paths.