Graph-grounded language models are usually evaluated by answer accuracy, yet a serialized prompt is a string representation of a graph rather than the graph itself. We argue that faithful graph-grounded reasoning requires the composed predictor F𝜃 ∘ z to be well-defined on graph-query equivalence classes: structurally equivalent graph-query pairs should induce the same prediction regardless of textual realization. We formalize this as a structural invariance property, decompose unfaithfulness into syntactic instability, semantic interference, and distractor susceptibility, and introduce corresponding diagnostics. On controlled graph reasoning tasks, DeepSeek-V4-Flash achieves 98.9% accuracy and near-perfect syntactic stability (FS = .975), yet its isomorphism consistency drops from .969 to .701 under semantic-name relabeling (∆_sem = .268); only 72.9% of originally correct answers survive this transformation. Across four model families, we observe targeted semantic interference in high-accuracy models, broad unfaithfulness in weaker models, and near-perfect invariance as a capability ceiling. A graph-grounded LLM can be accurate without being structurally faithful: its predictions may fail to remain invariant under graph-equivalent textual relabelings.