title: Determining if a graph is K-vertex-connected
body: <p>I'm looking to come up with an polynomial time algorithm that takes input in the form of a graph, G, and an integer, K, and determines whether G is K-vertex connected. I'm thinking that this would likely utilize Depth First Search. I can see how it could be none with a none-polynomial solution, i.e. just deleting K random vertices, running DFS to check for connectivity, and then doing it again with a different group of vertices. A run time of ~O(n^K) is a little much though, and it is apparently possible to bring this down to polynomial time. Any idea what I'm missing here? I imagine it has something to do with the non-tree vertices that we get after running a DFS, but I'm not totally sure what I'm looking for? Thanks in advance!</p>
  
  <p>Edit: To be clear, i am <em>not</em> looking to determine the connectivity of the graph. Rather, a number, k, is given on input and I am looking to check if the graph is k connected. It will <em>not</em> produce an answer that gives the connectivity of the graph, just a yes or no. </p>