<|endoftext|> Sinon, l’algorithme retourne un line-graphe de subdivision bipartie de $K_4$ de taille minimale.
- Exécuter l’algorithme \[reco.a.subK4\].
- $O(n^{20})$.
D’après le lemme \[reco.l.techK4\] on sait que, dans $G$, les line-graphes de subdivision *non-triviales* de $K_4$ sont exactement les line-graphes de subdivision *bipartie* de $K_4$. Ces dernières configurations sont donc correctement détectées par l’algorithme \[reco.a.subK4\].
### Prismes impairs
Nous pouvons désormais fournir un algorithme en temps polynomial pour détecter les prismes impairs. Il faut se montrer prudent car dans ce cas la technique des plus courts chemins fonctionne mal :
![Graphe contenant six prismes impairs\[reco.f.prismeimp\]](fig.reco.2)
Le graphe $G$ représenté figure \[reco.f.prismeimp\] comporte 5 cliques maximales de taille au moins trois. On vérifie que les quatre cliques grisées sont deux à deux ennemies (voir sous-section \[pair.ss.cliquesennemies\] page pour de plus amples explications sur les cliques ennemies). Tous les chemins sortants les reliant à la clique non grisée sont de longueur paire. On en déduit que $G$ est le line-graphe d’un graphe biparti, et qu’il est de Berge (pour s’en convaincre, on peut utiliser le lemme \[pair.l.caracennemie\], qui aura finalement servi à quelque chose !). Pour toute paire de cliques grisées, il existe un unique prisme impair de $G$ qui ait ces cliques pour triangles. On constate que les chemins $P_1$, $P_2$ et $P_3$ induisent un prisme impair de $G$ de taille minimale. Pourtant, si on remplace $P_1$, ou même simplement le sous-chemin ${}a_1 {\!-\!}P_1 {\!-\!}m_1 {}$ par un plus court chemin $P$, on n’a pas la garantie d’obtenir à nouveau un prisme impair. Un algorithme naïf par plus courts chemins risque donc d’échouer. En fait un tel algorithme (calculer les plus courts chemins pour chaque sextuplet $(a_1, a_2, a_3, b_1, b_2, b_3)\in V^6$) executé sur $G$ finirait bien par détecter un prisme impair : celui contenant les deux triangles les plus en haut sur le dessin. Mais il ne trouverait pas un prisme de taille minimale de $G$, ce qui fait qu’on ne voit comment prouver qu’il fonctionne (s’il fonctionne !).
On peut cependant remarquer que $G$ contient le line-graphe d’une subdivision bipartie de $K_4$ : le sous-graphe induit en oubliant les sommets “pleins”. Si ce type de configuration est interdite, il y a donc encore un espoir que les techniques de plus courts chemins fonctionnent. Le lemme suivant montre que cet espoir est fondé. On remarquera qu’il n’est même plus nécessaire de partir d’un prisme de taille minimale, ni de plus courts chemins, ce qui montre que l’interdiction des line-graphes de subdivision de $K_4$ est une contrainte très forte dont on a déjà eu une illustration dans la preuve du théorème fort des graphes parfaits (voir les théorèmes \[graphespar.t.spgtprismepair\] à \[graphespar.t.sartemis\]).
\[reco.l.prismeimp\] Soit $G$ un graphe sans trou impair et sans line-graphe de subdivision bipartie de $K_4$. Soit $