Intact Shortest-Path Structure Does Not Determine Failure Response: A Tight Degree-Preserving Separation

A shortest-path representation can look complete and still omit exactly the information that becomes decisive after a failure. We study this gap for connected simple unweighted graphs. For a source s, we fix a strong intact observable consisting of the complete source-distance vector, the full source shortest-path DAG, the exact number of shortest s–v paths for every vertex, and the labeled degree of every vertex. We construct an infinite family of graph pairs that agree on all of these data, yet react differently to deletion of the same edge. The construction uses a same-layer degree-preserving 2-switch: it is invisible to intact source-shortest-path structure but becomes visible when a gateway edge fails. For parameter L ≥ 1, both post-failure distances remain finite, while their difference is exactly 2L. With n = 4L + 3, the gap is (n − 3)/2, yielding a linear lower bound. A matching O(n) upper bound follows from the length of simple replacement paths, and a padding argument gives Θ(n) extremal finite ambiguity for all sufficiently large n. Exhaustive small-graph search and a reproducible 40-instance verification sweep independently check the construction and formulas. The result isolates a structural limitation of intact shortest-path summaries: fault response requires information that can be absent even when distances, all tight source edges, multiplicities, and labeled degrees are fully known.