# Number of connected components after removing $t$ edges from K-edge-connected graph

$k,s,t$ are positive integers such that $k(s+1)>2t$.

prove: if $G$ k-edge-connected graph then removing any $t$ edges from $G$ will yield a graph with at most $s$ connected components.

question from old exam i'm trying to solve .... have no idea where to start . the graph is k-connected so i guess i'm expected to use "Whitney theorem" or "Manger theorem" but i don't see how i can derive something about number of connected components using mentioned theorems and the given inequality

after some thought i think i need to use induction here .

• Think about putting the different connected components back together to make the original k edge connected graph. You cannot just add a single edge between most components (because the removal of a single edge would disconnect the graph). Feb 16 '15 at 14:03
• TravisJ thanks for the hint it helped . Feb 19 '15 at 8:37

given $s$ number of connected components after the removal of $t$ edges . each component had at least $k$ edges what were connecting vertices in it to the other vertices of the original graph $G$ , moreover each removed edge were connected to 2 vertices so it was connecting 2 components before it was removed. from this we can derive the wanted inequality
$$sk < 2t < sk + k$$
• $sk$ the minimal number of edges you need to remove to yield $s$ connected components
• $2t$ the number of removed edges
• $sk + k = k(s+1)$ the number of edges you would need to remove if there were $s+1$ connected components