Proving that $NPSPACE\subseteq PSPACE$ using the proof of Savitch's Theorem We were shown a proof of $NPSPACE\subseteq PSPACE$ in class. In short, the proof says:


Let $L\in NPSPACE$.
Then there exists a non-deterministic polynomial space bounded Turing machine $M$ that accepts $L$.
For every input word $w$, the number of vertices in the configuration graph of $M$ is exponential in $|w|$.
Nevertheless, using the algorithm from Savitch's proof, we can check whether there exists a path in the graph from the initial state to the accepting state, using space polynomial in $|w|$.


My problem is the memory required to store the graph. How can we store the graph using space polynomial in $|w|$?
I had the same thoughts when i did Complexity course myself.
Its a very simple answer - the graph is stored on the tape and even though it is part of the input, its not calculated as part of the space complexity of the machine. 
This is by definition of space complexity analysis.