Bonjour , j'espère que vous allez bien. Je bloque à l'exercice suivant :
Soit G = (S, A) un graphe simple, le nombre de croisement, noté Cr (G), est le nombre minimal de croisement necessaire pour dessiner ´G dans le plan.
1-Montrer par recurrence sur le nombre d'arêtes que Cr ˆ(G) ≥ |A| − 3|S|.
2-Soit G = (S, A) un graphe, on note |S| = s et |A| = a. Soit p ∈ [0, 1]. On choisit de maniere independante des sommet avec une probabilite p pour constituer un ensemble S' ⊂ S. On note X la variable aleatoire ´ du nombre de croisement du graphe induit par S'. On note Y la variable aleatoire correspondant au nombre de sommet et Z la variable aleatoire correspondant au nombre d'aretes.
Montrer que E(Y) = ps, E(Z) = p²a et E(X) ≤ p^4*Cr(G).
J'ai fait la première question , ainsi que E(Y)=ps , cependant j'arrive pas à montrer les deux dernières propriétés. Merci