Matrixes are typically stored in contiguous memory, and the content must have a defined mapping from the sequential memory layout to matrix cell
(x,y) (a typical mapping is described in this former "Programmers" post). Now, if there is to add a new vertex, one has to increase the storage for a
|V|² matrix to
(|V|+1)². That means you will have to copy the whole content of the former smaller matrix to the newly allocated memory for the bigger matrix, because the mapping won't fit anymore. And that is obviously an
One can mitigate this problem by providing a better memory allocation strategy, for example, by not increasing the matrix size one-by-one, but in bigger steps.