Graph paper is a cheat.
I mean for players, of course. I do think that mapping is a good thing: the party needs a map to find their way back out. You can risk relying on memory, but if you have a map, you can say, "We go back to the elephant statue room" and I'll assume you follow your map, only describing things seen on the way back if they matter. If you have no map, I would briefly describe each room or corridor branch and let you pick your route at each stage, and you can hope you remember correctly.
I also think that Travis at The Mule Abides has a good point about mapping being one of the few things the adventurers do that the players can also do. It adds to a feeling of "being there".
But graph paper is a cheat. Actual pre-industrial people most likely would make a sketch of their route, maybe with crude distances written besides lines indicating tunnels or other routes. If they are an official expedition, equipped with surveying instruments, maybe they can use precise measurements; but otherwise, all the measurements would be in terms of "I think I could walk that distance in 1 minute." Nothing precise.
So players can use graph paper if they want, but I'm only giving out sketch map-precision descriptions.