How to check whether a graph is connected in polynomial time?
Make a BFS/DFS traversal on the graph. If you visited every vertex then it is connected otherwise not.
Note: You have to apply BFS/DFS only one time on the graph