We consider a scenario in which a data owner outsources storage of a large graph to an untrusted server; the server performs computations on this graph in response to queries from a client (whether the data owner or others), and the goal is to ensure verifiability of the returned results. Applying generic verifiable computation (VC) would involve compiling each graph computation to a circuit or a RAM program and would incur large overhead, especially in the proof-computation time. In this work, we address the above by designing, building, and evaluating A litheia , a VC system tailored for graph queries such as computing shortest paths, longest paths, and maximum flows. The underlying principle of A litheia is to minimize the use of generic VC techniques by leveraging various algorithmic approaches specific for graphs. This leads to both theoretical and practical improvements. Asymptotically, it improves the complexity of proof computation by at least a logarithmic factor. On the practical side, our system achieves significant performance improvements over current state-of-the-art VC systems (up to a 10-orders-of-magnitude improvement in proof-computation time, and a 99.9% reduction in server storage), while scaling to 200,000-node graphs.