1
$\begingroup$

$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 .

$\endgroup$
2
  • 1
    $\begingroup$ 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). $\endgroup$
    – TravisJ
    Feb 16 '15 at 14:03
  • $\begingroup$ TravisJ thanks for the hint it helped . $\endgroup$ Feb 19 '15 at 8:37
-1
$\begingroup$

some trail and error led me to this solution hope its a valid one .

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$$

where:

  • $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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.