Is the reason this is O(n): Suppose G is fully connected (every vertex has an edge to every other vertex). What is the runtime of adding a vertex to the graph such that the graph remains fully connected. Assume that the graph is represented using an adjacency matrix and has n vertices and m edges.(Assume no resizing needed)
Because in a connected graph represented by an adjacency matrix, we just need to add a column and row of 1s?