Suppose $\lambda(G)$ =$k$ $\gt 0$. Show that there are sets of vertices $U$ and $V$ that partition the vertices of $G$, and such that there are exactly $k$ edges with one endpoint in $U$ and one endpoint in $V$.
I tried to prove this by induction on value of k (That is, suppose statement is true for k $\lt$ n and show statement still holds when k is n) , but in vain. Can anybody give me a hint or answer to this problem?
By definition $\lambda(G)=k$ is the minimum number of edges that need to be removed from $G$ to make it disconnected. So take $k$ edges that make $G$ disconnected when they are removed.
The resulting graph will have exactly two connected components (it cannot have less, because otherwise, adding back one of the edges still makes it disconnected).
Let $A$ and $B$ be the two edges. Clearly no edge besides the $k$ removed edges can have one end in $A$ and the other in $B$. On the other hand, each of the $k$ selected edges must have one end in each component, otherwise the graph is still disconnected after adding back that edge.
So $\{A,B\}$ is the desired partition.