Propriétés

Par récurrence sur $n$. Pour $n=1$, le graphe ne va avoir que des boucles et le graphe ci-après montre qu'il est planaire et que la formule d'Euler fonctionne, il y a 1 sommet, une face infinie et chaque arête ajoute une face intérieure :

On suppose par récurrence que la propriété est vraie pour $n$ et on considère un multi-graphe connexe avec boucle planaire à $n+1$ sommets. Par exemple celui-ci :

Le graphe étant connexe il possède une arête et l'on peut fusionner ses sommets en conservant toutes les arêtes :

La formule est alors respectée pour ce nouveau graphe qui a une arête et un sommet de moins que le graphe original mais exactement le même nombre de faces. On en déduit : $F = (m-1) - (n-1) + 2 = m - n + 2$.

Si l'intérieur du cycle dans la représentation graphique contenait des sommets, le supprimer ne pourrait que déconnecter $G$. L'intérieur du cycle ne contient donc pas de sommets et comme il est induit c'est forcément une face.

Prenons une face d'un graphe planaire 3-connexe et considérons sa frontière. Si ce cycle n'est pas induit, on se retrouve dans la condition suivante :

Et supprimer $u$ et $v$ va déconnecter le graphe ce qui est impossible puisque le graphe est 3-connexe.

Supposons cette frontière séparante et considérons $G_1, \dots, G_k$ les $k$ parties connexe de $G$ privé du cycle. Pour chaque $G_i$, on note $A(G_i)$ les sommets du cycle étant des extrémités d'arête finissant $G_i$. Comme $G$ est 3-connexe $\vert A(G_i)\vert \geq 3$ pour tout $i$. Pour $G_1$ on se retrouve dans cette situation :

Mais comme $G_2$ est aussi à l'extérieur du cycle il est forcément à l'intérieur de 2 éléments de $A(G_1)$ consécutifs :

Ce qui est impossible puisque les supprimer déconnecterait $G_1$ de $G_2$ (aucun $G_i$, $i>2$, ne peut avoir de sommets de $A(G_i)$ de part et d'autre de ces sommets) et $G$ est $3$-connexe :

Il y a donc au mieux un seul $G_i$ et le cycle est non séparant.

Pour chacune des $F$ faces d'un dessin planaire de $G$, on note $f_i$ le nombre d'arêtes formant la frontière de la face $i$. Comme chaque arête est sur la frontière d'exactement 2 faces, on a $\sum f_i = 2m$ et comme chaque face a au moins 3 arêtes il vient l'inégalité : $3F\leq \sum f_i = 2m$. En injectant la formule d'Euler dans cette inégalité on obtient $3(m - n + 2)\leq 2m$ d'où le résultat.

Si tous les sommets avaient un degré strictement plus grand que 5 on aurait : $2\cdot m = \sum\delta(x) \geq 6 \cdot n$, donc $m\geq 3\cdot n$. Ceci est cependant impossible puisque $m \leq 3\cdot n - 6 < 3\cdot n$.

On va associer à chaque sommet $x$ du graphe une charge $c(x) = 6-\delta(x)$. Pour notre graphe, seul les sommets de degré 5 on une charge positive (valant 5). On va ensuite appliquer la règle suivante : "tout sommet de degré 5 va donner 1/5 de ses charges à chacun de ses voisins".

À l'issue de l'application de cette règle, la somme totale des charge vaut toujours 12 : il existe un sommet de charge strictement positive. On étudie maintenant les cas :

• si son degré vaut 5 c'est qu'un de ses voisins lui a donné une charge et la proposition est démontrée
• si son degré vaut 6 c'est qu'elle a reçu une charge d'un de ses voisins et la proposition est démontrée
• si son degré vaut 7 ou plus alors on a deux cas :
  • soit deux de ses voisins de degré 5 forment une arêtes et la proposition est démontrée
  • soit aucun de ses voisins de degré 5 ne forme une arête ce qui signifie, comme le graphe est triangulé, que seul un de ses voisins sur deux dans l'ordre du dessin peut être de degré 5

Mais ce dernier cas est impossible car dans ce cas là sa charge finale serait inférieure à :

Donc les sommets de charge finale positive contiennent dans leur voisinage fermé un sommet de degré 5 et un sommet de degré inférieur ou égal à 6 qui sont voisins.

Il suffit de donner une charge initiale de $6-\delta(x)$ à chaque sommet $x$ et d'appliquer la règle :

"tout sommet de degré 5 va donner 1/4 de ses charges à chacun de ses voisins de degré 7 ou plus".

Le même raisonnement que précédemment montre qu'à l'issue de l'application de la règle la charge totale doit toujours être strictement positive et examinons les cas :

• si son degré vaut 5 c'est qu'au plus 3 de ses voisins sont de degré 7 ou plus
• il est impossible que son degré soit 6 puisqu'il ne peut pas gagner de charge
• si son degré vaut 7 ou plus alors on a deux cas :
  • soit trois de ses voisins consécutifs sont de degré 5
  • soit au plus 2 voisins consécutifs sont de degré 5 suivi d'un sommet de degré > 6.

Dans ce dernier cas, le nombre maximum de voisin de degré 5 que peut avoir le sommet est $\lfloor\frac{3 2}{3}\delta(x)\rfloor$ et sa charge finale est inférieure à :

On sait que $m \leq 3n-6$ pur un graphe planaire. Tout graphe avec plus d'arêtes va donc avoir au moins 1 croisement par arête surnuméraire : on peut itérativement supprimer une arête qui possède un croisement (il en existe forcément une si $m-3n+6>0$).

Si on peut prouver cette inégalité en utilisant la méthode probabiliste, il faut pouvoir associer à un graphe $G=(V, E)$ un autre graphe, $H=(V', E\vert_{V'})$, aléatoire tel que $V'$ est un sous-ensemble de $V$ où tout élément a été choisi indépendamment des autres avec une propriété $p$. On a alors :

• $\mathbb{E}[v(H)] = p\cdot n$
• $\mathbb{E}[e(H)] = p^2\cdot m$

Si on dessine $H$ en prenant la restriction d'un dessin de $G$ minimisant son nombre de croisements. Le nombre moyen de croisements de ce dessin pour $H$ vaut $p^4\text{cr}(G)$ puisque chaque croisement est un formé de 2 arêtes de $G$ qui ont chacune une probabilité $p^2$ d'être dans $H$.

De là si $C(H)$ est le nombre de croisement de la restriction à $H$ d'un dessin de $G$ minimisant les croisement, on a : $C(H) \geq \text{cr}(H) \geq e(H) - 3 \cdot v(H)$. Donc par linéarité de l'espérance on a également : $ \mathbb{E}[C(H)]\geq \mathbb{E}[e(H)] - 3 \cdot \mathbb{E}[v(H)]$ c'est à dire :

Et donc :

Comme on cherche une borne min, il faut maximiser la fonction $f(p)=\frac{p\cdot m - 3\cdot n}{p^3}$, ce qui est le cas pour $p = \frac{9}{2}\frac{n}{m}$, pour simplifier on prend $p=4n/m$, ce qui impose $m\geq 4n$ et donne le résultat.