0
$\begingroup$

I am trying to solve this assignment:
Find all $n \in \mathbb{N}$ for which the following is true: By removing two random edges from graph $K_n$ we create at most $(n - 3)$-connected graph.

I would say that it is true for all odd $n$, but I got to this conclusion just by drawing some graphs and highlighting the disjunct paths in them in accordance with Menger's theorem. Still - I am not exactly sure about it, nor have I been able to formulate a solid proof. Can someone please give me a little push?

1 Answers 1

2

I don't see how the random element enters into it -- it seems you actually mean "by removing any two edges"?

If a graph is $(n-2)$-connected that means we can't remove $n-3$ vertices leaving it disconnected. That is, any three vertices are connected by edges among themselves. This will be the case if and only if we remove $2$ edges that have no vertex in common. That's possible if and only if $n\ge4$. So the condition you're looking for is $n\lt4$.

  • 0
    I meant any two edges. Sorry for the confusion, the original assignment is in Czech, so I've tried to translate it and made an error. I am certainly thankful for your answer, but I'm a little confused about it. For example: When given a graph $K_5$: The graph is $4$-connected, so it stays connected even after deleting any 3 vertices, right? But can you please tell me how you got that we must remove the 2 edges that have no vertex in common? At first I thought that it will be true only for $n =1,2,3$, but the Menger's theorem is confusing me. What does it mean then? If you can elaborate please.2011-11-09