Partition of graph with $\lambda(G)$

Question

Let $\lambda(G)=\min\{|X|:X \subset E(G) \wedge G-Y \text{ is not connected} \}$ (minimum number of edged to delete to disconnect conntected graph). Let $\lambda(G) = k > 0$. Show that there is such partition $\{U, V\}$ of vertices that there is $k$ edges with one end in $U$ and with the other end in $V$.

My attempt:

Let $K$ be the set of edges from $\lambda(G)$. $G-K$ is disconnected and since $K$ is the smallest set of edges to disconnect graph $G$, $G-K$ has two components $C_1, C_2$. Now consider graph $C_1 \cup C_2 \cup K = G$. Edges from $K$ must have one end in $C_1$ and the other one in $C_2$ (so there are exactly $k$ vertices in each wchich connect with the other component). If some edge $e\in K$ connected $u, v \in C_1$ (for $C_2$ symtrically) then $K$ wouldn't be minimal - because after deleting this edge $C_1$ is still connected and thus it wasn't necessary to delete that edge to disconnect the graph. So in $K$ are only edges in form $\{v, u\}$ where $v \in C_1, \ u \in C_2$. The partition $\{U, V \}$ is $\{C_1, C_2 \}$.

I'd like to know if my thinking is correct. Thank you in advance.

Answer 1

The logic is (essentially) correct. I have a few minor things to point out.

You are making a bit of a leap when you say

since $K$ is the smallest set of edges to disconnect graph $G$, $G−K$ has two components $C_1, C_2$.

In principle there could be more components; it takes some extra argument to say that if there were more components, $G-K$ wouldn't be minimal. You could include that argument, but you don't need it.

It is simpler to say that since $K$ disconnects $G$, $G-K$ has some connected component $C_1$ which is not all of $G$. Let $C_2 = G - C_1$: the rest of $G$, whether that's connected or not. Now your argument still shows that all edges of $K$ must go between $C_1$ and $C_2$, otherwise they could be omitted.

Also, the argument

after deleting this edge $C_1$ is still connected and thus it wasn't necessary to delete that edge to disconnect the graph

isn't quite what you want here. It doesn't matter whether $C_1$ is connected or not after deleting that edge. The point is that if an edge $e$ does not go between $C_1$ and $C_2$, then $K' = K - \{e\}$ is also an edge cut, because $G - K'$ still has no edges between $C_1$ and $C_2$, so it's not connected.