## Checking if a $k$-subset of a graph is a vertex cover in time $O(kn)$

Given a graph $$G=(V,E)$$ with $$|V|=n,|E|=m$$. I am reading a $$\textit{brute force}$$ solution to determining whether each candidate vertex cover of size $$k \leq n$$ is a vertex cover. The graph does not have loops.

As per page 2 of the notes here we have:

• 1) $$C(n,k) = O(n^k)$$ $$k$$-subsets of $$V$$
• 2) $$O(kn)$$ time to check whether a subset is a vertex cover

I am considering 2).

What I would think of would be to take each edge in our graph, for which there is a maximum of $${n \choose 2} = O(n^2)$$, and check the candidate subset to see if at least one of the vertices is an endpoint of the edge, which would take $$O(kn^2)$$ checks.

I am not sure how the author arrived at $$O(kn)$$ operations, any insights appreciated.