In my discrete maths class we dabble a little bit into complexity theory. The lecturer frequently makes remarks such as: " "Is a graph G of n vertices k-connected?" is a problem in co-NP, since if it's not k-connected, we are given a k-set $E_k$ and can check in polynomial time whether $G - E_k$ is connected or not."
I'm trying to unpack this statement to see that we can indeed verify the "No" answer in polynomial time. My current interpretation is that we have to list out the $n \choose k$ sets $E_k$, and then run an algorithm that eventually would tell us that there is a pair of two vertices x and y in some $G - E_k$, such that there is no paths between x and y.
But here I'm stuck. How do I process to show that this process involves a polynomial-time algorithm? Is there anything being implied here that I should have deduced, or it's simply the case that there is such an algorithm somewhere in the literature that does the job?
You're missing the fact that the $E_k$ set is not something you need to find or search for; it is given to you as input to your verifier algoritm.
When you want to show that "is $G$ $k$-connected?" is in coNP, you need to argue that there is a polynomial algorithm for this problem:
To do this all you have to do is (a) construct $G\setminus E_k$ and (b) check that it is disconnected. Hopefully you can see for yourself that it is possible in polynomial time to check whether a single graph is connected or not.
The extra input is what makes it easier to see that the original problem is in (co-)NP than to see that the original problem is in (co-)P.
There are a few things swept under the rug here -- in particular, another way for $G$ to fail to be $k$ connected is, by definition, if it has too few vertices. But it is so easy to modify the algorithm to deal with this too that it would not always be mentioned explicitly. The short explanation of why the problem is in co-NP focuses on the part of the solution that the reader or listener might not have come up with themselves. In this case that is the choice of using, in particular, a $k$-vertex cut as the certificate of non-$k$-connectedness.
(Actually I think the certificate really needs to be a $(k-1)$-vertex-cut, but I don't care enough right now to unravel the off-by-one errors. That's another example of an "I am now convinced there is a solution; I don't need to write down all the details" situation).