Depending on your input graph, there're several options, each with its own advantages. I personally wouldn't simulate the failure of every node and then check for connectivity in the whole graph, that takes too much time.
A more clever approach could be to construct a spanning tree. Every leaf on that tree can be removed without disconnecting the rest of the graph as the rest of the tree still connects everything else. Building that one tree allows you to skip the leaves from individual examination. You can even construct more trees to try and get some of the other nodes (non-leaves) to be leaves (which can then be skipped). BFS from several nodes could get you started.
Also, when you simulate the removal of 1 node, you only have to check if its neighbours are still connected to each other. If the neighbours are connected, then the rest of the graph is also connected. If the graph is dense, this should limit the work per node.