déconnecter un graphe

Si $k<n-1$, le graphe ne peut pas être connexe (et c'est optimal, un arbre - connexe - a $n-1$ arêtes).

Je ne pense pas que ça serve. C'était juste que ton $k<n/2$ n'était pas optimal.

PS. Dans un graphe à $n$ sommets et $k$ arêtes, le degré minimum d'un sommet est au plus égal à $2k/n$.

Il doit y avoir des conditions sur $n$ et la condition de planarité me paraît inutilement forte. Parce que si $n \leq 4$ et que $G=K_n$ (graphe complet), il est impossible de perdre la connexité en enlevant des sommets. Donc, on va supposer que $n \geq 5$ et du coup, puisque le graphe est planaire, ce n'est pas un graphe complet et $k < \frac{n(n-1)}{2}$, d'où $\frac{2k}{n} < n-1$.

La somme des degrés étant le double du nombre d'arêtes vaut donc ici $2k$.

Ainsi, le degré moyen dans le graphe est $\frac{2k}{n}$. En particulier, il existe un sommet de degré $d \leq \frac{2k}{n}$. Si on élimine tous ses voisins, ce sommet est alors isolé (on a éliminé au plus $n-2$ sommets, donc il en reste au moins deux) et le graphe résultant n'est plus connexe.

Cela dit, du moment qu'au départ $G$ n'est pas complet, planaire ou pas, ça marche.

Pierre.