Graful K_n

[Vlad Matei]

Fie \( n>3 \) puncte in spatiu, oricare patru necoplanare, conectate oricare doua prin sarme.
1) Aratati ca prin taierea a mai putin de \( n-1 \) sarme structura nu devine deconectata.
2) Gasiti numarul minim de sarme astfel incat sa existe un mod in care sa deconectam structura prin taierea acelui numar de sarme.

Dan Schwarz, Stelele Matematicii 2007

[Filip Chindea]

Fie \( n > 3 \) si graful \( G \simeq K_n \).
1) Aratati ca \( \lambda(G) \ge n-1 \), unde prin \( \lambda \) am notat edge-conectivitatea lui \( G \).
2) Gasiti \( k \) minimal astfel incat exista \( M \subseteq E(G) \), \( |M| = k \) iar \( G - M \) disconex.

Dan Schwarz, Stelele Matematicii 2007

Sa vedem daca a meritat sa ramana nerezolvata cinci luni

Presupunem contrariul. Atunci exista \( M \subseteq E(G) \) cu \( |M| < n - 1 \), iar \( G - M =: H \), \( V(H) \) partitionat in \( A, B \) cu \( E(A, B) \) vida.

Astfel, \( {n \choose 2} - (n - 2) \le ||H|| \le {|A| \choose 2} + {|B| \choose 2} = {n \choose 2} - |A| \cdot |B| \), si \( n - 2 \ge |A| \cdot |B| = |A| \cdot (n - |A|) \ge n - 1 \), o contradictie.

Se obtine imediat ca \( \lambda(G) = n - 1 \) (eliminand toate muchiile la care un varf este incident obtinem doua componente, iar acestea sunt in numar de \( n - 1 \)).

Aceasta rezolva si a doua parte a problemei, cu raspunsul \( k = n - 1 \).