Sheet 2, no. 6:
Let G be connected.
How many components are left when we remove a lambda set of separating edges?
How many components are left when we remove a kappa-set of separating vertices?
Removing a minimum separating set of edges will result in 2 components (seeproof below).
For separating sets of vertices, consider the star K_1,r (one vertex v connected to r other vertices). Removing v will leave r isolated vertices (so we have r components), and r can be as large as we want, so there is no bound on the number of components.
Now let’s give an actual proof that removing a minimum separating set of edges will result in just 2 components.
First consider the case lambda = 1, i.e. the graph has some cut-edge uv.
Now G – uv is disconnected, but by adding just one edge (between u and v) we must get the connected graph G. A single edge uv can only join two components together (the component that contains u and the component that contains v). So G-uv cannot have more than 2 components.
For lambda > 1, let A be a separating set of lambda edges, let e be one of the edges of A, and define A’ := A \ {e}. (So A = A’ union {e}).
Note that A’ is too small to be a separating set (since |A’| = lambda – 1), so G-A’ is still connected. But now, removing edge e will disconnect the graph, since (G-A’)-{e} = G-A.
So the edge e is a cut-edge in G-A’, and as we saw above, (G-A’)-{e} must have only 2 components; that is, G-A has only 2 components.
