How to check whether a graph is connected in polynomial time? I have to solve the following problem:


  Consider the problem Connected:
  
  Input: An unweighted, undirected graph $G$.
  
  Output: True if and only if $G$ is connected.
  
  Show that Connected can be decided in polynomial time.


I have been at this for hours, and I can't seem to find a way to prove this.
Any hints?
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