I know $\lambda (G)$ is the smallest cutset, i.e. the samllest number of edges we need to delete to disconnect $G$.
The number of edges with a vertex as its endpoint is the degree of the vertex. So, deleting the degree number of edges from that vertex would make $G$ disconnected. That would satisfy the = portion of what I'm looking for, and this could be for a minimum k degrees, where $k \geq 2$.
As for the less than part, I think of a graph with a minimum of 3 degrees, there could be a bridge that could be deleted, which would be 1 edge, which is less than the degree.
Combined, $\lambda(G)\leq k$. While this isn't a formal proof, is this correct? Am I missing anything?
Best Answer
Correct. More formally, once you constructed your argument about deleting edges around one vertex $v$ to disconnect it, then you showed that $\lambda(G) \le k$. Your second half of the argument is not needed except to show that it could indeed be strictly smaller.